# Partitioning Strategies for Parallel Computation of Flexible Skylines
## 6 Related Work  
There is abundant literature that has studied and proposed sequential algorithms for the computation of the skyline, including Block-Nested Loop (BNL) and Divide-and-Conquer [2], Sort Filter Skyline (SFS) [4], Bitmap [10], Branch-and-Bound [11, 12], and Sort and Limit Skyline algorithm (SaLSa) [13]. The pre-sorting imposed by SFS is a suitable strategy for exploiting the topological sort property of dominance, which extends to \(\mathcal{F}\)-dominance, and has therefore been exploited in the sequential algorithms for computing flexible skylines [3, 14, 15], including SVE1F and POP12, which we used here.  
Systematic approaches for parallelizing the computation of skylines have been attempted for both _vertical partitioning_ (essentially following [PERSON]'s middleware scenario for top-k queries [16, 17, 18]) and _horizontal partitioning_[19], which we considered in the present work. Horizontal partitioning strategies for computing the skyline have found their way to practical implementations with the advent of computation paradigms such as Map-Reduce [20] and Spark [21], which allow seamless data distribution and processing through Mappers and Reducers, as demonstrated in [5, 6, 22], together with optimization opportunities given by representative tuples and the elimination of the final sequential round, which was partially advocated in [8].  
While other works have considered flexible skylines in the context of vertical distribution [14], the case of horizontal partitioning is, to the best of our knowledge, novel.  
While classical skylines have no support for preferences, top-\(k\) queries are the alternative (and, typically, preferred) ranking tool that not only supports preferences through scoring functions, but also controls the output size and accommodates various kinds of queries [23]. Many attempts are known that have tried to amalgamate top-\(k\) queries and skylines so as to obtain the most out of these tools [3, 15].  
Partitioning schemes similar to those that we have used in this paper have been successfully employed also for the computation of indicators of the strength of skyline tuples, i.e., numeric values that can be adopted for endowing skyline tuples with further attributes to be used for ranking purposes. These indicators include, e.g., the count of dominated tuples [11] and the best possible rank of a tuple when using a linear scoring function [24]. Several other indicators are introduced in [25], some requiring to build the _convex hull_ of a dataset [26, 27, 28], or to compute complex volumes [29, 30]; one of these indicators, called grid resistance, can be computed through parallel partitioning schemes similar to those discussed in this paper [31].  
Skylines, and even more so flexible skylines, are common components of complex data preparation pipelines involving Machine Learning steps [32, 33, 34, 35] over data collected from sources of various nature, like RFID [36, 37], pattern mining [38], crowdsourcing applications [39], and streaming data [40]. We observe that the optimization offered by  
Figure 11: Effect of the number of cores \(c\) on the execution time incurred by SVE1F (**a**) and POP12 (**b**) on an anticorrelated dataset with \(d=4\) dimensions and size \(N=1\) M. (**a**) Computing ND. (**b**) Computing PO.  
top-\(k\)-based processes, like those available in flexible skylines, is orthogonal to but often integrated with other query optimization opportunities relying on semantic properties of data expressible, e.g., through Query Containment [41; 42; 43; 44] or ontological reasoning [45; 46].