Window Query-Optimal Clustering of Spatial Objects

Summary: Defines static window-query optimal clustering: partition known spatial data into capacity-cb buckets to minimize expected bucket accesses, yielding a lower bound for spatial indexes. Poly-time for cb=2, NP-hard for cb≥3; simulated annealing shows dynamic structures and packed R-tree ≈20% worse than optimum. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1049
Venue: PODS
Year: 1995
Pagerank: 5.9806097e-05
Overall Rank: 6,089 | 58.23%
DOI: 10.1145/212433.212458

Incoming Non-self Citations Over Time

Authors

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

BibTeX Citation

@inproceedings{pagel_pods95,
        address = {New York, NY, USA},
        series = {{PODS} '95},
        title = {{Window Query-Optimal Clustering of Spatial Objects}},
        url = {https://dl.acm.org/doi/10.1145/212433.212458},
        doi = {10.1145/212433.212458},
        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 Winter, Mario},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,373	A Model for the Prediction of R-tree Performance	1996	PODS	0.0001098638
2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.9083221e-05
8,689	Adaptive Index Structures	2002	VLDB	5.3843737e-05
9,099	Are Window Queries Representative For Arbitrary Range Queries?	1996	PODS	5.3250598e-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
479	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017789732
650	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00015319951
698	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00014879675
839	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00013692785
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
5,007	A Decomposition-Based Simulated Annealing Technique for Data Clustering	1994	PODS	6.4032846e-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	9,234	On Optimal Node Splitting for R-trees	1998	VLDB
3	12,944	Algorithms for Querying by Spatial Structure	1998	VLDB
4	5,787	On the Optimality of Clustering Properties of Space Filling Curves	2012	PODS
5	11,141	Optimal (Multiway) Spatial Joins	2024	PODS
6	3,668	Efficient Processing of Window Queries in The Pyramid Data Structure	1990	PODS
7	3,581	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD
8	8,796	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB
9	9,099	Are Window Queries Representative For Arbitrary Range Queries?	1996	PODS
10	1,370	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS