On Efficient Aggregate Nearest Neighbor Query Processing in Road Networks

W.-W. Sun, C.-N. Chen, L. Zhu, Y.-J. Gao, Y.-N. Jing, Qing Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)

Abstract

© 2015, Springer Science+Business Media New York.An aggregate nearest neighbor (ANN) query returns a point of interest (POI) that minimizes an aggregate function for multiple query points. In this paper, we propose an efficient approach to tackle ANN queries in road networks. Our approach consists of two phases: searching phase and pruning phase. In particular, we first continuously compute the nearest neighbors (NNs) for each query point in some specific order to obtain the candidate POIs until all query points find a common POI. Second, we filter out the unqualified POIs based on the pruning strategy for a given aggregate function. The two-phase process is repeated until there remains only one candidate POI, and the remained one is returned as the final result. In addition, we discuss the partition strategies for query points and the approximate ANN query for the case where the number of query points is huge. Extensive experiments using real datasets demonstrate that our proposed approach outperforms its competitors significantly in most cases.
Original languageEnglish
Pages (from-to)781-798
Number of pages18
JournalJournal of Computer Science and Technology
Volume30
Issue number4
DOIs
Publication statusPublished - 22 Jul 2015
Externally publishedYes

Keywords

  • ANN query
  • road network
  • spatial database

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this