Database Paper Browser

Back to papers

Towards an Analysis of Range Query Performance in Spatial Data Structures

Summary: Derives probabilistic models for four user-defined window-query classes to predict expected bucket accesses for points and non-point objects. Provides data-structure–agnostic formulas (fixed relative window area, uniform window centers) to analytically compare spatial organizations' range-query efficiency. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1001
Venue
PODS
Year
1993
Pagerank
0.00011749057
Overall Rank
1,479 | 89.72%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
242 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00031110894
512 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00021380733
631 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD 0.00018935493
1,067 The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries 2003 VLDB 0.00014327945
1,241 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00013097578
1,488 On the Analysis of Indexing Schemes 1997 PODS 0.00011699446
1,586 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00011250856
2,889 Prediction and Indexing of Moving Objects with Unknown Motion Patterns 2004 SIGMOD 7.9587247e-05
3,255 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3160522e-05
6,076 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.223696e-05
6,577 On Efficiently Searching Trajectories and Archival Data for Historical Similarities 2008 VLDB 5.0042166e-05
7,519 A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing 2005 VLDB 4.7180617e-05
7,784 Authenticated Online Data Integration Services 2015 SIGMOD 4.6517065e-05
7,915 HINT: A Hierarchical Index for Intervals in Main Memory 2022 SIGMOD 4.617775e-05
8,894 Are Window Queries Representative For Arbitrary Range Queries? 1996 PODS 4.4274507e-05
9,143 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 4.3850454e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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.0032169493
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
838 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00016088938
1,008 The BANG file: a new kind of grid file 1987 SIGMOD 0.00014666726
2,144 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.4416732e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,546 I/O-Efficient Planar Range Skyline and Attrition Priority Queues 2013 PODS 4.4937074e-05
12,105 Space-Efficient Range Reporting for Categorical Data 2012 PODS 4.1945683e-05
2,203 Independent Range Sampling 2014 PODS 9.2981095e-05
1,182 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013455963
1,528 A Model for the Prediction of R-tree Performance 1996 PODS 0.00011497734
76 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00057303551
6,516 (Almost) Optimal Parallel Block Access for Range Queries 2000 PODS 5.0321577e-05
3,615 Efficient Processing of Window Queries in The Pyramid Data Structure 1990 PODS 6.9127616e-05
6,076 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.223696e-05
8,894 Are Window Queries Representative For Arbitrary Range Queries? 1996 PODS 4.4274507e-05