Efficient algorithms for historical continuous kNN query processing over moving object trajectories

Yunjun Gao Li, Chun Li, Gencai Chen, Qing Li, Chun Chen

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

5 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationAdvances 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
Pages188-199
Number of pages12
Publication statusPublished - 1 Dec 2007
Externally publishedYes
EventJoint 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 - Huang Shan, China
Duration: 16 Jun 200718 Jun 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4505 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceJoint 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
CountryChina
CityHuang Shan
Period16/06/0718/06/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this