On the Complexity of Query Result Diversification
Summary: Explores the complexity of query result diversification for relational queries under a bi-criteria relevance–diversity objective; defines existence, ranking, and counting of k-element diversified sets. Establishes tight bounds for several languages and three objectives, and notes tractable cases. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Ting Deng
- 2. Wenfei Fan
Incoming Citations (Sorted by Pagerank)
Showing 9 of 9 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,614 | Interactive Summarization and Exploration of Top Aggregate Query Answers | 2018 | VLDB | 6.0467204e-05 |
| 5,649 | Query Refinement for Diverse Top-k Selection | 2024 | SIGMOD | 5.3911246e-05 |
| 6,643 | Query Refinement for Diversity Constraint Satisfaction | 2024 | VLDB | 4.9786132e-05 |
| 7,101 | RC-Index: Diversifying Answers to Range Queries | 2018 | VLDB | 4.8322751e-05 |
| 7,195 | Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue | 2024 | PODS | 4.8037242e-05 |
| 9,847 | Discovering Top-k Relevant and Diversified Rules | 2024 | SIGMOD | 4.2721228e-05 |
| 10,308 | Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching | 2026 | VLDB | 4.1945683e-05 |
| 10,489 | Incremental Rule Discovery in Response to Parameter Updates | 2025 | SIGMOD | 4.1945683e-05 |
| 11,337 | Representative Query Results by Voting | 2022 | SIGMOD | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 11 of 11 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7 | Optimal Aggregation Algorithms for Middleware [Extended Abstract] | 2001 | PODS | 0.0015496097 |
| 1,605 | Addressing Diverse User Preferences in SQL-Query-Result Navigation | 2007 | SIGMOD | 0.00011186762 |
| 1,667 | Structured Search Result Differentiation | 2009 | VLDB | 0.00010960247 |
| 1,725 | Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates | 2012 | PODS | 0.00010748322 |
| 2,480 | Top-k Bounded Diversification | 2012 | SIGMOD | 8.6899714e-05 |
| 2,961 | Evaluating Rank Joins with Optimal Cost | 2008 | PODS | 7.8110394e-05 |
| 2,979 | FlexRecs: Expressing and Combining Flexible Recommendations | 2009 | SIGMOD | 7.7844948e-05 |
| 3,941 | Efficient Diversification of Web Search Results | 2011 | VLDB | 6.6124442e-05 |
| 6,882 | RankSQL: Supporting Ranking Queries in Relational Database Management Systems | 2005 | VLDB | 4.8963901e-05 |
| 7,276 | Efficient and Generic Evaluation of Ranked Queries | 2011 | SIGMOD | 4.7798595e-05 |
| 7,770 | On the Complexity of Package Recommendation Problems | 2012 | PODS | 4.6562597e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,824 | Optimization of Multiple-Relation Multiple-Disjunct Queries | 1988 | PODS | 4.6418459e-05 |
| 6,643 | Query Refinement for Diversity Constraint Satisfaction | 2024 | VLDB | 4.9786132e-05 |
| 1,445 | Diversifying Top-K Results | 2012 | VLDB | 0.00011945231 |
| 7,101 | RC-Index: Diversifying Answers to Range Queries | 2018 | VLDB | 4.8322751e-05 |
| 7,195 | Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue | 2024 | PODS | 4.8037242e-05 |
| 602 | On the Complexity of Bounded-Variable Queries | 1995 | PODS | 0.00019352415 |
| 7,468 | Boolean + Ranking: Querying a Database by K-Constrained Optimization | 2006 | SIGMOD | 4.7210446e-05 |
| 10,927 | Computing A Well-Representative Summary of Conjunctive Query Results | 2024 | PODS | 4.1945683e-05 |
| 3,715 | Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries | 2020 | VLDB | 6.8220943e-05 |
| 5,649 | Query Refinement for Diverse Top-k Selection | 2024 | SIGMOD | 5.3911246e-05 |