移動對象反向k近鄰查詢研究.pdf

1、近年來，移動設備和無線網(wǎng)絡的廣泛應用帶來了基于位置的服務(LBS)應用的快速發(fā)展。位置信息相關的查詢在LBS中扮演了極為重要的角色。其中一種重要的查詢是(單色)反向k近鄰查詢(RkNN)，該查詢能夠返回所有以查詢點作為k近鄰的對象集合。隨著無線通訊技術的發(fā)展，用戶已不再滿足于僅獲取靜止對象的信息，還希望LBS應用能夠提供移動對象的信息。當前，針對移動對象的空間查詢受到了越來越多的關注。
　　 給定一個查詢點q和一個查詢時間段T，

2、移動對象反向k近鄰查詢(M-RkNN)能夠返回T時間段內所有時刻查詢點q的反向k近鄰集合?，F(xiàn)有唯一能夠處理該查詢的算法(M-SAA)存在效率不高和只能處理2維移動對象等缺陷。為解決這一問題，本文提出了一種能夠有效解決多維M-RkNN查詢的新算法(M-TPL)。該算法基于過濾-精煉框架，并整合了兩種高效的動態(tài)裁剪策略：移動對象支配域和時變最小包圍盒對角線長度裁剪策略。
　　 當查詢點也是線性運動時，M-RkNN問題將變得更加復雜。

3、給定一個查詢點q和一個查詢時間段T，其中q使用關于t的線性函數(shù)表示，移動對象連續(xù)k近鄰查詢(CM-RkNN)可以返回查詢時間段T內任意時刻查詢點q在新位置的反向k近鄰集合。本文首次提出并正式定義了CM-RkNN查詢，并且給出了能夠高效處理該查詢的CM-TPL算法。
　　 實驗結果表明：(1)M-TPL算法在2維數(shù)據(jù)集上比M-SAA算法大幅節(jié)省I/O和查詢時間開銷，并且它能夠有效處理多維M-RkNN查詢，且查詢性能并不隨維度增長下