Efficient Indexes for Diverse Top-k Range Queries
Summary: Studying top-k range queries that return diverse, high-weight points in R^d under bicriteria (trade-off value vs. diversity) and constrained (maximize value with diversity constraint) objectives; gives offline (0.5-ε)-approx algorithms. Proposes near-linear-size, near-linear-time-built indexes answering rectangle queries in O(k polylog n) with (0.5-ε)-approx; for constrained queries achieves 0.5^{O(d)}-approx or (1-ε)-approx if allowing ε expansion, same query time. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Pankaj K. Agarwal (Duke University)
- 2. Stavros Sintos (Duke University)
- 3. Alex Steiger (Duke University)
BibTeX Citation
@inproceedings{agarwal_pods20,
address = {New York, NY, USA},
series = {{PODS} '20},
title = {{Efficient Indexes for Diverse Top-k Range Queries}},
url = {https://dl.acm.org/doi/10.1145/3375395.3387667},
doi = {10.1145/3375395.3387667},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Agarwal, Pankaj K. and Sintos, Stavros and Steiger, Alex},
year = {2020}
}Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,728 | Computing A Well-Representative Summary of Conjunctive Query Results | 2024 | PODS | 5.3766157e-05 |
| 10,151 | Coresets for Robust Query Optimization | 2026 | PODS | 5.093636e-05 |
| 11,175 | Faster Algorithms for Fair Max-Min Diversification in Rd | 2024 | SIGMOD | 5.093636e-05 |
| 11,419 | Equitable Top-k Results for Long Tail Data | 2023 | SIGMOD | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,959 | Composable Core-sets for Diversity and Coverage Maximization | 2014 | PODS | 7.9182968e-05 |
| 5,847 | MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension | 2017 | VLDB | 6.0676282e-05 |
| 7,119 | RC-Index: Diversifying Answers to Range Queries | 2018 | VLDB | 5.6971547e-05 |
| 8,172 | On Top-k Range Reporting in 2D Space | 2015 | PODS | 5.4740049e-05 |
| 8,173 | Dynamic Top-K Range Reporting in External Memory | 2012 | PODS | 5.4740049e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 12,027 | Range-Max Queries on Uncertain Data | 2016 | PODS |
| 2 | 7,299 | Efficient and Generic Evaluation of Ranked Queries | 2011 | SIGMOD |
| 3 | 12,489 | Worst-Case Efficient Range Search Indexing | 2009 | PODS |
| 4 | 8,281 | Efficient Top-K Processing Over Query-Dependent Functions | 2008 | VLDB |
| 5 | 12,296 | Efficient Indexing for Diverse Query Results | 2013 | VLDB |
| 6 | 12,028 | Efficient Top-k Indexing via General Reductions | 2016 | PODS |
| 7 | 3,007 | Towards Robust Indexing for Ranked Queries | 2006 | VLDB |
| 8 | 7,259 | Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search | 2025 | SIGMOD |
| 9 | 1,529 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS |
| 10 | 6,753 | Optimal Indexing Using Near-Minimal Space [Extended Abstract] | 2003 | PODS |