Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity

Yuan Ko Huang, Chiang Lee

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


Continuous Range (CR) query and Continuous K-Nearest Neighbor (CKNN) query are two important types of spatio-temporal queries. Given a time interval [ts, te] and a moving query object q, a CR query is to find the moving objects whose Euclidean distances to q are within a user-given distance at each time instant within [ts, te]. A CKNN query is to retrieve the K-Nearest Neighbors (KNNs) of this query object q at each time instant within [ts, te]. In this paper, we investigate how to process these spatio-temporal queries efficiently under the situation that the velocity of each object is not fixed. This uncertainty on the velocity of object inevitably results in high complexity in processing spatio-temporal queries. We will discuss the complications incurred by this uncertainty and propose two algorithms, namely the Possibility-based possible within objects searching algorithm and the Possibility-based possible KNN searching algorithm, for the CR query and the CKNN query, respectively. A Possibility-based model is designed accordingly to quantify the possibility of each object being the result of a CR query or a CKNN query. Comprehensive experiments are performed to demonstrate the effectiveness and the efficiency of the proposed approaches.

Original languageEnglish
Pages (from-to)163-200
Number of pages38
Issue number2
Publication statusPublished - 2010 Apr

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Geography, Planning and Development


Dive into the research topics of 'Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity'. Together they form a unique fingerprint.

Cite this