Range nearest-neighbor query

Haibo Hu, Dik Lun Lee

Research output: Journal article publicationJournal articleAcademic researchpeer-review

98 Citations (Scopus)

Abstract

A range nearest-neighbor (RNN) query retrieves the nearest neighbor (NN) for every point in a range. It is a natural generalization of point and continuous nearest-neighbor queries and has many applications. In this paper, we consider the ranges as (hyper)rectangles and propose efficient in-memory processing and secondary memory pruning techniques for RNN queries in both 2D and high-dimensional spaces. These techniques are generalized for kRNN queries, which return the k nearest neighbors for every point in the range. In addition, we devise an auxiliary solution-based index EXO-tree to speed up any type of NN query. EXO-tree is orthogonal to any existing NN processing algorithm and, thus, can be transparently integrated. An extensive empirical study was conducted to evaluate the CPU and I/O performance of these techniques, and the study showed that they are efficient and robust under various data sets, query ranges, numbers of nearest neighbors, dimensions, and cache sizes.
Original languageEnglish
Pages (from-to)78-91
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume18
Issue number1
DOIs
Publication statusPublished - 1 Jan 2006
Externally publishedYes

Keywords

  • Nearest-neighbor search
  • Spatial database

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this