DBScholar

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
3023
Venue
SIGMOD
Year
1997
Pagerank
0.00022537944
Overall Rank
277 | 98.11%
DOI
10.1145/253260.253347

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{katayama_sigmod97,
        title = {{The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries}},
        author = {Katayama, Norio and Satoh, Shin'ichi},
        series = {{SIGMOD} '97},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/253260.253347},
        url = {https://dl.acm.org/doi/10.1145/253260.253347},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 36 of 36 citing papers.

Rank Citing Paper Year Venue Pagerank
21 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00056760516
46 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044853085
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
797 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013927251
864 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013522522
990 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00012796562
1,602 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.00010239526
1,778 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.7769047e-05
1,819 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.6810907e-05
1,862 MindReader: Querying databases through multiple examples 1998 VLDB 9.5951515e-05
2,886 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.9957585e-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,217 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.6314544e-05
3,252 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.5951443e-05
3,279 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.5711218e-05
4,657 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.5830079e-05
4,712 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 6.5506649e-05
5,118 Efficient Streaming Subgraph Isomorphism with Graph Neural Networks 2021 VLDB 6.3580186e-05
5,666 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 6.1285141e-05
6,887 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.7457967e-05
8,200 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.4677285e-05
8,848 A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems 2021 SIGMOD 5.3577837e-05
9,034 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 5.3274671e-05
9,261 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 5.2968259e-05
9,417 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.2740525e-05
10,454 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 5.093636e-05
11,738 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 5.093636e-05
11,974 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 5.093636e-05
12,472 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 5.093636e-05
12,794 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 5.093636e-05
12,818 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 5.093636e-05
12,863 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 5.093636e-05
12,864 An Extendible Hash for Multi-Precision Similarity Querying of Image Databases 2001 VLDB 5.093636e-05
12,940 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 5.093636e-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.0020210012
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00082404462
28 Nearest Neighbor Queries 1995 SIGMOD 0.00052102434
42 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00046170812
85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00035405879
353 The Query By Image Content (QBIC) System 1995 SIGMOD 0.00020370587
522 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00017133516
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 581 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD
2 21 Similarity Search in High Dimensions via Hashing 1999 VLDB
3 705 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB
4 592 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD
5 9,334 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB
6 8,655 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD
7 12,944 Algorithms for Querying by Spatial Structure 1998 VLDB
8 580 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB
9 1,384 Content-Based Image Indexing 1994 VLDB
10 1,778 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB