空間數(shù)據(jù)的聚集最遠(yuǎn)鄰居查詢研究.pdf

1、在這篇文章中，研究一種新型的空間查詢，叫做聚集k最遠(yuǎn)鄰居查詢(簡(jiǎn)稱AkFN Query)。給定一個(gè)數(shù)據(jù)點(diǎn)集P和一個(gè)查詢點(diǎn)集Q，AkFN查詢返回P里面離Q中所有點(diǎn)的聚集距離最大的k個(gè)點(diǎn)。例如，要在一個(gè)城市里新開(kāi)一間旅館，希望選一個(gè)地點(diǎn)到所有現(xiàn)有的旅館聚集距離最大，以此最大限度的降低競(jìng)爭(zhēng)。
　　 主要討論三種聚集函數(shù)，和(Sum)、最大值(Max)和最小值(Min)。假設(shè)數(shù)據(jù)集是R樹(shù)索引的，針對(duì)查詢集為內(nèi)存存儲(chǔ)時(shí)，提出了兩個(gè)高效解決

2、所有三種AkFN查詢的算法，最小界定(簡(jiǎn)稱MB)算法和最好優(yōu)先(簡(jiǎn)稱BF)算法。其中BF算法是增量式的，而且可以證明是IO開(kāi)銷最優(yōu)的算法。另外，提出一種基于凸包(簡(jiǎn)稱CHB)的算法來(lái)解決聚集函數(shù)為Sum和Max的情況，它利用到了數(shù)據(jù)集的凸包。另外，對(duì)于查詢集很大為磁盤存儲(chǔ)時(shí)，對(duì)以上三種算法進(jìn)行擴(kuò)展分別提出了磁盤最小界定(簡(jiǎn)稱DMB)算法、磁盤最好優(yōu)先(簡(jiǎn)稱DBF)算法和磁盤基于凸包(簡(jiǎn)稱DCHB)的算法。
　　 在合成數(shù)據(jù)集和真