路網(wǎng)中移動對象最近鄰及反向最近鄰查詢處理研究.pdf

1、無線廣播技術高速發(fā)展和移動通信設備的不斷普及使得位置相關服務(location-based services，LBSs)越來越走進我們的日常生活。而位置相關查詢處理(location-based queries，LBQs)作為位置相關服務的支持性技術之一，已經(jīng)成為一個研究熱點問題。近年來，研究者們對位置相關查詢，特別是最近鄰查詢和反向最近鄰查詢進行了深入的研究，提出了許多有效的查詢處理方法。但是，在最近鄰查詢方面，目前尚無人提出路網(wǎng)中可

2、變速移動對象的連續(xù)k近鄰查詢處理算法；在反向最近鄰方面，目前尚無人提出徹底的、對象和查詢點均可連續(xù)移動的、路網(wǎng)中連續(xù)反向k近鄰處理算法。目前位置相關查詢處理的主要形式都是基于傳統(tǒng)的按需訪問（on-demand access）模式。按需訪問方式只適合于無線信道和服務器處理容量都充足的輕負載系統(tǒng)。當客戶量大、客戶發(fā)起的移動查詢量大時，服務器的處理能力和無線信道的帶寬都會影響到查詢處理的效率和速度。近年來，人們開始關注數(shù)據(jù)廣播環(huán)境下的位置查詢

3、處理的研究，也提出了一些研究成果。但是到目前為止，這些研究只是局限于歐氏空間。歐氏空間環(huán)境下的相關算法是不能通過簡單的修改而應用到路網(wǎng)環(huán)境下的，所以研究數(shù)據(jù)廣播環(huán)境下路網(wǎng)中位置查詢處理算法是非常迫切、必要的。
　　首次討論了路網(wǎng)中反向k近鄰查詢連續(xù)監(jiān)控問題(CRkNN)，分析了路網(wǎng)中移動對象連續(xù)反向k近鄰查詢的關鍵技術。提出了一種全新的稱為DLM樹的數(shù)據(jù)結構來索引CRkNN查詢的監(jiān)控范圍，從而將CRkNN查詢問題的處理簡化為監(jiān)控幾

4、個多路樹，而不必在位置更新發(fā)生時重新計算查詢結果。提出了統(tǒng)一解決單色數(shù)據(jù)集和雙色數(shù)據(jù)集上反向k(≥1)近鄰查詢的框架和相應算法；為進一步提高算法的效率，給出了有關引理以盡可能地削減查詢空間，并提出一些優(yōu)化技術以高效地處理與查詢結果有關的位置更新。模擬實驗表明所提出的算法是有效的。
　　討論了路網(wǎng)中不定速移動對象連續(xù)k近鄰查詢(CUkNN)的處理問題，分析目前現(xiàn)有的路網(wǎng)中移動對象連續(xù)k近鄰查詢算法的局限性。提出了一種不確定路網(wǎng)距離計

5、算模式以計算路網(wǎng)中不定速移動對象和移動查詢點之間的距離。基于這種距離模式，提出了兩種CUkNN的連續(xù)監(jiān)控算法，即CUkNN PLS和CUkNN Mean。在CUkNN PLS算法中，引入了可能距離區(qū)域和可能距離線段(PLS)的概念，以簡化對象o成為查詢q的kNN之一的概率值的計算。在CUkNN Mean算法中，為了進一步簡化概率的處理，我們沒有計算每個候選對象的成為查詢q的kNN之一、確切的概率值，而是提出了一種有效的方法來將所有可能成

6、為查詢q的kNN結果之一的對象按照其概率值遞減的順序進行排列，選擇排在前k位的對象構成最終的kNN結果集。此外，提出了一種處理對象速度超出界限和對象移動方向發(fā)生改變的方法，以維持查詢結果持續(xù)有效。通過用一種新穎、規(guī)整的方法組織有關數(shù)據(jù)結構，擴展所提出的CUkNN算法以高效地、低磁盤訪問代價地處理大路網(wǎng)中的CUkNN查詢。模擬實驗驗證了所提出算法的有效性和可擴展性。
　　首次討論了無線廣播環(huán)境下路網(wǎng)中連續(xù)最近鄰查詢處理問題(CNBN

7、N)。通過用屬性obj_dom來標記路網(wǎng)上每一條邊，以表明該邊屬于某個特定對象的voronoi多邊形，提出了NVD結構以保留NVD圖的特性。提出了一種稱之為NVD四分劃分的路網(wǎng)劃分方法，將路網(wǎng)劃分為一系列網(wǎng)格單元。特別地，各網(wǎng)格單元占據(jù)大致相同的存儲空間，而且具有較好的局部性保留性能。然后，提出了一種稱為NVD-DI的分布式索引結構以支持CNBNN查詢處理?；谶@種NVD-DI索引結構，提出了一種有效的CNBNN查詢處理算法。CNBNN