Bottom-up nearest neighbor search for R-trees

Moon Bae Song, Kwang Jin Park, Ki S. Kong, Sang-Geun Lee

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


A new nearest neighbor (NN) search algorithm for R-trees was proposed that performed in a bottom-up manner. The proposed approach starts at the leaf level and traverses to the Root node. The experimental results demonstrate that the proposed NN search algorithm outperforms existing NN search algorithms which are based on the R-tree including the existing I/O optimal algorithm. The conventional R-trees were required to be modified to make the bottom-up approach possible. Two new pruning heuristics were also proposed where the first is the remnant property and the second is safe MBR property. The possible usage of the safe MBRs is to be investigated without the additional hash structure. It was found that the proposed approach outperforms existing approaches such as DFS and BFS without respect to the number of nearest neighbors.

Original languageEnglish
Pages (from-to)78-85
Number of pages8
JournalInformation Processing Letters
Issue number2
Publication statusPublished - 2007 Jan 31


  • Bottom-up search
  • Databases
  • Nearest neighbor search
  • R-trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Bottom-up nearest neighbor search for R-trees'. Together they form a unique fingerprint.

Cite this