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 (Beihang University)
- 2. Wenfei Fan (Beihang University; University of Edinburgh)
BibTeX Citation
@article{deng_vldb13,
title = {{On the Complexity of Query Result Diversification}},
author = {Deng, Ting and Fan, Wenfei},
journal = {PVLDB},
series = {{VLDB} '13},
volume = {6},
number = {8},
pages = {577--588},
doi = {10.14778/2536354.2536358},
url = {https://doi.org/10.14778/2536354.2536358},
year = {2013}
}Incoming Citations (Sorted by Pagerank)
Showing 10 of 10 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,631 | Interactive Summarization and Exploration of Top Aggregate Query Answers | 2018 | VLDB | 6.595034e-05 |
| 5,918 | Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue | 2024 | PODS | 6.0427671e-05 |
| 6,293 | Query Refinement for Diversity Constraint Satisfaction | 2024 | VLDB | 5.9247942e-05 |
| 6,389 | Query Refinement for Diverse Top-k Selection | 2024 | SIGMOD | 5.8895166e-05 |
| 7,119 | RC-Index: Diversifying Answers to Range Queries | 2018 | VLDB | 5.6971547e-05 |
| 9,197 | Representative Query Results by Voting | 2022 | SIGMOD | 5.3058708e-05 |
| 9,999 | Discovering Top-k Relevant and Diversified Rules | 2024 | SIGMOD | 5.1814573e-05 |
| 10,301 | Towards Selecting Informative Alternative Relational Query Plans for Database Education | 2026 | SIGMOD | 5.093636e-05 |
| 10,606 | Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching | 2026 | VLDB | 5.093636e-05 |
| 10,766 | Incremental Rule Discovery in Response to Parameter Updates | 2025 | SIGMOD | 5.093636e-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 |
|---|---|---|---|---|
| 5 | Optimal Aggregation Algorithms for Middleware [Extended Abstract] | 2001 | PODS | 0.0010828372 |
| 1,725 | Addressing Diverse User Preferences in SQL-Query-Result Navigation | 2007 | SIGMOD | 9.9197083e-05 |
| 1,908 | Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates | 2012 | PODS | 9.5010932e-05 |
| 2,259 | Top-k Bounded Diversification | 2012 | SIGMOD | 8.8529269e-05 |
| 2,379 | Structured Search Result Differentiation | 2009 | VLDB | 8.666326e-05 |
| 2,585 | Evaluating Rank Joins with Optimal Cost | 2008 | PODS | 8.3774452e-05 |
| 3,048 | FlexRecs: Expressing and Combining Flexible Recommendations | 2009 | SIGMOD | 7.815276e-05 |
| 4,122 | Efficient Diversification of Web Search Results | 2011 | VLDB | 6.8879418e-05 |
| 5,862 | RankSQL: Supporting Ranking Queries in Relational Database Management Systems | 2005 | VLDB | 6.0635561e-05 |
| 7,299 | Efficient and Generic Evaluation of Ranked Queries | 2011 | SIGMOD | 5.6513289e-05 |
| 8,028 | On the Complexity of Package Recommendation Problems | 2012 | PODS | 5.504636e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,293 | Query Refinement for Diversity Constraint Satisfaction | 2024 | VLDB |
| 2 | 7,119 | RC-Index: Diversifying Answers to Range Queries | 2018 | VLDB |
| 3 | 1,454 | Diversifying Top-K Results | 2012 | VLDB |
| 4 | 5,918 | Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue | 2024 | PODS |
| 5 | 763 | On the Complexity of Bounded-Variable Queries | 1995 | PODS |
| 6 | 7,352 | Boolean + Ranking: Querying a Database by K-Constrained Optimization | 2006 | SIGMOD |
| 7 | 8,728 | Computing A Well-Representative Summary of Conjunctive Query Results | 2024 | PODS |
| 8 | 2,745 | Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries | 2020 | VLDB |
| 9 | 10,180 | Query Answering Under Volume-Based Diversity Functions | 2026 | PODS |
| 10 | 6,389 | Query Refinement for Diverse Top-k Selection | 2024 | SIGMOD |