The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation
Published 10 September 2000
Yasushi Sakurai, Masatoshi Yoshikawa, Shunsuke Uemura, Haruhiko Kojima
Citations206
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A novel index structure, A-tree (Approximation tree), for similarity search of high-dimensional data, which outperforms the SR-tree and the VA-File in all range of dimensionality up to 64 dimension, which is the highest dimension in the authors' experiments.
Abstract
We propose a novel index structure, A-tree (Approximation tree), for similarity search of high-dimensional data. The basic idea of the A-tree is the introduction ofVirtual BoundingRectangl # (VBRs), which contain and approximate MBRs and data objects. VBRs can be represented rathercompactl , and thus affect the tree configuration both quantitativel and qualzR%#z el .Firstl , since tree nodes caninstal lsta number of entries of VBRs, fanout of nodes becomes lomes thuslR]# to fast search. More importantl , we have a free hand in arranging MBRs and VBRs in tree nodes. In the A-trees, nodes contain entries of an MBRand its chil8z8 VBRs. Therefore, by fetching a node of an A-tree, we can obtain the information of exact position of a parent MBR and approximate position of its chil*8#R We have performed experiments using both synthetic andreal data sets. For thereal data sets, the A-tree outperforms the SR-tree and the VA-Fil in al range ofdimensional...
Keywords
Computer Science
R-trees
6,543 Citations1984Antonin Guttman
A dynamic index structure called an R-tree is described which meets this need, and algorithms for searching and updating it are given and it is concluded that it is useful for current database systems in spatial applications.
The R*-tree: an efficient and robust access method for points and rectangles
4,176 Citations1990Norbert Beckmann, Hans‐Peter Kriegel +2 more
The R*-tree is designed which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory which clearly outperforms the existing R-tree variants.
Similarity Search in High Dimensions via Hashing
3,108 Citations1999Aristides Gionis, Piotr Indyk +1 more
Experimental results indicate that the novel scheme for approximate similarity search based on hashing scales well even for a relatively large number of dimensions, and provides experimental evidence that the method gives improvement in running time over other methods for searching in highdimensional spaces based on hierarchical tree decomposition.
International Journal of Computer VisionVisual learning and recognition of 3-d objects from appearance
1,891 Citations1995Hiroshi Murase, Shree K. Nayar
A near real-time recognition system with 20 complex objects in the database has been developed and a compact representation of object appearance is proposed that is parametrized by pose and illumination.
View-based and modular eigenspaces for face recognition
1,813 Citations1994Pentland, Moghaddam +1 more
A modular eigenspace description technique is used which incorporates salient features such as the eyes, nose and mouth, in an eigenfeature layer, which yields higher recognition rates as well as a more robust framework for face recognition.
ACM Computing SurveysMultidimensional access methods
1,591 Citations1998Volker Gaede, Oliver Günther
The class of point access methods, which are used to search sets of points in two or more dimensions, are presented and a discussion of theoretical and experimental results concerning the relative performance of various approaches are discussed.
A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces
1,513 Citations1998Roger Weber, Hans‐Jörg Schek +1 more
It is shown formally that partitioning and clustering techniques for similarity search in HDVSs exhibit linear complexity at high dimensionality, and that existing methods are outperformed on average by a simple sequential scan if the number of dimensions exceeds around 10.
Nearest neighbor queries
1,408 Citations1995Nick Roussopoulos, Stephen Kelley +1 more
This paper presents an efficient branch-and-bound R-tree traversal algorithm to find the nearest neighbor object to a point, and then generalizes it to finding the k nearest neighbors.
Elsevier eBooksThe X-tree: An Index Structure for High-Dimensional Data Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.
1,127 Citations2002Stefan Berchtold, Daniel A. Keim +1 more
A new organization of the directory is introduced which uses a split algorithm minimizing overlap and additionally utilizes the concept of supernodes to keep the directory as hierarchical as possible, and at the same time to avoid splits in the directory that would result in high overlap.
The SR-tree
819 Citations1997Norio Katayama, Shin’ichi Satoh
This paper proposes a new index structure called the SR-tree (Sphere/Rectangle-tree) which integrates bounding spheres and bounding rectangles which enhances the performance on nearest neighbor queries especially for high-dimensional and non-uniform data which can be practical in actual image/video similarity indexing.
Similarity indexing with the SS-tree
639 Citations2002David A. White, Ramesh Jain
This work defines the problem as "similarity indexing" and describes the fundamental types of "similarity queries" that should be supported and proposes a new dynamic structure for similarity indexing called the similarity search tree or SS-tree.
Digital Repository at the University of Maryland (University of Maryland College Park)Hilbert R-tree: An Improved R-tree using Fractals
536 Citations2018Ibrahim Kamel, Christos Faloutsos
A new Rtree structure that outperforms all the older ones by proposing an ordering on the R-tree nodes, and using the so-called ‘2D-c’ method, which sorts rectangles according to the Hilbert value of the center of the rectangles.
A cost model for nearest neighbor search in high-dimensional data space
374 Citations1997Stefan Berchtold, Christian Böhm +2 more
A new cost model for nearest neighbor search in high-dimensional data space is developed which takes boundary effects into account and therefore also works in high dimensions and is applicable to different data distributions and index structures.
Lecture notes in computer scienceRanking in spatial databases
355 Citations1995Gı́sli R. Hjaltason, Hanan Samet
An algorithm for ranking spatial objects according to increasing distance from a query object is introduced and analyzed, which is well suited for k nearest neighbor queries, and has the property that k needs not be fixed in advance.
ComputerIntelligent access to digital video: Informedia project
344 Citations1996Howard D. Wactlar, Takeo Kanade +2 more
Carnegie Mellon's Informedia Digital Video Library project will establish a large, on-line digital video library featuring full-content and knowledge-based search and retrieval, and focused the work on two corpuses.
Independent quantization: an index compression technique for high-dimensional data spaces
289 Citations2002Stefan Berchtold, Christian Böhm +3 more
This work develops a compressed index, called the IQ-tree, with a three-level structure, and develops a cost model and an optimization algorithm based on this cost model that permits an independent determination of the degree of compression for each second level page to minimize expected query cost.
Viewbased and modular eigenspaces for face recognition
200 Citations1994Alex Pentland
Very Large Data BasesMultidimensional Access Methods: Trees Have Grown Everywhere
36 Citations1997Timos Sellis, Nick Roussopoulos +1 more
This paper is a survey of work and issues on multidimensional search trees, providing a classification of such methods, the related algorithms, the performance analysis efforts, and the future research directions are outlined.