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: 1584
Venue: PODS
Year: 2012
Pagerank: 6.5226838e-05
Overall Rank: 4,755 | 67.38%
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,528	Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size	2022	PODS	5.093636e-05
11,631	Model Counting meets F0 Estimation	2021	PODS	5.093636e-05
11,640	Estimating the Size of Union of Sets in Streaming Models	2021	PODS	5.093636e-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
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
648	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00015324657
723	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014620977
3,703	Approximation Techniques for Spatial Data	2004	SIGMOD	7.1829776e-05
4,543	Exact and Approximate Aggregation in Constraint Query Languages	1999	PODS	6.6388258e-05
6,160	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS	5.9538639e-05
6,727	Fast Range-Summable Random Variables for Efficient Aggregate Estimation	2006	SIGMOD	5.7902041e-05

Semantically Similar Papers

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