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,608 | Interactive Summarization and Exploration of Top Aggregate Query Answers | 2018 | VLDB | 6.046643e-05 |
| 5,660 | Query Refinement for Diverse Top-k Selection | 2024 | SIGMOD | 5.3859487e-05 |
| 6,644 | Query Refinement for Diversity Constraint Satisfaction | 2024 | VLDB | 4.973836e-05 |
| 7,083 | RC-Index: Diversifying Answers to Range Queries | 2018 | VLDB | 4.8331444e-05 |
| 7,145 | Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue | 2024 | PODS | 4.8139975e-05 |
| 9,847 | Discovering Top-k Relevant and Diversified Rules | 2024 | SIGMOD | 4.2680295e-05 |
| 10,320 | Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching | 2026 | VLDB | 4.1905499e-05 |
| 10,499 | Incremental Rule Discovery in Response to Parameter Updates | 2025 | SIGMOD | 4.1905499e-05 |
| 11,339 | Representative Query Results by Voting | 2022 | SIGMOD | 4.1905499e-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 |
|---|---|---|---|---|
| 8 | Optimal Aggregation Algorithms for Middleware [Extended Abstract] | 2001 | PODS | 0.0015436578 |
| 1,606 | Addressing Diverse User Preferences in SQL-Query-Result Navigation | 2007 | SIGMOD | 0.00011175693 |
| 1,664 | Structured Search Result Differentiation | 2009 | VLDB | 0.0001096091 |
| 1,717 | Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates | 2012 | PODS | 0.00010768447 |
| 2,474 | Top-k Bounded Diversification | 2012 | SIGMOD | 8.6956353e-05 |
| 2,965 | Evaluating Rank Joins with Optimal Cost | 2008 | PODS | 7.8049517e-05 |
| 2,982 | FlexRecs: Expressing and Combining Flexible Recommendations | 2009 | SIGMOD | 7.7771174e-05 |
| 3,942 | Efficient Diversification of Web Search Results | 2011 | VLDB | 6.6072828e-05 |
| 6,136 | RankSQL: Supporting Ranking Queries in Relational Database Management Systems | 2005 | VLDB | 5.1906626e-05 |
| 7,273 | Efficient and Generic Evaluation of Ranked Queries | 2011 | SIGMOD | 4.775366e-05 |
| 7,768 | On the Complexity of Package Recommendation Problems | 2012 | PODS | 4.6523419e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,644 | Query Refinement for Diversity Constraint Satisfaction | 2024 | VLDB | 4.973836e-05 |
| 7,083 | RC-Index: Diversifying Answers to Range Queries | 2018 | VLDB | 4.8331444e-05 |
| 1,435 | Diversifying Top-K Results | 2012 | VLDB | 0.00011981694 |
| 7,145 | Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue | 2024 | PODS | 4.8139975e-05 |
| 603 | On the Complexity of Bounded-Variable Queries | 1995 | PODS | 0.00019334592 |
| 7,469 | Boolean + Ranking: Querying a Database by K-Constrained Optimization | 2006 | SIGMOD | 4.7165172e-05 |
| 8,521 | Computing A Well-Representative Summary of Conjunctive Query Results | 2024 | PODS | 4.4893996e-05 |
| 3,702 | Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries | 2020 | VLDB | 6.8251643e-05 |
| 10,007 | Query Answering Under Volume-Based Diversity Functions | 2026 | PODS | 4.1905499e-05 |
| 5,660 | Query Refinement for Diverse Top-k Selection | 2024 | SIGMOD | 5.3859487e-05 |