CoSky: A Practical Method for Ranking Skylines in Databases

International audienceDiscovering Skylines in Databases have been actively studied to effectively identify optimal tuples/objects with respect to a set of designated preference attributes. Few approaches have been proposed for ranking the skylines to resolve the problem of the high cardinality of the result set. The most recent approach to rank skylines is the dp-idp (dominance power-inverse dominance power) which extensively uses the Pareto-dominance relation to determine the score of each skyline. The dp-idp method is in the very same spirit as tf-idf weighting scheme from Information Retrieval. In this paper, we firstly make an Enrichment of dp-idp with Dominance Hierarchy to facilitate the determination of Skyline scores, we propose then the CoSky method (Cosine Skylines) for fast ranking skylines in Databases without computing the Pareto-dominance relation. Cosky is a TOPSIS-like method (Technique for Order of Preference by Similarity to Ideal Solution) resulting from the cross-fertilization between the fields of Information Retrieval, Multiple Criteria Decision Analysis, and Databases. The innovative features of CoSky are principally: the automatic weighting of the normalized attributes based on Gini index, the score of each skyline using the Saltons cosine of the angle between each skyline object and the ideal object, and its direct implementation into any RDBMS without further structures. Finally, we propose the algorithm DeepSky, a Multilevel skyline algorithm based on CoSky method to find Top-k ranked Skylines