%0 Journal Article
%T Efficient k-Nearest-Neighbor Search Algorithms for Historical Moving Object Trajectories
%A Yun-Jun Gao
%A Chun Li
%A Gen-Cai Chen
%A Ling Chen
%A Xian-Ta Jiang
%A Chun Chen
%A <br>Yun-Jun Gao
%A Chun Li
%A Gen-Cai Chen
%A Ling Chen
%A Xian-Ta Jiang
%A and Chun Chen
%J 计算机科学技术学报
%D 2007
%I 
%X k Nearest Neighbor (kNN) search is one of the most important operations in spatial and spatio-temporal databases. Although it has received considerable attention in the database literature, there is little prior work on kNN retrieval for moving object trajectories. Motivated by this observation, this paper studies the problem of efficiently processing kNN (k   1) search on R-tree-like structures storing historical information about moving object trajectories. Two algorithms are developed based on best-first traversal paradigm, called BFPkNN and BFTkNN, which handle the kNN retrieval with respect to the static query point and the moving query trajectory, respectively. Both algorithms minimize the number of node access, that is, they perform a single access only to those qualifying nodes that may contain the final result. Aiming at saving main-memory consumption and reducing CPU cost further, several effective pruning heuristics are also presented. Extensive experiments with synthetic and real datasets confirm that the proposed algorithms in this paper outperform their competitors significantly in both efficiency and scalability. Electronic supplementary material Electronic supplementary material is available for this article at and accessible for authorised users. Supported by the National High Technology Development 863 Program of China under Grant No. 2003AA4Z3010-03.
%K query processing
%K k-nearest-neighbor search
%K moving object trajectories
%K algorithms
%K spatio-temporal databases<br>时空数据库
%K 运动目标轨道
%K 最近邻域搜索算法
%K 查询处理
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=CBCDFFE5AEBDB1BF682185B0946C4497&yid=A732AF04DDA03BB3&vid=BC12EA701C895178&iid=0B39A22176CE99FB&sid=E1D946F217E3B046&eid=5B5B75F4854B8331&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=32