Efficient Processing of Window Queries in The Pyramid Data Structure

Summary: Introduces the incomplete pyramid, a variant of the pyramid spatial index, and algorithms for exist/report window queries running in O(n log log T) time for an n×n window in a T×T space. Thus query cost scales almost linearly with window diameter n, not its area n^2. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h8491fab5416da44b
Venue: PODS
Year: 1990
Pagerank: 7.4986756e-05
Overall Rank: 3,243 | 78.20%
DOI: 10.1145/298514.298579

Incoming Non-self Citations Over Time

Authors

1. Walid G. Aref (University of Maryland)
2. Hanan Samet (University of Maryland)

BibTeX Citation

@inproceedings{aref_pods90,
        address = {New York, NY, USA},
        series = {{PODS} '90},
        title = {{Efficient Processing of Window Queries in The Pyramid Data Structure}},
        url = {https://dl.acm.org/doi/10.1145/298514.298579},
        doi = {10.1145/298514.298579},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Aref, Walid G. and Samet, Hanan},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,768	The New Casper: Query Processing for Location Services without Compromising Privacy	2006	VLDB	9.6873901e-05
3,279	Searchlight: Enabling Integrated Search and Exploration over Large Multidimensional Data	2015	VLDB	7.4620555e-05
7,215	Indexing Methods for Moving Object Databases: Games and Other Applications	2013	SIGMOD	5.5837763e-05
7,651	Kamel: A Scalable BERT-based System for Trajectory Imputation	2024	VLDB	5.4772833e-05
8,001	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	5.4092483e-05
10,870	KAFY: An Extensible and Scalable Transformers-Based System for Trajectory Data Analysis	2026	VLDB	4.9793485e-05
10,972	A Demonstration of KAFY: An Extensible and Scalable Transformers-Based System for Trajectory Data Analysis	2026	VLDB	4.9793485e-05
11,367	Polaris: An Interactive and Scalable Data Infrastructure for Polar Science	2025	VLDB	4.9793485e-05
11,404	A Demonstration of Polaris: An Interactive and Scalable Data Infrastructure for Polar Science	2025	VLDB	4.9793485e-05
12,222	A Demonstration of Sya: A Spatial Probabilistic Knowledge Base Construction System	2018	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,913	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS
2	9,941	Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads	2015	VLDB
3	11,489	Optimal (Multiway) Spatial Joins	2024	PODS
4	101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD
5	886	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD
6	3,658	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD
7	13,234	Algorithms for Querying by Spatial Structure	1998	VLDB
8	1,404	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS
9	9,273	Are Window Queries Representative For Arbitrary Range Queries?	1996	PODS
10	6,216	Window Query-Optimal Clustering of Spatial Objects	1995	PODS