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.00011752931
Overall Rank: 1,476 | 89.75%
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.00031093647
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021385343
628	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018957327
1,055	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00014391376
1,240	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013090678
1,485	On the Analysis of Indexing Schemes	1997	PODS	0.00011698762
1,568	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.0001131667
2,893	Prediction and Indexing of Moving Objects with Unknown Motion Patterns	2004	SIGMOD	7.9547451e-05
3,259	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3101573e-05
6,073	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.2215154e-05
6,575	On Efficiently Searching Trajectories and Archival Data for Historical Similarities	2008	VLDB	4.9993797e-05
7,518	A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing	2005	VLDB	4.7135369e-05
7,784	Authenticated Online Data Integration Services	2015	SIGMOD	4.6472451e-05
7,916	HINT: A Hierarchical Index for Intervals in Main Memory	2022	SIGMOD	4.6133471e-05
8,894	Are Window Queries Representative For Arbitrary Range Queries?	1996	PODS	4.4232095e-05
9,173	Similarity Query Processing Using Disk Arrays	1998	SIGMOD	4.3807204e-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.0032118946
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
833	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016085787
1,009	The BANG file: a new kind of grid file	1987	SIGMOD	0.00014658958
2,144	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4375327e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,113	Space-Efficient Range Reporting for Categorical Data	2012	PODS	4.1905499e-05
8,761	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	4.4520434e-05
2,207	Independent Range Sampling	2014	PODS	9.2896559e-05
1,183	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013444058
1,519	A Model for the Prediction of R-tree Performance	1996	PODS	0.00011535609
75	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057450043
6,512	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS	5.0273291e-05
3,619	Efficient Processing of Window Queries in The Pyramid Data Structure	1990	PODS	6.9061356e-05
6,073	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.2215154e-05
8,894	Are Window Queries Representative For Arbitrary Range Queries?	1996	PODS	4.4232095e-05