On the complexity of query result diversification

DOI10.1145/2602136MaRDI QIDQ2790132zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ting Deng, Wenfei Fan

Publication date 2 March 2016

Published in ACM Transactions on Database Systems (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/20.500.11820/89aee8f1-4349-495b-9e41-6a137b322a6e

zbMATH Keywords

relevancerecommender systemsdiversitycounting problemsdata complexitydatabase queriesresult diversificationcombined complexity

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Recommendations

• Approximation algorithms for diversified search ranking
• Towards better separation between deterministic and randomized query complexity
• On the complexity of database queries
• Separation between deterministic and randomized query complexity
• Top-k diversity queries over bounded regions
• On the data complexity of consistent query answering

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• Composite recommendations: from items to packages
• Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete
• Max-sum diversification, monotone submodular functions, and dynamic updates
• On the complexity of package recommendation problems
• Optimal aggregation algorithms for middleware.
• Polynomial Space Counting Problems
• Subtractive reductions and complete problems for counting complexity classes
• The complexity of computing the permanent
• The equitable dispersion problem

Cited in

(3)

• On the complexity of package recommendation problems
• Diversity of answers to conjunctive queries
• Diversity of answers to conjunctive queries

Describes a project that uses

Uses Software

• FlexRecs

This page was built for publication: On the complexity of query result diversification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2790132)