Categorical Range Maxima Queries

Summary: Defines Categorical Range Maxima Query (CRMQ): for each color in A[a..b] report the maximum-valued item (and its position); considers threshold and top-k variants. Presents linear-space RAM O(k) queries and external-memory structures with optimal O(1+k/B) I/Os (almost-linear or linear space with O(log* n) overhead), yielding improved categorical range reporting and document-retrieval bounds. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h8616d2bbe775ddda
Venue: PODS
Year: 2014
Pagerank: 5.4772833e-05
Overall Rank: 7,667 | 48.46%
DOI: 10.1145/2594538.2594557

Incoming Non-self Citations Over Time

Authors

1. Manish Patil (Louisiana State University)
2. Sharma V. Thankachan (University of Waterloo)
3. Rahul Shah (Louisiana State University)
4. Yakov Nekrich (University of Waterloo)
5. Jeffrey Scott Vitter (University of Kansas)

BibTeX Citation

@inproceedings{patil_pods14,
        address = {New York, NY, USA},
        series = {{PODS} '14},
        title = {{Categorical Range Maxima Queries}},
        url = {https://dl.acm.org/doi/10.1145/2594538.2594557},
        doi = {10.1145/2594538.2594557},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Patil, Manish and Thankachan, Sharma V. and Shah, Rahul and Nekrich, Yakov and Vitter, Jeffrey Scott},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,323	Efficient Top-k Indexing via General Reductions	2016	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 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,559	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00010252232
12,593	Space-Efficient Range Reporting for Categorical Data	2012	PODS	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,322	Range-Max Queries on Uncertain Data	2016	PODS
2	8,913	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS
3	8,249	On Top-k Range Reporting in 2D Space	2015	PODS
4	4,698	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS
5	12,350	Range Thresholding on Streams	2016	SIGMOD
6	7,776	Efficient Indexes for Diverse Top-k Range Queries	2020	PODS
7	8,250	Dynamic Top-K Range Reporting in External Memory	2012	PODS
8	12,454	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS
9	12,323	Efficient Top-k Indexing via General Reductions	2016	PODS
10	12,593	Space-Efficient Range Reporting for Categorical Data	2012	PODS