Efficient KNN processing over moving objects with uncertain velocity

Spatio-temporal databases aim at combining the spatial and temporal characteristics of data. The continuous K-Nearest Neighbor (CKNN) query is an important type of spatiotemporal query that finds the K-Nearest Neighbors (KNNs) of a moving query object at each time instant within a given time interval [t_s, t_e]. In this paper, we investigate how to process a CKNN query efficiently under the situation that each object moves with an uncertain velocity. This uncertainty on the velocity of each object inevitably results in high complexity of the CKNN problem. We propose a cost-effective PKNN algorithm to tackle the complicated problem incurred by this uncertainty.