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.00022308048
Overall Rank
279 | 98.13%
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.00057568153
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.0004503446
280 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.0002230467
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015149775
811 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013745617
886 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.0001325914
927 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013025904
1,634 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.0001001862
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6235776e-05
1,856 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.4938262e-05
1,912 MindReader: Querying databases through multiple examples 1998 VLDB 9.3904326e-05
2,939 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.8340314e-05
2,969 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.8000797e-05
3,016 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.7483267e-05
3,034 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.7330662e-05
3,253 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.4900624e-05
3,302 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.4433382e-05
4,050 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 6.8298981e-05
4,728 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.4473669e-05
5,218 Efficient Streaming Subgraph Isomorphism with Graph Neural Networks 2021 VLDB 6.2231041e-05
5,796 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 5.9910143e-05
7,023 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.6186604e-05
8,369 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3450708e-05
8,786 A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems 2021 SIGMOD 5.2768554e-05
9,204 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 5.2080128e-05
9,435 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 5.1780501e-05
9,597 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1557462e-05
10,326 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 5.0346745e-05
12,041 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 4.9793485e-05
12,272 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 4.9793485e-05
12,763 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.9793485e-05
13,084 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.9793485e-05
13,108 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.9793485e-05
13,153 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 4.9793485e-05
13,154 An Extendible Hash for Multi-Precision Similarity Querying of Image Databases 2001 VLDB 4.9793485e-05
13,230 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.9793485e-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.001992968
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011405675
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0008122792
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051312804
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045337853
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034860244
353 The Query By Image Content (QBIC) System 1995 SIGMOD 0.00020222998
527 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016880616
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 650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB
4 9,400 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB
5 8,818 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,234 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,407 Content-Based Image Indexing 1994 VLDB
10 1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB