Dynamic Top-K Range Reporting in External Memory

Summary: Fully-dynamic external-memory top-K range reporting structure that matches the static optimal space O(N/B) and query O(log_B N + K/B) bounds. Supports amortized updates in O((log_B N)^2) per insert/delete and construction in O((N/B) log_{M/B} (N/B)). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1570
Venue: PODS
Year: 2012
Pagerank: 5.4740049e-05
Overall Rank: 8,173 | 43.93%
DOI: 10.1145/2213556.2213576

Incoming Non-self Citations Over Time

Authors

1. Cheng Sheng (Chinese University of Hong Kong)
2. Yufei Tao (Korea Advanced Institute of Science and Technology)

BibTeX Citation

@inproceedings{sheng_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Dynamic Top-K Range Reporting in External Memory}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213576},
        doi = {10.1145/2213556.2213576},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sheng, Cheng and Tao, Yufei},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,172	On Top-k Range Reporting in 2D Space	2015	PODS	5.4740049e-05
9,073	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS	5.3251649e-05
12,028	Efficient Top-k Indexing via General Reductions	2016	PODS	5.093636e-05
12,163	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	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
1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00010482997

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,281	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB
2	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
3	7,299	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD
4	9,073	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS
5	12,302	Space-Efficient Range Reporting for Categorical Data	2012	PODS
6	2,443	Independent Range Sampling	2014	PODS
7	8,750	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS
8	8,172	On Top-k Range Reporting in 2D Space	2015	PODS
9	12,028	Efficient Top-k Indexing via General Reductions	2016	PODS
10	12,163	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS