時間依賴路網上的移動對象K近鄰查詢算法

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