Probabilistic nearest neighbor queries on uncertain moving object trajectories (technical report

Nearest neighbor (NN) queries in trajectory databases have received significant attention in the past, due to their application in spatio-temporal data analysis. Recent work has considered the realistic case where the trajectories are uncertain; however, only simple un-certainty models have been proposed, which do not allow for ac-curate probabilistic search. In this paper, we fill this gap by ad-dressing probabilistic nearest neighbor queries in databases with uncertain trajectories modeled by stochastic processes, specifically the Markov chain model. We study three nearest neighbor query semantics that take as input a query state or trajectory q and a time interval. For some queries, we show that no polynomial time so-lution can be found. For problems that can be solved in PTIME, we present exact query evaluation algorithms, while for the general case, we propose a sophisticated sampling approach, which uses Bayesian inference to guarantee that sampled trajectories conform to the observation data stored in the database. This sampling ap-proach can be used in Monte-Carlo based approximation solutions. We include an extensive experimental study to support our theoret-ical results. 1