TY - GEN
T1 - Efficient algorithms for historical continuous kNN query processing over moving object trajectories
AU - Li, Yunjun Gao
AU - Li, Chun
AU - Chen, Gencai
AU - Li, Qing
AU - Chen, Chun
PY - 2007/12/1
Y1 - 2007/12/1
N2 - In this paper, we investigate the problem of efficiently processing historical continuous k-Nearest Neighbor (HCANN) queries on R-tree-like structures storing historical information about moving object trajectories. The existing approaches for HCANN queries need high I/O (i.e., number of node accesses) and CPU costs since they follow depth-first fashion. Motivated by this observation, we present two algorithms, called HCp-ANN and HC T-ANN, which deal with the HCkNN retrieval with respect to the stationary query point and the moving query trajectory, respectively. The core of our solution employs best-first traversal paradigm and enables effective update strategies to maintain the nearest lists. Extensive performance studies with real and synthetic datasets show that the proposed algorithms outperform their competitors significantly in both efficiency and scalability.
AB - In this paper, we investigate the problem of efficiently processing historical continuous k-Nearest Neighbor (HCANN) queries on R-tree-like structures storing historical information about moving object trajectories. The existing approaches for HCANN queries need high I/O (i.e., number of node accesses) and CPU costs since they follow depth-first fashion. Motivated by this observation, we present two algorithms, called HCp-ANN and HC T-ANN, which deal with the HCkNN retrieval with respect to the stationary query point and the moving query trajectory, respectively. The core of our solution employs best-first traversal paradigm and enables effective update strategies to maintain the nearest lists. Extensive performance studies with real and synthetic datasets show that the proposed algorithms outperform their competitors significantly in both efficiency and scalability.
UR - http://www.scopus.com/inward/record.url?scp=38049008510&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
AN - SCOPUS:38049008510
SN - 9783540724834
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 188
EP - 199
BT - Advances in Data and Web Management - Joint 9th Asia-Pacific Web Conference, APWeb 2007 and 8th International Conference on Web-Age Information Management, WAIM 2007, Proceedings
T2 - Joint 9th Asia-Pacific Web Conference on Advances in Data and Web Management, APWeb 2007 and 8th International Conference on Web-Age Information Management, WAIM 2007
Y2 - 16 June 2007 through 18 June 2007
ER -