反向最近鄰聯(lián)合查詢技術(shù)的研究.pdf

1、隨著GPS設(shè)備的不斷普及，基于位置的服務(wù)逐漸走進我們的日常生活。反向k最近鄰(Reverse k Nearest Neighbor，RkNN)查詢作為基于位置服務(wù)的支持技術(shù)之一，已經(jīng)成為當前的一個研究熱點問題。RkNN查詢檢索的是以查詢點為k最近鄰的對象集合，目前研究主要集中在單色反向k最近鄰查詢上，而對于雙色反向k最近鄰查詢研究較少，且現(xiàn)有的算法不能高效地處理查詢發(fā)起者為一個集合的雙色反向k最近鄰查詢問題。針對現(xiàn)有查詢算法的不足，本文

2、提出了一種基于集合的雙色反向k最近鄰查詢——雙色反向k最近鄰聯(lián)合查詢(Bichromatic Reverse k Nearest Neighbor Combined query，CBRkNN query)，并給出了高效的CBRkNN查詢算法。
　　首先，在分析和總結(jié)現(xiàn)有RkNN查詢算法的基礎(chǔ)上，本文提出了CBRkNN查詢問題，并且給出了基于Finch的CBRkNN查詢算法。算法首先根據(jù)查詢集合構(gòu)造出查詢區(qū)域，然后檢索出落入該區(qū)域內(nèi)

3、的用戶構(gòu)成候選集，最后對候選集中每個用戶進行確認，排除錯誤的查詢結(jié)果。實驗驗證了算法的高效性。
　　其次，通過對基于Voronoi圖的BRNN查詢算法的深入研究，本文引入了影響區(qū)域的概念并提出了基于影響區(qū)域的CBRNN查詢算法。算法將查詢集合與Voronoi圖結(jié)合，給出了組Voronoi圖的定義。算法利用組Voronoi圖構(gòu)造出查詢集合的影響區(qū)域，檢索出落入該區(qū)域內(nèi)的用戶構(gòu)成結(jié)果集。實驗驗證了基于影響區(qū)域的CBRNN查詢算法比基于

4、Finch的CBRNN查詢算法效率更高。
　　最后，本文引入k級影響區(qū)域的概念并利用該區(qū)域減小搜索空間，給出了基于k級影響區(qū)域的CBRkNN查詢算法(k>1)。算法根據(jù)查詢集合劃分平面，引入凸多邊形級別的定義，搜索出級別小于k的凸多邊形構(gòu)成k級影響區(qū)域，最后檢索出落入該區(qū)域內(nèi)的用戶構(gòu)成結(jié)果集。實驗驗證了基于k級影響區(qū)域的CBRkNN查詢算法比基于Finch的CBRkNN查詢算法效率更高。
　　綜上所述，本文針對現(xiàn)有BRkNN