Database Paper Browser

Back to papers

The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation

Summary: A-tree introduces Virtual Bounding Rectangles (VBRs) to compactly approximate MBRs and data for high-dimensional similarity search. High fanout with MBR–VBR entries yields fast search and pruning; on real data up to 64D it saves ~77% page accesses vs SR-tree and ~78% vs VA-File. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
8677
Venue
VLDB
Year
2000
Pagerank
0.00010079134
Overall Rank
1,923 | 86.64%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
399 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00024359304
1,013 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014632051
3,182 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 7.4280768e-05
3,206 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3855924e-05
3,259 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3101573e-05
3,297 Approximate Embedding-Based Subsequence Matching of Time Series 2008 SIGMOD 7.2549403e-05
3,301 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.2450912e-05
3,574 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9520978e-05
3,906 Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems 2017 VLDB 6.6413008e-05
6,077 Query-Sensitive Embeddings 2005 SIGMOD 5.2203422e-05
8,127 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 4.5757206e-05
12,184 Effective Data Co-Reduction for Multimedia Similarity Search 2011 SIGMOD 4.1905499e-05
12,679 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032118946
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076824554
48 Nearest Neighbor Queries 1995 SIGMOD 0.0006954126
78 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056385781
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
301 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028396714
356 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00026091196
1,180 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00013455619
1,943 Multidimensional Access Methods: Trees Have Grown Everywhere 1997 VLDB 0.00010009557
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076824554
91 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00051785122
574 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.0001987713
675 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018304179
8,645 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4725847e-05
78 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056385781
9,769 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 4.2815042e-05
301 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028396714
9,288 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB 4.3589837e-05