Loading...
Please wait, while we are loading the content...
Similar Documents
Best-k queries on database systems.
| Content Provider | CiteSeerX |
|---|---|
| Author | Chengxiang, Tao Tao |
| Abstract | 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 bestk query is an NP-hard problem and propose an efficient approximation algorithm. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Database System Best-k Query Top-k Query Fuzzy Matching Top-k Tuples Complex Query Certain Utility Function Top-k Query Search General Bestk Query Database Selection Special Case Efficient Approximation Algorithm Much Attention Decision Problem Tuple Redundancy Best-k Query Search Database Tuples Np-hard Problem Boolean Query Search Selection Criterion Global Measure General Formal Framework Database Selection Problem |
| Content Type | Text |
