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.4103278e-05
Overall Rank: 3,338 | 77.56%
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.6632438e-05
4,729	Interactive Summarization and Exploration of Top Aggregate Query Answers	2018	VLDB	6.4470592e-05
5,989	Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue	2024	PODS	5.9253439e-05
6,247	RC-Index: Diversifying Answers to Range Queries	2018	VLDB	5.8360766e-05
6,520	Query Refinement for Diverse Top-k Selection	2024	SIGMOD	5.7573717e-05
9,377	Representative Query Results by Voting	2022	SIGMOD	5.1868213e-05
10,186	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.0651993e-05
10,513	Towards Selecting Informative Alternative Relational Query Plans for Database Education	2026	SIGMOD	4.9793485e-05
10,852	Fast and Private Max-Sum Diversification	2026	VLDB	4.9793485e-05
11,053	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.9793485e-05
11,188	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	4.9793485e-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.0010679641
1,729	Addressing Diverse User Preferences in SQL-Query-Result Navigation	2007	SIGMOD	9.7679275e-05
1,936	Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates	2012	PODS	9.3387282e-05
2,174	Top-k Bounded Diversification	2012	SIGMOD	8.917444e-05
2,414	Structured Search Result Differentiation	2009	VLDB	8.5081277e-05
2,614	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.2255837e-05
3,096	FlexRecs: Expressing and Combining Flexible Recommendations	2009	SIGMOD	7.652501e-05
4,168	Efficient Diversification of Web Search Results	2011	VLDB	6.7634315e-05
5,941	RankSQL: Supporting Ranking Queries in Relational Database Management Systems	2005	VLDB	5.940085e-05
7,394	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	5.5370795e-05
8,183	On the Complexity of Package Recommendation Problems	2012	PODS	5.3817332e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,327	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB
2	6,247	RC-Index: Diversifying Answers to Range Queries	2018	VLDB
3	1,476	Diversifying Top-K Results	2012	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,497	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD
7	7,513	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS
8	2,591	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
9	10,396	Query Answering Under Volume-Based Diversity Functions	2026	PODS
10	6,520	Query Refinement for Diverse Top-k Selection	2024	SIGMOD