Computing skyline groups: an experimental evaluation

Haoyang Zhu, Xiaoyong Li, Qiang LiuTsinghua 2018 · DOI

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.

Introduction

While traditional skyline queries find individual "best" items, skyline groups identify non-dominated teams or bundles of items. This paper provides the first comprehensive experimental benchmark of the two competing ways to define group dominance, revealing that while permutation-based definitions offer the most options, aggregate-based definitions (like SUM) are computationally grueling but often more practical for decision-making.

Problem Definition

Imagine you are building a fantasy sports team. A traditional "skyline query" helps you find individual players who aren't strictly worse than anyone else in all stats (points, rebounds, assists). But you aren't just picking one player; you’re picking a team.

The "Skyline Group" concept was created to find groups of points that aren't dominated by any other group of the same size. However, the field has been fragmented by two different definitions of "dominance":

  1. Permutation-based: Group A dominates Group B if you can pair up their members such that every member of A is better than their counterpart in B.
  2. Aggregate-based: Group A dominates Group B if its total (SUM), best (MAX), or worst (MIN) stats are better.

Until now, these definitions and their associated algorithms hadn't been tested side-by-side on large, high-dimensional datasets, leaving engineers in the dark about which to implement.

Methods and Algorithms

The authors systematically evaluate several key algorithms under a unified framework:

  • unit-wise+: The state-of-the-art for permutation-based skylines. It uses a "unit" concept—grouping a point with all points that dominate it—to prune the search space.
  • DPSG (Dynamic Programming for Skyline Groups): A DP approach primarily used for SUM aggregates. It builds $l$-point groups by combining $(l-1)$-point groups with individual points.
  • DPAV (Distinct Aggregate Vectors): An algorithm designed to find unique aggregate signatures for MAX and MIN definitions.
  • MAXG/MING: Brute-force methods used to reconstruct actual groups from aggregate vectors.

The paper also contributes a theoretical proof showing the relationship between these definitions—specifically, that a skyline group under the SUM definition is always a subset of the permutation-based skyline.

Key Insights: The Complexity Gap

Computing skyline groups is orders of magnitude harder than traditional skylines. While a traditional skyline might return dozens of points, a skyline group query can return billions of combinations.

Output size vs. group size (l) for different dominance definitions.

A surprising finding is the "MAX" Explosion: if your group size ($l$) is larger than the number of dimensions ($d$), the output size explodes. Once you've picked the "best" players for each stat, the remaining slots in the group can be filled by anyone, leading to a combinatorial nightmare. As shown in the figure above, the output size for permutation and MAX definitions grows exponentially with group size.

Key Results: Efficiency and Scalability

  • Efficiency: unit-wise+ is generally the fastest for permutation queries. For aggregate queries, DPSG surprisingly outperforms DPAV when computing aggregate vectors for MAX and MIN.
  • Runtime Bottlenecks: DPSG(SUM) is the slowest, often taking 2 to 4 orders of magnitude longer than permutation or MAX/MIN queries. Because the sum is sensitive to every single point in the group, the algorithm has to perform far more dominance tests.
Runtime (ms) vs. group size (l) highlighting the computational cost of SUM.
  • Output Size: Permutation-based definitions yield the most groups, making them "informative" but potentially overwhelming. SUM provides a more refined, smaller subset of results.
  • Scalability: Runtimes grow exponentially with the number of dimensions ($d$) and group size ($l$), but only linearly with the total number of points ($n$).

Limitations and Future Work

The biggest hurdle remains the "Information Overload"—the sheer number of skyline groups can be too large for a human to process. The authors suggest that future work should focus on Top-k dominating queries to rank the most important groups. Additionally, because these algorithms are computationally heavy, the authors point toward the development of parallel algorithms that can leverage multi-core GPUs and distributed computing platforms.

Summary updated

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.
BibTeX
@inproceedings{zhu2018computing,
  author = {Haoyang Zhu and Xiaoyong Li and Qiang Liu and Hao Zhu},
  title = {{Computing skyline groups: an experimental evaluation}},
  booktitle = {Tsinghua},
  year = {2018},
  doi = {10.26599/tst.2018.9010051},
}
Figure