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: 1000
Venue: PODS
Year: 1993
Pagerank: 0.00010997795
Overall Rank: 1,370 | 90.61%
DOI: 10.1145/153850.153878

Incoming Non-self Citations Over Time

Authors

1. Bernd-Uwe Pagel (FernUniversität in Hagen (University of Hagen))
2. Hans-Werner Six (FernUniversität in Hagen (University of Hagen))
3. Heinrich Toben (FernUniversität in Hagen (University of Hagen))
4. Peter Widmayer (ETH Zurich)

BibTeX Citation

@inproceedings{pagel_pods93,
        address = {New York, NY, USA},
        series = {{PODS} '93},
        title = {{Towards an Analysis of Range Query Performance in Spatial Data Structures}},
        url = {https://dl.acm.org/doi/10.1145/153850.153878},
        doi = {10.1145/153850.153878},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Pagel, Bernd-Uwe and Six, Hans-Werner and Toben, Heinrich and Widmayer, Peter},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
202	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00025454884
365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00020041735
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
957	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012962576
1,053	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012401532
1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010625076
1,512	On the Analysis of Indexing Schemes	1997	PODS	0.00010536001
2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.9083221e-05
3,394	Prediction and Indexing of Moving Objects with Unknown Motion Patterns	2004	SIGMOD	7.4500025e-05
6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.9806097e-05
6,756	On Efficiently Searching Trajectories and Archival Data for Historical Similarities	2008	VLDB	5.7829178e-05
7,225	HINT: A Hierarchical Index for Intervals in Main Memory	2022	SIGMOD	5.6673083e-05
7,879	Authenticated Online Data Integration Services	2015	SIGMOD	5.5245691e-05
7,939	A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing	2005	VLDB	5.5181056e-05
9,099	Are Window Queries Representative For Arbitrary Range Queries?	1996	PODS	5.3250598e-05
9,417	Similarity Query Processing Using Disk Arrays	1998	SIGMOD	5.2740525e-05

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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
936	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00013092484
1,032	The BANG file: a new kind of grid file	1987	SIGMOD	0.00012530965
1,877	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.5658249e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,750	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS
2	12,302	Space-Efficient Range Reporting for Categorical Data	2012	PODS
3	2,443	Independent Range Sampling	2014	PODS
4	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
5	1,373	A Model for the Prediction of R-tree Performance	1996	PODS
6	96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD
7	6,619	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS
8	3,668	Efficient Processing of Window Queries in The Pyramid Data Structure	1990	PODS
9	6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
10	9,099	Are Window Queries Representative For Arbitrary Range Queries?	1996	PODS