Rectangle-Efficient Aggregation in Spatial Data Streams

Summary: Near-optimal streaming sketches for multidimensional axis-aligned rectangles: estimate k-th frequency moments of point-containment counts, answer point-stabbing queries, and find heavy-hitters. Also gives the first streaming algorithm for Klee's measure (union volume) beyond 1D. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h7828ee97c3176bb5
Venue: PODS
Year: 2012
Pagerank: 6.3763323e-05
Overall Rank: 4,865 | 67.30%
DOI: 10.1145/2213556.2213595

Incoming Non-self Citations Over Time

Authors

1. Srikanta Tirthapura (Iowa State University)
2. David P. Woodruff (IBM)

BibTeX Citation

@inproceedings{tirthapura_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Rectangle-Efficient Aggregation in Spatial Data Streams}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213595},
        doi = {10.1145/2213556.2213595},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Tirthapura, Srikanta and Woodruff, David P.},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,837	Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size	2022	PODS	4.9793485e-05
11,938	Model Counting meets F0 Estimation	2021	PODS	4.9793485e-05
11,947	Estimating the Size of Union of Sets in Streaming Models	2021	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021311793
664	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00014995058
742	Dynamic Multidimensional Histograms	2002	SIGMOD	0.0001431602
3,758	Approximation Techniques for Spatial Data	2004	SIGMOD	7.0437238e-05
4,640	Exact and Approximate Aggregation in Constraint Query Languages	1999	PODS	6.4903073e-05
6,295	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS	5.8202752e-05
6,865	Fast Range-Summable Random Variables for Efficient Aggregate Estimation	2006	SIGMOD	5.6603286e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,379	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB
2	6,748	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS
3	8,579	Adaptive Sampling for Geometric Problems over Data Streams	2004	PODS
4	3,758	Approximation Techniques for Spatial Data	2004	SIGMOD
5	12,329	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD
6	3,818	Spatial Online Sampling and Aggregation	2016	VLDB
7	6,216	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
8	6,295	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS
9	11,489	Optimal (Multiway) Spatial Joins	2024	PODS
10	8,722	Efficient Aggregation over Objects with Extent	2002	PODS