# Parallelizing the Computation of Grid Resistance to Measure the Strength of Skyline Tuples
## 5 Results
Figure 5 clearly shows that representative filtering is overall ineffective: in almost all considered  
Figure 4: Number of dominance tests as the number of partitions varies on ANT (**a**) and UNI (**b**) 3D datasets with \(N=1\) M tuples. Figure 3: Number of dominance tests with a default number of partitions (\(p=16\)) as the number of dimensions varies on ANT (**a**) and UNI (**b**) datasets with \(N=1\) M tuples. scenarios, using representatives only overburdens the parallel phase with additional dominance tests, without actually significantly reducing the union of local skylines. Again, this is due to the fact that grid projections of skyline points are very likely to remain non-dominated, especially for smaller grid sizes, so that the pruning power of representative tuples fades. The only case where a small advantage emerges is with SLiced on ANT with \(rep=1000\), which determines a minor \(5\%\) decrease in the number of dominance tests with respect to the case with no representatives. We also observe that a target number of representatives corresponds to a smaller average number of actually non-dominated tuples; for instance, on ANT, only 3.88 tuples are non-dominated, on average, out of 10 selected representatives, and only 132.36 out of 1000. **Real datasets. ** Figure 6 shows how the number of dominance tests varies depending on the partitioning strategy on different real datasets. Figure 5(a) shows the three datasets with smaller skyline sizes, EMP, NBA, and HOU, whose skyline sizes are, respectively, 14, 14, and 16. Note that, while NBA is a small dataset, the other two are much larger, but their tuples are correlated, thus causing a smaller skyline. Figure 5(b) shows what happens with real datasets with larger skylines: SEN has 1496 tuples in its skyline, while RES has 8789. The results shown in the figure confirm what was found in the synthetic datasets: for the smaller cases, ANGular and Grid do not yield benefits, while SLiced essentially has no parallel phase, thereby coinciding with or slightly improving over None. With the larger datasets, the gains are at least 35% with all strategies on SEN and at least 29% on RES, with peak improvements of 50% on SEN by ANGular and 64% on RES by SLiced. **Execution times. ** In order to analyze the concrete execution time required to complete the computation of gres using the different partitioning strategies, we focus on ANT and RES, i.e., the most challenging synthetic and real datasets, respectively. Figure 7 shows stacked bars reporting the breakdown of the execution time for the various partitioning strategies with two components: the time needed to complete the parallel phase (the lower part of the bar, shown in a lighter color) and the rest of the time (the upper part), including the final, sequential phase and the additional overhead caused by the coordination of the execution over multiple cores. In our execution setting, computing gres for all the tuples in the skyline of ANT with the default parameter values (Figure 6(a)) requires 0.01s with a plain, sequential  
Figure 5: Number of dominance tests with a default number of representatives (\(rep=16\)) as the number of partitions varies on ANT (**a**) and UNI (**b**) 3D datasets with \(N=1\) M tuples. Figure 6: Number of dominance tests with real datasets. implementation, in which the skyline is computed through a standard SFS algorithm [25]. Parallelization starts to yield benefits with just two cores with Angular and Sliced, while it takes at least four cores for Grid to surpass None. With 16 cores, all strategies find the result in less than half the time required by None. We observe that, while all partitioning strategies improve as the number of cores grows, Sliced improves very little after eight cores, since its parallel phase, for this dataset, is already very light when compared to the final phase.