海量點集數據的極大點查找算法及相關應用研究.pdf

1、在現(xiàn)實應用中存在大量的海量數據，由于其太大而不能完全裝入計算機內存。因此在快速的內存和相對慢速的外存（比如硬盤）之間的輸入/輸出（I/O）通訊就成了制約算法性能的主要瓶頸。特別在以下方面：空間數據庫中的海量幾何數據、地理信息系統(tǒng)（GIS）、約束邏輯規(guī)劃、數據庫、統(tǒng)計學、虛擬現(xiàn)實系統(tǒng)、計算機圖形學。由此產生了外存儲算法與數據結構的設計和分析領域，其主要目標就是研究算法的局部性以盡量減小程序的輸入/輸出代價。 極大點查找問題是是計算

2、幾何的一個重要的基本問題。由于極大點集在一個點集的邊界上存在很多有意義的特性，其與凸包、最近點對等問題均有密切的聯(lián)系。同時極大點查找問題也出現(xiàn)了越來越多的各種應用。 本文研究了已有的極大點查找算法。在此基礎上提出一種針對海量點集數據的極大點查找概率算法，并證明了算法的可靠性。通過實驗取得了很好的實驗效果。并對其在數據庫查詢中的應用進行了研究。 本文的研究工作和創(chuàng)新包括以下兩個方面： （1）針對極大點查找問題，目前