Top-k Combinatorial Skyline with Threshold and Cardinality Constraints
| Autor: | Wen-Hsin Chang, 張文欣 |
|---|---|
| Rok vydání: | 2009 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 97 In recent years, the skyline operator has been popular. This is mainly due to the importance of various skyline results in applications involving multi-criteria decision making. However, skyline queries are considered in comparing each tuple one by one so as to provide useful information for the user but ignoring that user may wish to find information from a combination (constituted through a specific function from one to more tuples) which meets the conditions of the isuued query. %Then, the user wishes to make this combination to meet the conditions of the issued query. In this paper, we exploit a new skyline query, {em { f T}op-k { f C}ombinatorial { f S}kyline with { f T}hreshold and { f C}ardinality constraints { f Q}uery} ({em Top-k CSTCQ}). Top-k CSTCQ can tackle the problem of a combination which is constituted from one to more tuples. However, the computation complexity of top-k CSTCQ is quite high. We design an efficient algorithm, named {em { f T}op-k { f T}hreshold and { f C}ardinality-based { f C}ombinatorial { f S}kyline} ({em TTCCS}) algorithm, to solve Top-k CSTCQ. First, TTCCS algorithm adopts a concept of transforming threshold constraints to cardinality constraint to reduce the number of combinations, and then uses the concept of binomial coefficient and dynamic programming to construct a table-based algorithm. We propose four pruning strategies to improve TTCCS algorithm (named {em TTCCS -Extension}) to prune the non-qualifying combinations progressively. Comprehensive experiments show that our algorithms can answer Top-k CSTCQ on various synthetic datasets efficiently. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|