海量點(diǎn)集數(shù)據(jù)的極大點(diǎn)查找算法及相關(guān)應(yīng)用研究.pdf

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

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