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.00022250557
Overall Rank
282 | 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.00057610161
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044967652
281 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022262975
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015142453
812 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013710393
889 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013212387
925 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013026835
1,642 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 9.9812004e-05
1,805 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.5936926e-05
1,867 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.4581343e-05
1,921 MindReader: Querying databases through multiple examples 1998 VLDB 9.3580039e-05
2,952 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.8061763e-05
2,968 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.7879589e-05
3,025 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.7214661e-05
3,044 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.7045269e-05
3,267 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.46539e-05
3,315 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.4155055e-05
4,077 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 6.8040917e-05
4,749 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.423839e-05
5,224 Efficient Streaming Subgraph Isomorphism with Graph Neural Networks 2021 VLDB 6.2100595e-05
5,814 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 5.9684385e-05
7,045 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.5975731e-05
8,391 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3248747e-05
8,813 A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems 2021 SIGMOD 5.2570736e-05
9,235 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 5.1884043e-05
9,465 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 5.1590473e-05
9,631 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1362663e-05
10,359 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 5.0156513e-05
12,091 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 4.9605343e-05
12,321 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 4.9605343e-05
12,812 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.9605343e-05
13,131 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.9605343e-05
13,155 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.9605343e-05
13,200 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 4.9605343e-05
13,201 An Extendible Hash for Multi-Precision Similarity Querying of Image Databases 2001 VLDB 4.9605343e-05
13,277 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.9605343e-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.0019892478
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011386412
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00081207565
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051134355
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045231517
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034749222
350 The Query By Image Content (QBIC) System 1995 SIGMOD 0.0002018411
530 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016832286
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 578 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD
2 20 Similarity Search in High Dimensions via Hashing 1999 VLDB
3 650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB
4 9,434 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB
5 598 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD
6 8,844 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD
7 13,281 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,413 Content-Based Image Indexing 1994 VLDB
10 1,805 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB