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 |
|---|---|---|---|---|
| 8,521 | Computing A Well-Representative Summary of Conjunctive Query Results | 2024 | PODS | 4.4893996e-05 |
| 10,964 | Faster Algorithms for Fair Max-Min Diversification in Rd | 2024 | SIGMOD | 4.1905499e-05 |
| 11,220 | Equitable Top-k Results for Long Tail Data | 2023 | SIGMOD | 4.1905499e-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,756 | Composable Core-sets for Diversity and Coverage Maximization | 2014 | PODS | 8.1682323e-05 |
| 5,888 | MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension | 2017 | VLDB | 5.2843653e-05 |
| 7,083 | RC-Index: Diversifying Answers to Range Queries | 2018 | VLDB | 4.8331444e-05 |
| 7,850 | On Top-k Range Reporting in 2D Space | 2015 | PODS | 4.6320876e-05 |
| 7,851 | Dynamic Top-K Range Reporting in External Memory | 2012 | PODS | 4.6320876e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,832 | Range-Max Queries on Uncertain Data | 2016 | PODS | 4.1905499e-05 |
| 7,273 | Efficient and Generic Evaluation of Ranked Queries | 2011 | SIGMOD | 4.775366e-05 |
| 12,302 | Worst-Case Efficient Range Search Indexing | 2009 | PODS | 4.1905499e-05 |
| 7,966 | Efficient Top-K Processing Over Query-Dependent Functions | 2008 | VLDB | 4.6089395e-05 |
| 12,107 | Efficient Indexing for Diverse Query Results | 2013 | VLDB | 4.1905499e-05 |
| 11,833 | Efficient Top-k Indexing via General Reductions | 2016 | PODS | 4.1905499e-05 |
| 3,447 | Towards Robust Indexing for Ranked Queries | 2006 | VLDB | 7.082382e-05 |
| 8,419 | Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search | 2025 | SIGMOD | 4.5119865e-05 |
| 1,183 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013444058 |
| 5,695 | Optimal Indexing Using Near-Minimal Space [Extended Abstract] | 2003 | PODS | 5.3675705e-05 |