Predictive Nearest Neighbor Queries Over Uncertain Spatial-Temporal Data

Abstract. Predictive nearest neighbor queries over spatial-temporal da-ta have received significant attention in many location-based services including intelligent transportation, ride sharing and advertising. Due to physical and resource limitations of data collection devices like R-FID, sensors and GPS, data is collected only at discrete time instants. In-between these discrete time instants, the positions of the monitored moving objects are uncertain. In this paper, we exploit the filtering and refining framework to solve the predictive nearest neighbor queries over uncertain spatial-temporal data. Specifically, in the filter phase, our ap-proach employs a semi-Markov process model that describes object mo-bility between space grids and prunes those objects that have zero prob-ability to encounter the queried object. In the refining phase, we use a Markov chain model to describe the mobility of moving objects between space points and compute the nearest neighbor probability for each can-didate object. We experimentally show that our approach can filter out most of the impossible objects and has a good predication performance