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)

Paper ID: hd5c8ea3384e61728
Venue: VLDB
Year: 2013
Pagerank: 7.4068199e-05
Overall Rank: 3,338 | 77.57%
DOI: 10.14778/2536354.2536358

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 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,327	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB	6.6600895e-05
4,731	Interactive Summarization and Exploration of Top Aggregate Query Answers	2018	VLDB	6.4440072e-05
5,989	Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue	2024	PODS	5.9225389e-05
6,250	RC-Index: Diversifying Answers to Range Queries	2018	VLDB	5.8333139e-05
6,522	Query Refinement for Diverse Top-k Selection	2024	SIGMOD	5.7546462e-05
9,386	Representative Query Results by Voting	2022	SIGMOD	5.1843659e-05
10,189	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.0628015e-05
10,524	Towards Selecting Informative Alternative Relational Query Plans for Database Education	2026	SIGMOD	4.9769913e-05
10,861	Fast and Private Max-Sum Diversification	2026	VLDB	4.9769913e-05
11,062	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.9769913e-05
11,197	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	4.9769913e-05

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.0010679903
1,732	Addressing Diverse User Preferences in SQL-Query-Result Navigation	2007	SIGMOD	9.7633187e-05
1,937	Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates	2012	PODS	9.334308e-05
2,177	Top-k Bounded Diversification	2012	SIGMOD	8.9132232e-05
2,415	Structured Search Result Differentiation	2009	VLDB	8.5041001e-05
2,615	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.2217676e-05
3,098	FlexRecs: Expressing and Combining Flexible Recommendations	2009	SIGMOD	7.6488784e-05
4,168	Efficient Diversification of Web Search Results	2011	VLDB	6.760235e-05
5,941	RankSQL: Supporting Ranking Queries in Relational Database Management Systems	2005	VLDB	5.937273e-05
7,396	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	5.5344583e-05
8,190	On the Complexity of Package Recommendation Problems	2012	PODS	5.3791856e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,327	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB
2	1,476	Diversifying Top-K Results	2012	VLDB
3	6,250	RC-Index: Diversifying Answers to Range Queries	2018	VLDB
4	5,989	Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue	2024	PODS
5	794	On the Complexity of Bounded-Variable Queries	1995	PODS
6	7,502	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD
7	7,518	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS
8	2,593	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
9	10,408	Query Answering Under Volume-Based Diversity Functions	2026	PODS
10	6,522	Query Refinement for Diverse Top-k Selection	2024	SIGMOD