Are Window Queries Representative For Arbitrary Range Queries?

Summary: Gives closed-form expected-bucket-access formulas for intersection/containment/enclosure queries, expressing cost as a weighted sum of regions' total area, perimeter, and count. Weights depend on shape/query, and analysis largely confirms window (rectangular) queries are representative proxies for general range queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1084
Venue: PODS
Year: 1996
Pagerank: 5.3250598e-05
Overall Rank: 9,099 | 37.58%
DOI: 10.1145/237661.237704

Incoming Non-self Citations Over Time

Authors

1. Bernd-Uwe Pagel (University of Hagen)
2. Hans-Werner Six (University of Hagen)

BibTeX Citation

@inproceedings{pagel_pods96,
        address = {New York, NY, USA},
        series = {{PODS} '96},
        title = {{Are Window Queries Representative For Arbitrary Range Queries?}},
        url = {https://dl.acm.org/doi/10.1145/237661.237704},
        doi = {10.1145/237661.237704},
        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},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.5541724e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
650	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00015319951
936	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00013092484
1,370	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00010997795
1,877	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.5658249e-05
2,774	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	8.1372328e-05
6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.9806097e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,472	Transforming Range Queries To Equivalent Box Queries To Optimize Page Access	2010	VLDB
2	3,581	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD
3	1,512	On the Analysis of Indexing Schemes	1997	PODS
4	8,555	Efficient Aggregation over Objects with Extent	2002	PODS
5	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
6	96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD
7	3,668	Efficient Processing of Window Queries in The Pyramid Data Structure	1990	PODS
8	6,619	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS
9	6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
10	1,370	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS