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: hef8d5922c6e4e191
Venue: PODS
Year: 1995
Pagerank: 5.847583e-05
Overall Rank: 6,216 | 58.21%
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,405	A Model for the Prediction of R-tree Performance	1996	PODS	0.0001076417
3,034	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.7330662e-05
8,856	Adaptive Index Structures	2002	VLDB	5.2635701e-05
9,273	Are Window Queries Representative For Arbitrary Range Queries?	1996	PODS	5.2055814e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017462723
665	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00014990574
708	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00014629998
859	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00013418999
1,404	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00010767648
1,903	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4032472e-05
5,094	A Decomposition-Based Simulated Annealing Technique for Data Clustering	1994	PODS	6.2775013e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,913	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS
2	13,234	Algorithms for Querying by Spatial Structure	1998	VLDB
3	9,406	On Optimal Node Splitting for R-trees	1998	VLDB
4	5,904	On the Optimality of Clustering Properties of Space Filling Curves	2012	PODS
5	11,489	Optimal (Multiway) Spatial Joins	2024	PODS
6	3,243	Efficient Processing of Window Queries in The Pyramid Data Structure	1990	PODS
7	3,658	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD
8	8,960	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB
9	9,273	Are Window Queries Representative For Arbitrary Range Queries?	1996	PODS
10	1,404	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS