# Partitioning Strategies for Parallel Computation of Flexible Skylines
## 5 Experiments
We do not include results regarding Grid here, because, for solving LP problems of this size, we need partitions to be as balanced as possible, while Grid produces extremely unbalanced partitions (especially with anticorrelated data), with consequently very poor results. Figure 5a shows the times required to compute PO starting from ND by using POPI2 (the time to compute ND is thus not included in the total). We observe that, in this case, Sliced performs much more poorly than Angular, and this, although Sliced, still incurs lower execution times during the parallel phase, as shown in Figure 5b. The reason is that the partitioning along one single dimension effected by Sliced is not particularly efficient at removing tuples during the parallel phase, as Figure 6 shows, with Angular removing as many as 85% of the tuples with a 4d anticorrelated dataset with 2 M tuples, while Sliced only attains 62% in that case. To be precise, PO is a very small set compared with ND (with \(|\mathrm{ND}|=16,781\) and \(|\mathrm{PO}|=150\) with the 4d dataset of 2 M tuples), and this might be the source of ineffectiveness of sorting the dataset in one dimension as in Sliced. Figure 5a also shows a comparison with our sequential baseline (a non-parallelized execution with POPI2, indicated as Serial), highlighting significant gains with our parallelized solutions. Table 3 shows the execution times of the parallel and the sequential phase for a 4d dataset with 2 million tuples, highlighting that the Sliced strategy incurs a very high overhead in the sequential phase due to a much worse ability to remove tuples during the parallel phase, with more than three times as many tuples remaining with the Sliced strategy than with the Angular strategy. **Varying size: improved strategies. ** Figure 7 shows the effect of applying the improvements discussed in Section 4.2. Representative Filtering causes slight improvements in terms of execution times with both Sliced and Angular, as can be seen in Figure 6(a) for the computation of ND, where the improved versions are indicated as Sliced+ and Angular+. We also applied the NoSeq scheme on top of the Sliced partitioning strategy (with representatives), which has determined significant improvements in the computation of ND. It turns out that NoSeq largely outperforms the other strategies, with overall execution times that are more than 7 times smaller than the second-best strategy (Sliced+). Grid Filtering, available for Grid partitioning, takes too long to return the local set and is overall disadvantageous in terms of duration compared with the basic version, so we will not consider it any further in the experiments. As for the computation of PO with POP12, Figure 6(b) reports the NoSeq strategy along with Sliced and Angular (representatives prove to be ineffective for computing PO and thus are not reported). We observe that applying the NoSeq scheme on top of Sliced makes it even more efficient than Angular, which was the best option for this kind of problem. In order to complete our analysis as the size varies, we also tested the behavior of the NoSeq strategy with even larger dataset sizes. Figure 8 shows that, from 1 M to 10 M tuples, execution times incurred with NoSeq follow an almost perfectly linear growth with the dataset size, both for ND and for PO, confirming the scalability of the approach. **Varying dimensions. ** Increasing the number of dimensions \(d\) results in a notable rise in execution time due to the significantly larger number of tuples in the output. As the number of dimensions increases, the probability of a tuple being \(\mathcal{F}\)-dominated decreases substantially. Figure 9 illustrates that, for anticorrelated datasets, NoSeq is also affected by the \"curse of dimensionality\", with execution times increasing at a rate greater than linear as the number of dimensions grows. Figure 8: Performance of the NoSeq strategy on an anticorrelated dataset with \(d=4\) dimensions and varying sizes: total execution times for SVE1F and POP12.