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

Continuous Range (CR) query and Continuous K-Nearest Neighbor (CKNN) query are two important types of spatio-temporal queries. Given a time interval [t_s, t_e] 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 [t_s, t_e]. A CKNN query is to retrieve the K-Nearest Neighbors (KNNs) of this query object q at each time instant within [t_s, t_e]. 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.