移動(dòng)對(duì)象反向k近鄰查詢研究.pdf

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

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

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