Database Paper Browser

Back to papers

The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries

Summary: Introduces SR-tree (Sphere/Rectangle-tree) for high-dimensional NN queries by combining bounding spheres with bounding rectangles. Intersecting sphere and rectangle yields tighter, more disjoint regions than SS-tree, boosting NN search for high-dim/non-uniform data and beating SS-tree and R*-tree. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
2961
Venue
SIGMOD
Year
1997
Pagerank
0.00028994728
Overall Rank
284 | 98.03%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 36 of 36 citing papers.

Rank Citing Paper Year Venue Pagerank
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076637636
79 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056242144
400 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.0002427237
648 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 0.00018666267
825 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00016228517
931 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00015238406
1,010 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014652858
1,229 SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013157271
1,608 MindReader: Querying databases through multiple examples 1998 VLDB 0.00011151257
1,806 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.00010490769
1,925 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010073407
3,018 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.7002798e-05
3,255 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3160522e-05
3,275 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.2897998e-05
3,300 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.2516103e-05
3,338 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.2040692e-05
4,090 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.4577834e-05
4,243 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 6.32976e-05
5,521 Efficient Streaming Subgraph Isomorphism with Graph Neural Networks 2021 VLDB 5.4614637e-05
5,569 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 5.4290942e-05
6,778 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 4.9284526e-05
8,359 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 4.5372925e-05
8,693 A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems 2021 SIGMOD 4.466142e-05
8,763 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 4.456315e-05
8,895 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 4.427268e-05
9,121 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 4.3922853e-05
9,143 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 4.3850454e-05
10,165 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1945683e-05
11,541 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 4.1945683e-05
11,769 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 4.1945683e-05
12,277 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.1945683e-05
12,601 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.1945683e-05
12,625 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.1945683e-05
12,670 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 4.1945683e-05
12,671 An Extendible Hash for Multi-Precision Similarity Querying of Image Databases 2001 VLDB 4.1945683e-05
12,747 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
5 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0018397217
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538
47 Nearest Neighbor Queries 1995 SIGMOD 0.0007015885
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.0004429571
330 The Query By Image Content (QBIC) System 1995 SIGMOD 0.00027229588
478 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.0002222104
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076637636
682 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018201541
1,010 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014652858
575 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00019882723
8,647 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4768766e-05
9,283 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB 4.3631652e-05
12,751 Algorithms for Querying by Spatial Structure 1998 VLDB 4.1945683e-05
867 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00015792021
1,293 Content-Based Image Indexing 1994 VLDB 0.00012783639
1,925 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010073407