Tsinghua Science and Technology  2019, Vol. 24 Issue (2): 171-182    doi: 10.26599/TST.2018.9010051
Computing Skyline Groups: An Experimental Evaluation
Haoyang Zhu, Xiaoyong Li*, Qiang Liu, Hao Zhu
∙ Haoyang Zhu is with the Academy of Military Science of the People’s Liberation Army, Beijing 100091, China. E-mail: zhuhaoyang@nudt.edu.cn.
∙ Xiaoyong Li is with the Academy of Ocean Science and Engineering, National University of Defense Technology, Changsha 410073, China.
∙ Qiang Liu and Hao Zhu are with the College of Computer, National University of Defense Technology, Changsha 410073, China. E-mail: qiangliu06@nudt.edu.cn; haozhu@nudt.edu.cn.
 Download: PDF (1018 KB)      HTML Export: BibTeX | EndNote (RIS)       Supporting Info
Guide

Abstract

Skyline group, also named as combinational skyline or group-based skyline, has attracted more attention recently. The concept of skyline groups is proposed to address the problem in the inadequacy of the traditional skyline to answer queries that need to analyze not only individual points but also groups of points. Skyline group algorithms aim at finding groups of points that are not dominated by any other same-size groups. Although two types of dominance relationship exist between the groups defined in existing works, they have not been compared systematically under the same experimental framework. Thus, practitioners face difficulty in selecting an appropriate definition. Furthermore, the experimental evaluation in most existing works features a weakness, that is, studies only experimented on small data sets or large data sets with small dimensions. For comprehensive comparisons of the two types of definition and existing algorithms, we evaluate each algorithm in terms of time and space on various synthetic and real data sets. We reveal the characteristics of existing algorithms and provide guidelines on selecting algorithms for different situations.

Received: 22 May 2017      Published: 29 April 2019
Corresponding Authors: Xiaoyong Li
 Fig. 1 A skyline example. Table 1 Summary of notations. Fig. 2 Dominance relations under different aggregate functions. Table 2 Skyline groups under different definitions. Fig. 3 An example of computing 2-point skyline groups under Permutation. Table 3 G and V, under various n, l (d=6). Table 4 G and V, under various d, l (n=1 $×?×$$𝟏𝟎𝟔$). Fig. 4 Runtime on NBA data set. Fig. 5 Output size on NBA data set. Fig. 6 Experimental results on NBA data set under MAX. Fig. 7 Experimental results on NBA data set under MIN. Fig. 8 (a) and (b): Runtime; (c) and (d): output size, mixture of SUM, MAX, and MIN. n=1××𝟏𝟎𝟔,l=2)."> Fig. 9 Experimental results on correlated data sets ($n=1××𝟏𝟎𝟔,l=2)$. n=1××𝟏𝟎𝟔,l=2)."> Fig. 10 Experimental results on independent data sets ($n=1××𝟏𝟎𝟔,l=2)$. n=1××𝟏𝟎𝟔,l=2)."> Fig. 11 Experimental results on anti-correlated data sets ($n=1××𝟏𝟎𝟔,l=2)$. Table 5 Characteristics of existing algorithms.