Evaluating continuous K-nearest neighbor query on moving objects with uncertainty

Yuan Ko Huang, Shi Jei Liao, Chiang Lee

研究成果: Article同行評審

19 引文 斯高帕斯(Scopus)


Continuous K-nearest neighbor (C K NN) query is one of the most fundamental queries in the field of spatio-temporal databases. Given a time interval [ts, te], a C K NN query is to retrieve the K-nearest neighbors (K NNs) of a moving user at each time instant within [ts, te]. Existing methods for processing a C K NN query, however, assume that each object moves with a fixed direction and/or a fixed speed. In this paper, we relieve this assumption by allowing both the moving speed and the moving direction of each object to vary. This uncertainty on speed and direction of a moving object would increase the complexity of processing a C K NN query. We thoroughly analyze the involved issues incurred by this uncertainty and propose a continuous possible KNN (CPKNN) algorithm to effectively find the objects that could be the K NNs. These objects are termed the possible KNNs (PKNNs) in this paper. A probability-based model is designed accordingly to quantify the possibility of each P K NN being the K NN. In addition, we design a PKNN updating mechanism to rapidly evaluate the new query result when object updates occur. Comprehensive experiments are conducted to demonstrate the effectiveness and the efficiency of the proposed approach.

頁(從 - 到)415-437
期刊Information Systems
出版狀態Published - 2009 6月

All Science Journal Classification (ASJC) codes

  • 軟體
  • 資訊系統
  • 硬體和架構


深入研究「Evaluating continuous K-nearest neighbor query on moving objects with uncertainty」主題。共同形成了獨特的指紋。