DBScholar

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
8867
Venue
VLDB
Year
2000
Pagerank
9.7769047e-05
Overall Rank
1,778 | 87.81%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{sakurai_vldb00,
        title = {{The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation}},
        author = {Sakurai, Yasushi and Yoshikawa, Masatoshi and Uemura, Shunsuke and Kojima, Haruhiko},
        journal = {PVLDB},
        series = {{VLDB} '00},
        pages = {516},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
287 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022323585
705 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014829964
2,572 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4027322e-05
2,974 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.9083221e-05
2,979 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.8984588e-05
3,047 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.8155543e-05
3,363 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 7.4808966e-05
3,440 Approximate Embedding-Based Subsequence Matching of Time Series 2008 SIGMOD 7.4142918e-05
3,576 Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems 2017 VLDB 7.2936598e-05
5,909 Query-Sensitive Embeddings 2005 SIGMOD 6.0444989e-05
8,391 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 5.4356884e-05
12,371 Effective Data Co-Reduction for Multimedia Similarity Search 2011 SIGMOD 5.093636e-05
12,863 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 5.093636e-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.0020210012
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
21 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00056760516
28 Nearest Neighbor Queries 1995 SIGMOD 0.00052102434
46 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044853085
85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00035405879
277 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022537944
329 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00021068647
1,137 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00012027131
2,421 Multidimensional Access Methods: Trees Have Grown Everywhere 1997 VLDB 8.6033032e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 12,489 Worst-Case Efficient Range Search Indexing 2009 PODS
2 21 Similarity Search in High Dimensions via Hashing 1999 VLDB
3 56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB
4 592 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD
5 581 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD
6 8,655 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD
7 46 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB
8 9,887 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
9 277 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD
10 9,334 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB