  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 uncertainty models have been
proposed, which do not allow for accurate probabilistic search. In this paper,
we fill this gap by addressing 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 solution 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 approach can be used in Monte-Carlo based approximation solutions. We
include an extensive experimental study to support our theoretical results.
