DBScholar

Back to papers

Selectivity Estimation in Spatial Databases

Summary: Proposes selectivity estimation for 2D spatial queries using BSP-based partitioning and histograms to handle spatial skew. Introduces Min-Skew BSP partitioning, an efficient, compact method delivering accurate estimates across queries, outperforming sampling and parametric baselines on synthetic and TIGER data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
ha521ac1eb5c43a2e
Venue
SIGMOD
Year
1999
Pagerank
8.9031141e-05
Overall Rank
2,176 | 85.42%
DOI
10.1145/304182.304184

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{acharya_sigmod99,
        title = {{Selectivity Estimation in Spatial Databases}},
        author = {Acharya, Swarup and Poosala, Viswanath and Ramaswamy, Sridhar},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304184},
        url = {https://dl.acm.org/doi/10.1145/304182.304184},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029532435
254 The History of Histograms (abridged) 2003 VLDB 0.00022999992
868 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00013336675
3,646 Location-based Spatial Queries 2003 SIGMOD 7.1177166e-05
3,765 Approximation Techniques for Spatial Data 2004 SIGMOD 7.0178846e-05
4,269 Selectivity Estimation for Spatio-Temporal Queries to Moving Objects 2002 SIGMOD 6.6778228e-05
4,480 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 6.566036e-05
7,542 Comparing Synopsis Techniques for Approximate Spatial Data Analysis 2019 VLDB 5.4821664e-05
8,834 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 5.2524856e-05
8,883 Adaptive Index Structures 2002 VLDB 5.2436823e-05
9,859 Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects 2010 SIGMOD 5.1064323e-05
10,032 Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets 2003 VLDB 5.080531e-05
12,598 Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects 2013 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0023948467
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
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047770864
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047654188
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045231517
78 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036725074
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036394222
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033847446
234 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00023726296
668 The Sequoia 2000 Storage Benchmark 1993 SIGMOD 0.00014936842
747 Client-Server Paradise 1994 VLDB 0.00014259869
1,412 A Model for the Prediction of R-tree Performance 1996 PODS 0.00010725178
2,838 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.9401525e-05
2,966 The Size of Projections of Relations Satisfying a Functional Dependency 1982 VLDB 7.7893283e-05
3,080 The Montage Extensible DataBlade Architecture 1994 SIGMOD 7.6526762e-05
4,563 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.5201574e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 287 Selectivity Estimation using Probabilistic Models 2001 SIGMOD
2 12,598 Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects 2013 VLDB
3 6,924 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB
4 7,542 Comparing Synopsis Techniques for Approximate Spatial Data Analysis 2019 VLDB
5 2,838 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB
6 4,956 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD
7 960 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB
8 9,859 Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects 2010 SIGMOD
9 4,269 Selectivity Estimation for Spatio-Temporal Queries to Moving Objects 2002 SIGMOD
10 3,765 Approximation Techniques for Spatial Data 2004 SIGMOD