BFPκNN: An Efficient κ-Nearest-Neighbor Search Algorithm for Historical Moving Object Trajectories

摘要

This paper studies κ-nearest-neighbor (κNN) search on R-tree-based structures storing historical information about trajectories. We develop BFPκNN, an efficient best-first based algorithm for handling κNN search with arbitrary values of k, which is I/O optimal, i.e., it performs a single access only to those qualifying nodes that may contain the final result. Furthermore, in order to save memory space consumption and reduce CPU overhead further, several effective pruning heuristics are also proposed. Finally, extensive experiments with synthetic and real datasets show that BFPκNN outperforms its competitor significantly in both efficiency and scalability in all cases.