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: 8676
Venue: VLDB
Year: 2000
Pagerank: 0.00010073407
Overall Rank: 1,925 | 86.61%
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
400	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002427237
1,010	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014652858
3,199	Similarity Evaluation on Tree-structured Data	2005	SIGMOD	7.3927291e-05
3,225	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.3463484e-05
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
3,294	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD	7.2619257e-05
3,300	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.2516103e-05
3,579	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9502303e-05
3,912	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	6.6354964e-05
6,082	Query-Sensitive Embeddings	2005	SIGMOD	5.2205711e-05
8,123	Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation	2001	VLDB	4.5801104e-05
12,176	Effective Data Co-Reduction for Multimedia Similarity Search	2011	SIGMOD	4.1945683e-05
12,670	Fast Evaluation Techniques for Complex Similarity Queries	2001	VLDB	4.1945683e-05

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.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
47	Nearest Neighbor Queries	1995	SIGMOD	0.0007015885
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.0004429571
284	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028994728
354	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026137988
1,183	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00013455596
1,945	Multidimensional Access Methods: Trees Have Grown Everywhere	1997	VLDB	0.00010001003

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,294	Worst-Case Efficient Range Search Indexing	2009	PODS	4.1945683e-05
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
575	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00019882723
682	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018201541
8,647	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	4.4768766e-05
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
9,767	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2856106e-05
284	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028994728
9,283	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB	4.3631652e-05