Group-Based Skyline for Pareto Optimal Groups
- 17 December 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 33 (7), 2914-2929
- https://doi.org/10.1109/tkde.2019.2960347
Abstract
Skyline computation, aiming at identifying a set of skyline points that are not dominated by any other point, is particularly useful for multi-criteria data analysis and decision making. Traditional skyline computation, however, is inadequate to answer queries that need to analyze not only individual points but also groups of points. To address this gap, we generalize the original skyline definition to the novel group-based skyline (G-Skyline), which represents Pareto optimal groups that are not dominated by other groups. In order to compute G-Skyline groups consisting of s points efficiently, we present a novel structure that represents the points in a directed skyline graph and captures the dominance relationships among the points based on the first s skyline layers. We propose efficient algorithms to compute the first s skyline layers. We then present two heuristic algorithms to efficiently compute the G-Skyline groups: the point-wise algorithm and the unit group-wise algorithm, using various pruning strategies. We observe that the number of G-Skyline groups of a dataset can be significantly large, we further propose the top- k representative G-Skyline groups based on the number of dominated points and the number of dominated groups and present efficient algorithms for computing them. The experimental results on the real NBA dataset and the synthetic datasets show that G-Skyline is interesting and useful, and our algorithms are efficient and scalable.Keywords
Funding Information
- National Science Foundation (IIS-1838200, CNS-1618932)
- Air Force Office of Scientific Research (FA9550-12-1-0240)
This publication has 33 references indexed in Scilit:
- Finding Pareto optimal groupsProceedings of the VLDB Endowment, 2015
- Preference-Based Top-k Representative Skyline Queries on Uncertain DatabasesLecture Notes in Computer Science, 2015
- Faster output-sensitive skyline computation algorithmInformation Processing Letters, 2014
- Taking the Big Picture: representative skylines based on significance and diversityThe VLDB Journal, 2014
- On Skyline GroupsIEEE Transactions on Knowledge and Data Engineering, 2013
- Group skyline computationInformation Sciences, 2012
- Discovering Representative Skyline Points over Distributed DataLecture Notes in Computer Science, 2012
- Algorithms and analyses for maximal vector computationThe VLDB Journal, 2006
- On the Average Number of Maxima in a Set of Vectors and ApplicationsJournal of the ACM, 1978
- On Finding the Maxima of a Set of VectorsJournal of the ACM, 1975