# Parallelizing the Computation of Grid Resistance to Measure the Strength of Skyline Tuples
## 5 Results
For instance, with default parameter values (\(N=1\) M and \(d=3\)), the skyline barely consists of two tuples and the computation essentially amounts to 25 dominance tests, i.e., one per tested grid interval value. The situation does not change for other values of \(N\), with \(|\textsc{sky}|\) always less than 5. For this reason, we refrain from considering the COR dataset further. **Varying the number of dimensions \(d\). ** Figure 3 shows how the number of dominance tests varies as the number of dimensions in the synthetic dataset grows. The plots need to use a logarithmic scale since the number of tests grows exponentially, as an effect of the \"curse of dimensionality\". With the ANT datasets (Figure 3a), all partitioning strategies offer significant gains with respect to the plain sequential execution, with savings of up to nearly 80% and never under 60% for \(d>2\). Indeed, when \(d=2\), the skyline consists of only 62 tuples, so the benefits of partitioning are smaller. In particular, Grid is the top performer for \(d\leq 4\), while Angular wins for \(d\geq 5\), although the differences between the best and the worst strategies are always under 5%. The dashed lines indicate the largest number of dominance tests performed in any partition during the parallel phase, while the  
Figure 2: Number of dominance tests incurred by the various partitioning strategies with a default number of partitions (\(p=16\)) and varying dataset sizes on ANT (**a**) and UNI (**b**). solid lines indicate the overall cost of a parallel execution, i.e., by adding to the previous component the number of dominance tests in the final phase. In the case of UNI datasets, the skyline sizes are very small for low \(d\), with as few as \(11\) tuples when \(d=2\). Clearly, parallelizing does not yield benefits in such circumstances. For larger values of \(d\), the gains are more significant, reaching nearly 50% when \(d=6\) with the Sliced strategy, which proves to be the most suitable for this type of dataset in all scenarios, while Grid and Angular reach 26% and 47%, respectively, under the same conditions. We also note that, when there are more partitions than skyline points (as is the case, e.g., with \(d=2\), in which \(p=16>11=\left\lfloor\textsc{SkY}\right\rfloor\)), the partitions in Sliced will have either 0 or 1 points, so no dominance test will ever take place in the parallel phase, which is then completely ineffective. **Varying the number of partitions \(p\). ** Figure 4 shows the effect of the number of partitions on the number of dominance tests. While the partitioning is always beneficial with the ANT datasets (Figure 3(a)), increasing the number of partitions only increases the overhead. This phenomenon is due to two factors: the first one is the relatively small size of the input dataset for the computation of gres, i.e., the size of the skyline of a 3D dataset of 1 M tuples (1022 tuples in our case), which makes it less open to more intense parallelization opportunities; the second reason is that, since the input consists of skyline tuples of the original dataset, for small grid intervals (i.e., for larger values of \(g\) as used in Algorithm 1), the grid projections of these skyline tuples will almost never exit the skyline, so that dominance tests will be ineffective and the final phase will be predominant, as can be clearly seen, e.g., in Figure 3(b). For UNI, these effects do not change but are less visible because of the much smaller skyline size involved (just 78 tuples), which makes Grid and Angular completely ineffective, while Sliced maintains performance on par with or slightly better than that of None. **Varying the number of representatives \(rep\). ** We now measure the effects of the representative filtering technique on the computation of gres by varying the number of representative tuples, \(rep\), with default values for all other parameters for synthetic datasets.