TY - JOUR
T1 - Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity
AU - Huang, Yuan Ko
AU - Lee, Chiang
N1 - Funding Information:
Acknowledgements This work was supported by National Science Council of Taiwan (R.O.C.) under Grants NSC96-2221-E-006-260-MY2 and NSC96-2221-E-006-261-MY2.
PY - 2010/4
Y1 - 2010/4
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77954085014&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77954085014&partnerID=8YFLogxK
U2 - 10.1007/s10707-009-0081-8
DO - 10.1007/s10707-009-0081-8
M3 - Article
AN - SCOPUS:77954085014
SN - 1384-6175
VL - 14
SP - 163
EP - 200
JO - GeoInformatica
JF - GeoInformatica
IS - 2
ER -