University of Illinois Urbana-Champaign

Best-k Queries on Database Systems

Tao, Tao; Zhai, ChengXiang

Content Files
Best-k Queries on Database Systems.pdf

Permalink

https://hdl.handle.net/2142/11248

Description

Title
Best-k Queries on Database Systems
Author(s)
  • Tao, Tao
  • Zhai, ChengXiang
Issue Date
2006-08
Keyword(s)
database
Date of Ingest
2009-04-21T16:30:01Z
Abstract
As exploratory queries become more and more popular, the study of how to select k items based on fuzzy matching and ranking of database tuples (i.e. top-k queries) has attracted much attention recently. However, taking the top-k tuples based on their scores computed independently is inadequate for modeling some complex queries finding the best-k tuples based on some selection criteria involving a global measure on multiple selected tuples (e.g., tuple redundancy or compatibility). In this paper, we introduce and study such best-k queries, and further model a database selection problem generally as a decision problem, in which a database system would respond to a query by selecting a subset of tuples that optimize a certain utility function defined globally. Accordingly, we present a general formal framework for database selection, which covers the boolean query search, the top-k query search, and the best-k query search all as special cases. We prove that finding answers to a general best-k query is an NP-hard problem. We propose an anytime algorithm, which allows a user to stop the algorithm at any time to achieve a flexible tradeoff between the result optimality and the running time, to execute a best-k query efficiently. Experiment results show that the algorithm can be used to efficiently answer a best-k query.
Type of Resource
text
Genre of Resource
Technical Report
Permalink
http://hdl.handle.net/2142/11248
Copyright and License Information
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections

Research and Tech Reports - Computer Science PRIMARY