摘要：隨著基于位置服務(wù)的廣泛應(yīng)用,時(shí)間依賴路網(wǎng)上的對(duì)象查詢逐漸成為研究熱點(diǎn)。以往研究大多只針對(duì)時(shí)間依賴路網(wǎng)上的靜態(tài)對(duì)象(如加油站、餐廳等),未考慮到移動(dòng)對(duì)象(如出租車)的情況,而移動(dòng)對(duì)象的查詢?cè)谌粘Ｉ钪杏兄浅V泛的應(yīng)用場(chǎng)景。因此,文中提出了一種針對(duì)時(shí)間依賴路網(wǎng)上的移動(dòng)對(duì)象K近鄰查詢算法TD-MOKNN,該算法分為預(yù)處理階段和查詢階段。在預(yù)處理階段,通過建立路網(wǎng)和網(wǎng)格索引,提出了一種新的移動(dòng)對(duì)象到路網(wǎng)的映射方法,解除了以往研究假設(shè)移動(dòng)對(duì)象恰好在路網(wǎng)頂點(diǎn)上的限制;在查詢階段,采用啟發(fā)式搜索,借助倒排網(wǎng)格索引計(jì)算了一種新的高效啟發(fā)值,通過預(yù)處理信息和啟發(fā)值設(shè)計(jì)了高效K近鄰查詢算法,并給出了算法的正確性證明和時(shí)間復(fù)雜度分析。實(shí)驗(yàn)驗(yàn)證了所提算法的有效性,相比現(xiàn)有算法,TD-MOKNN算法在遍歷頂點(diǎn)數(shù)和響應(yīng)時(shí)間上分別減少了55.91%和54.57%,查詢效率平均提升了55.2%。