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
- 2. Stavros Sintos
- 3. Alex Steiger
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,927 | Computing A Well-Representative Summary of Conjunctive Query Results | 2024 | PODS | 4.1945683e-05 |
| 10,961 | Faster Algorithms for Fair Max-Min Diversification in Rd | 2024 | SIGMOD | 4.1945683e-05 |
| 11,218 | Equitable Top-k Results for Long Tail Data | 2023 | SIGMOD | 4.1945683e-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,752 | Composable Core-sets for Diversity and Coverage Maximization | 2014 | PODS | 8.1742326e-05 |
| 5,883 | MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension | 2017 | VLDB | 5.2890537e-05 |
| 7,101 | RC-Index: Diversifying Answers to Range Queries | 2018 | VLDB | 4.8322751e-05 |
| 7,845 | On Top-k Range Reporting in 2D Space | 2015 | PODS | 4.6365341e-05 |
| 7,846 | Dynamic Top-K Range Reporting in External Memory | 2012 | PODS | 4.6365341e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,824 | Range-Max Queries on Uncertain Data | 2016 | PODS | 4.1945683e-05 |
| 7,276 | Efficient and Generic Evaluation of Ranked Queries | 2011 | SIGMOD | 4.7798595e-05 |
| 12,294 | Worst-Case Efficient Range Search Indexing | 2009 | PODS | 4.1945683e-05 |
| 7,963 | Efficient Top-K Processing Over Query-Dependent Functions | 2008 | VLDB | 4.613363e-05 |
| 12,099 | Efficient Indexing for Diverse Query Results | 2013 | VLDB | 4.1945683e-05 |
| 11,825 | Efficient Top-k Indexing via General Reductions | 2016 | PODS | 4.1945683e-05 |
| 3,463 | Towards Robust Indexing for Ranked Queries | 2006 | VLDB | 7.069675e-05 |
| 8,425 | Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search | 2025 | SIGMOD | 4.5163161e-05 |
| 1,182 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013455963 |
| 5,682 | Optimal Indexing Using Near-Minimal Space [Extended Abstract] | 2003 | PODS | 5.372736e-05 |