Efficient k-Nearest-Neighbor Search Algorithms for Historical Moving Object Trajectories

k Nearest Neighbor (kNN) search is one ofthe most important operations in spatial and spatio-temporal databases.Although it has received considerable attention in the databaseliterature, there is little prior work on kNN retrieval formoving object trajectories. Motivated by this observation, this paperstudies the problem of efficiently processing kNN (k\ge 1)search on R-tree-like structures storing historical information aboutmoving object trajectories. Two algorithms are developed based onbest-first traversal paradigm, called BFPkNN and BFTkNN,which handle the kNN retrieval with respect to the static querypoint and the moving query trajectory, respectively. Both algorithmsminimize the number of node access, that is, they perform a singleaccess only to those qualifying nodes that may contain the finalresult. Aiming at saving main-memory consumption and reducing CPU costfurther, several effective pruning heuristics are also presented.Extensive experiments with synthetic and real datasets confirm that theproposed algorithms in this paper outperform their competitorssignificantly in both efficiency and scalability.