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
2962
Venue
SIGMOD
Year
1997
Pagerank
0.00028396714
Overall Rank
301 | 97.91%
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.00076824554
78 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056385781
399 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00024359304
821 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00016232579
929 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.0001523035
1,013 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014632051
1,225 SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013182109
1,613 MindReader: Querying databases through multiple examples 1998 VLDB 0.00011141103
1,802 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.0001048177
1,923 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010079134
2,020 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.7766925e-05
3,018 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.6995792e-05
3,259 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3101573e-05
3,278 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.2858181e-05
3,301 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.2450912e-05
3,340 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.1987694e-05
4,096 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.4506806e-05
4,230 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 6.3337893e-05
5,530 Efficient Streaming Subgraph Isomorphism with Graph Neural Networks 2021 VLDB 5.4562393e-05
5,577 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 5.423881e-05
6,778 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 4.9237313e-05
8,354 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 4.5329424e-05
8,687 A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems 2021 SIGMOD 4.4621895e-05
8,759 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 4.4520434e-05
8,895 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 4.423024e-05
9,119 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 4.3881453e-05
9,173 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 4.3807204e-05
10,165 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1905499e-05
11,545 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 4.1905499e-05
11,777 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 4.1905499e-05
12,285 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.1905499e-05
12,610 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.1905499e-05
12,634 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.1905499e-05
12,679 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 4.1905499e-05
12,680 An Extendible Hash for Multi-Precision Similarity Querying of Image Databases 2001 VLDB 4.1905499e-05
12,756 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.1905499e-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.0032118946
5 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0018380955
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083300888
48 Nearest Neighbor Queries 1995 SIGMOD 0.0006954126
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
331 The Query By Image Content (QBIC) System 1995 SIGMOD 0.00027199905
479 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00022182486
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.00076824554
675 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018304179
1,013 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014632051
9,288 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB 4.3589837e-05
8,645 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4725847e-05
574 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.0001987713
12,760 Algorithms for Querying by Spatial Structure 1998 VLDB 4.1905499e-05
858 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00015833075
1,290 Content-Based Image Indexing 1994 VLDB 0.00012774326
1,923 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010079134