New Results on Two-dimensional Orthogonal Range Aggregation in External Memory

Summary: External-memory study of orthogonal range aggregation over N axis-aligned rectangles with integer weights, answering aggregates over rectangles intersecting a query rectangle. Presents linear/near-linear-space indexes with O(log_B N) I/Os for max/min and O(log^2_B N) I/Os for sum/count/avg. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1539
Venue: PODS
Year: 2011
Pagerank: 5.9538639e-05
Overall Rank: 6,160 | 57.74%
DOI: 10.1145/1989284.1989297

Incoming Non-self Citations Over Time

Authors

1. Cheng Sheng (Chinese University of Hong Kong)
2. Yufei Tao (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{sheng_pods11,
        address = {New York, NY, USA},
        series = {{PODS} '11},
        title = {{New Results on Two-dimensional Orthogonal Range Aggregation in External Memory}},
        url = {https://dl.acm.org/doi/10.1145/1989284.1989297},
        doi = {10.1145/1989284.1989297},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sheng, Cheng and Tao, Yufei},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,024	A Scalable Algorithm for Maximizing Range Sum in Spatial Databases	2012	VLDB	7.8388143e-05
3,700	Approximate MaxRS in Spatial Databases	2013	VLDB	7.1861452e-05
4,755	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS	6.5226838e-05
7,600	Towards Best Region Search for Data Exploration	2016	SIGMOD	5.5867987e-05
8,172	On Top-k Range Reporting in 2D Space	2015	PODS	5.4740049e-05
10,173	A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions	2026	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
648	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00015324657

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,173	Dynamic Top-K Range Reporting in External Memory	2012	PODS
2	1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS
3	4,755	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS
4	6,619	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS
5	12,302	Space-Efficient Range Reporting for Categorical Data	2012	PODS
6	12,163	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS
7	3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS
8	12,303	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS
9	8,172	On Top-k Range Reporting in 2D Space	2015	PODS
10	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS