Constrained k-nearest neighbor query processing over moving object trajectories

Given a set D of trajectories, a query object (point or trajectory) q, a time interval T, and a constrained region CR, a constrained k-nearest neighbor (CkNN) query over moving object trajectories retrieves from D within T, the k (>= 1) trajectories that lie closest to q and intersect (or are enclosed by) CR. In this paper, we propose several algorithms for efficiently processing CkNN search on moving object trajectories. In particular, we thoroughly investigate two types of CkNN queries, viz. CkNN(p) and CkNN(T) queries, which are defined w.r.t. stationary query points and moving query trajectories, respectively. The performance of our algorithms is evaluated with extensive experiments using both real and synthetic datasets.