NDLI: On the Complexity of Query Result Diversification

Content Provider	ACM Digital Library
Author	Fan, Wenfei Deng, Ting
Copyright Year	2014
Abstract	Query result diversification is a bi-criteria optimization problem for ranking query results. Given a database $\textit{D},$ a query $\textit{Q},$ and a positive integer $\textit{k},$ it is to find a set of $\textit{k}$ tuples from $\textit{Q}(\textit{D})$ such that the tuples are as relevant as possible to the query, and at the same time, as diverse as possible to each other. Subsets of $\textit{Q}(\textit{D})$ are ranked by an objective function defined in terms of relevance and diversity. Query result diversification has found a variety of applications in databases, information retrieval, and operations research. This article investigates the complexity of result diversification for relational queries. (1) We identify three problems in connection with query result diversification, to determine whether there exists a set of $\textit{k}$ tuples that is ranked above a bound with respect to relevance and diversity, to assess the rank of a given $\textit{k}-element$ set, and to count how many $\textit{k}-element$ sets are ranked above a given bound based on an objective function. (2) We study these problems for a variety of query languages and for the three objective functions proposed in Gollapudi and Sharma [2009]. We establish the upper and lower bounds of these problems, all matching, for both combined complexity and data complexity. (3) We also investigate several special settings of these problems, identifying tractable cases. Moreover, (4) we reinvestigate these problems in the presence of compatibility constraints commonly found in practice, and provide their complexity in all these settings.
Starting Page	1
Ending Page	46
Page Count	46
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/2602136
Volume Number	39
Issue Number	2
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-05-26
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Result diversification Combined complexity Counting problems Data complexity Database queries Diversity Recommender systems Relevance
Content Type	Text
Resource Type	Article
Subject	Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the complexity of query result diversification.

Ranking queries on uncertain data

Distributed query evaluation on semistructured data

Linear queries in statistical databases

On the Complexity of Query Result Diversification

Optimizing complex queries based on similarities of subqueries

Searching the Web with Queries

A survey of query result diversification

Flexible and Efficient Resolution of Skyline Query Size Constraints

On the Complexity of Query Result Diversification

Similar Documents

On the complexity of query result diversification.

Ranking queries on uncertain data

Distributed query evaluation on semistructured data

Linear queries in statistical databases

On the Complexity of Query Result Diversification

Optimizing complex queries based on similarities of subqueries

Searching the Web with Queries

A survey of query result diversification

Flexible and Efficient Resolution of Skyline Query Size Constraints

On the Complexity of Query Result Diversification