# Parallelizing the Computation of Grid Resistance to Measure the Strength of Skyline Tuples
## 5 Results
Before starting the experiments, we observe that, while the exact determination of gres would require determining \(\ell\) as in line 2 of Algorithm 1 and its inverse \(\hat{g}\), the actual value of \(\ell\) may be impractically small. Bearing in mind that the aim of the gres indicator is to determine the tuples that are \"strong\" with regard to grid resistance, and that, for very small values of \(\ell\), the corresponding value of gres would be insignificant, we choose to move to a more practical option. Therefore, instead of looking for the smallest non-zero difference (in absolute value) between any two values on the same attribute in the dataset, we simply set \(\hat{g}=25\) as a reasonable threshold of significance for the number of grid intervals. **Varying the dataset size \(N\). ** Our first experiment focuses on the effect of the dataset size on the number of dominance tests needed to compute the result, while keeping all the other operating parameters to their default values, as indicated in Table 1. Figure 1(a) focuses on ANT and reports stacked bars for each of the partitioning strategies, in which the lower part refers to the largest number of dominance tests performed in any partition during the parallel phase, while the top part indicates the number of dominance tests performed during the final phase. We observe that, up to \(N=1\) M, all partitioning strategies are \begin{table}
\begin{tabular}{l l} \hline \hline
**Full Name** & **Tested Value** \\ \hline Distribution & synthetic: ANT, UNI; real: NBA, HOU, EMP, RES, SEN \\ Synthetic dataset size (\(N\)) & 100 K, 500 K, **1 M**, 5 M, 10 M \\ \# of dimensions (\(d\)) & 2, **3**, 4, 5, 6, 7 \\ \# of partitions (\(p\)) & **16**, 32, 64, 128 \\ \# of representatives (\(rep\)) & **0**, 1, 10, 100, 1000 \\ \# of cores (\(c\)) & 2, 4, 8, **16** \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Operating parameters for testing of efficiency (defaults in bold). beneficial with respect to no partitioning (indicated as None), with Angular as the most effective strategy and Sliced as the strategy with the lowest parallel costs, due to the ideal balancing of the number of tuples in each partition. For larger sizes, however, Grid becomes less effective, Angular is on par with None, and Sliced becomes the most effective strategy. This is due to the non-monotonic behavior with respect to the number of skyline points: for a growing dataset size, the size of the skyline typically also grows; however, when we move from \(N=1\) M to \(N=5\) M, there is a fall from 1022 to only 527 tuples in \(|\textsc{Sky}|\). This is due to the fact that the larger dataset, besides containing more tuples, also includes some very strong tuples that dominate most of the remaining ones. A similar effect is observed for \(N=10\) M, for which the skyline size only grows to 650 tuples and is therefore smaller than with \(N=1\) M and actually even smaller than with \(N=500\) K (where \(|\textsc{Sky}|=940\)) \(N=100\) K (where \(|\textsc{Sky}|=719\)). These numbers refer to one of our exemplar instances, but similar behaviors, which are due to the way in which the data are generated (we adopted the widely used synthetic data generator proposed by the authors of [1]), are nonetheless common to all five repetitions of the experiments that we describe. Figure 2b shows the stacked bars for the UNI dataset. Here, the benefits of parallelization are essentially lost, at least for Grid and Angular, due to the extremely small skyline sizes that occur with uniform distributions (varying from 75 tuples for \(N=100\) K to 101 for \(N=10\) M). The Sliced partitioning strategy manages to still offer slight improvements with respect to None by performing very little removal work during the parallel phase; therefore, the final phase is only slightly lighter than with None. An even more extreme situation occurs with the COR dataset, for which the skyline sizes are so small that the benefits of parallelism are completely nullified.