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
h59bb83798fb08ad2
Venue
SIGMOD
Year
1997
Pagerank
0.00022303081
Overall Rank
281 | 98.12%
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
20 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.0005758001
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00045027197
278 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022310642
648 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015156941
812 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013744009
886 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013253709
927 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013028642
1,634 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.00010013999
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6212318e-05
1,858 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.4893333e-05
1,913 MindReader: Querying databases through multiple examples 1998 VLDB 9.386654e-05
2,940 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.8306095e-05
2,955 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.8111585e-05
3,017 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.7455245e-05
3,035 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.7296096e-05
3,254 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.487573e-05
3,304 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.4398851e-05
4,051 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 6.8266649e-05
4,730 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.4444432e-05
5,223 Efficient Streaming Subgraph Isomorphism with Graph Neural Networks 2021 VLDB 6.2201582e-05
5,798 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 5.9882057e-05
7,024 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.6160027e-05
8,374 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3425405e-05
8,794 A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems 2021 SIGMOD 5.2745144e-05
9,213 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 5.2056173e-05
9,441 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 5.175852e-05
9,605 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1533056e-05
10,333 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 5.0322912e-05
12,047 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 4.9769913e-05
12,278 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 4.9769913e-05
12,769 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.9769913e-05
13,090 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.9769913e-05
13,114 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.9769913e-05
13,159 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 4.9769913e-05
13,160 An Extendible Hash for Multi-Precision Similarity Querying of Image Databases 2001 VLDB 4.9769913e-05
13,236 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.9769913e-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.0019923528
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011402175
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00081200096
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051292389
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045319457
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034847854
352 The Query By Image Content (QBIC) System 1995 SIGMOD 0.00020218955
527 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016874202
Previous Page 1 / 1 Next

Semantically Similar Papers

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