Enhanced nearest neighbour search on the R-tree

1 September 1998

journal article
Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record

Vol. 27 (3) , 16-21
https://doi.org/10.1145/290593.290596

Abstract

Multimedia databases usually deal with huge amounts of data and it is necessary to have an indexing structure such that efficient retrieval of data can be provided. R-Tree with its variations, is a commonly cited indexing method. In this paper we propose an improved nearest neighbor search algorithm on the R-tree and its variants. The improvement lies in the removal of two hueristics that have been used in previous R*-tree work, which we prove cannot improve on the pruning power during a search.

Keywords

This publication has 10 references indexed in Scilit:

A cost model for nearest neighbor search in high-dimensional data space
Published by Association for Computing Machinery (ACM) ,1997
Fast parallel similarity search in multimedia databases
Published by Association for Computing Machinery (ACM) ,1997
Chabot: retrieval from a relational database of images
Computer, 1995
Query by image and video content: the QBIC system
Computer, 1995
FastMap
Published by Association for Computing Machinery (ACM) ,1995
Nearest neighbor queries
Published by Association for Computing Machinery (ACM) ,1995
Heterogeneous multimedia reasoning
Computer, 1995
The TV-tree: An index structure for high-dimensional data
The VLDB Journal, 1994
The R*-tree: an efficient and robust access method for points and rectangles
Published by Association for Computing Machinery (ACM) ,1990
An Algorithm for Finding Best Matches in Logarithmic Expected Time
ACM Transactions on Mathematical Software, 1977