# Partitioning Strategies for Parallel Computation of Flexible Skylines
## 4 Parallel Computation of Flexible Skylines  
A general scheme for parallelizing the computation of flexible skylines is based on the idea that the dataset can be partitioned and each partition is processed independently and in parallel. This produces a \"local\" result; the union of all local results still has some redundancies that can be eliminated by applying a last (sequential) round of removal. This approach has been described for skylines, e.g., in ([PERSON] and others, 2016; 2017), and is correct since when \(r=r_{1}\cup\ldots\cup r_{p}\), with \(r_{i}\cap r_{j}=\emptyset\) for \(i\
eq j\), we have \(\textsc{Sky}(r)=\textsc{Sky}(\textsc{Sky}(r_{1})\cup\ldots\cup\textsc{Sky}(r_ {p}))\). A similar principle applies to \(\mathcal{F}\)-skylines by replacing in the above formula \(\textsc{Sky}(\cdot)\) with \(\textsc{ND}(\cdot;\mathcal{F})\) or \(\textsc{PO}(\cdot;\mathcal{F})\).  
The algorithmic pattern in Algorithm 1 performs this in three phases: first, \(r\) is partitioned into \(r_{1},\ldots,r_{p}\) (line 2), with possible meta-information to be used later; then, (local) results are computed independently (line 3) and in parallel, possibly using the meta-information; finally, all the local results are merged (line 4) and processed sequentially (line 5).  
```
In: relation \(r\), functions \(\mathcal{F}\) via constraints \(\mathcal{C}\), number of partitions \(p\)  Out: a flexible skyline \(\textsc{ND}(r;\mathcal{F})\) or \(\textsc{PO}(r;\mathcal{F})\) \(ls:=\emptyset\)// the local result \((r_{1},\ldots,r_{p},meta):=\texttt{Partition}(r,p)\)// partitions and meta-information \((r_{1},\ldots,r_{p},meta):=\texttt{Partition}(r,p)\)// partitions and meta-information \((r_{1},\ldots,r_{p},meta)\) \(ls:=ls\cup\texttt{ComputeLocalSet}(r_{i},meta)\) \((r_{1},\ldots,r_{p})\) return \(\textsc{ND}(ls;\mathcal{F})\) or \(\textsc{PO}(ls;\mathcal{F})\)
```  
**Algorithm 1**Algorithmic pattern for parallel skyline computation  
We shall adopt for flexible skylines the main partitioning strategies used in the literature for computing skylines, which are summarized next: Grid Partitioning, Angular Partitioning, and Sliced Partitioning. We refrain from considering Random Partitioning (2017), which simply randomly distributes the tuples across the various partitions, and is therefore too simple a baseline to receive further attention.  
We also observe that parallelizing the computation of flexible skylines may pose additional challenges with respect to classical skylines. Load imbalance may arise from the notion of \(\mathcal{F}\)-dominance, which makes it harder to predict how many points in each partition will need comparison, leading to potential workload skew and inefficiencies, even in the presence of balanced data distributions across partitions. While standard skyline computation can be efficiently parallelized by assigning independent partitions and merging partial results, the computation of flexible skylines might experience increased inter-partition dependencies, since \(\mathcal{F}\)-dominance relations may depend on non-local tuples, increasing the need for communication and synchronization between computing nodes. In Section 4.2 we will propose improvements over classical partitioning strategies that help to mitigate these risks.  
A parallel computation of skyline-based operators works best typically with high-dimensional, large-scale datasets that exhibit diverse attribute values. Clearly, a small-scale dataset receives little benefits from parallelization, because these would be exceeded by the overheads due to coordination. High-dimensional data typically ensure a certain degree of sparsity, which, in turn, allows for an even distribution of data in each partition. However, the Sliced partitioning strategy, proposed below, allows for forcing this characteristic in any data distribution, including anticorrelated data.