# Parallelizing the Computation of Grid Resistance to Measure the Strength of Skyline Tuples
## 7 Conclusions  
In this paper, we tackled the problem of assigning and computing a value of strength to skyline tuples, so that these tuples can be ranked and selected accordingly. In particular, we have focused on a specific indicator of robustness, called grid resistance, that measures the amount of value quantization that can be tolerated by a given skyline tuple for it to continue to be part of the skyline. Based on now consolidated algorithmic patterns that exploit data partitioning for the computation of skylines, we reviewed the main partitioning strategies that may be adopted in parallel environments (Grid, Angular, Sliced), as well as a common optimization strategy that can be used on top of this (representative filtering), and devised an algorithmic scheme that can be used to also compute the grid resistance on a partitioned dataset.  
We conducted an extensive experimental evaluation on a number of different real and synthetic datasets and studied the effect of several parameters (dataset size, number of dimensions, data distribution, number of partitions, and number of representative tuples) on the number of dominance tests that are ultimately required to compute the grid resistance. Our results showed that all partitioning strategies may be beneficial, with Grid often reaching lower levels of effectiveness than Angular and Sliced. We have observed that the specific problem at hand, in which one only manages skyline (i.e., inherently strong) tuples, makes representative filtering ineffective and suggests to not over-partition the dataset. Indeed, the relatively low value that we used as the default for the number of partitions (\(p=16\)) also proved to be a good choice from a practical point of view. Our experiments on the execution time as the number of available cores varied confirmed the objective findings on the number of dominance tests and showed that, even with the limited parallelization opportunities offered by a single machine, the use of partitioning strategies may improve the performance by more than 50%, suggesting that there is room for further improvements with an increased number of available cores.  
Our results also show the remarkable impact of the dataset characteristics (namely, the data distribution) on the performance. In particular, smaller or uniformly distributed datasets hardly benefit from the parallelized approach, since the problem size does not lend itself well to partitioning--an effect that is exacerbated in the case of correlated datasets. Anti-correlated datasets, according to our experiments, offer the most tangible improvements when exploiting partitioning.  
While parallel processing does not lower the asymptotic computational complexity of the problem, which remains quadratic in the dataset size (and linear in the number of grid intervals to be tested, i.e., in the desired precision of the resulting grid resistance value), substantial gains can be experienced in practice, as we observed, in terms of both the overall dominance tests and the execution times.  
No fair comparison with other approaches can be carried out at this time since, to the best of our knowledge, ours is the first parallel proposal for the computation of gres. The sketchy sequential pattern described in [20] essentially corresponds to no partitioning (the None strategy), which has been thoroughly analyzed and extensively compared with our approach in Section 5.  
Future work will try to adapt or revisit the techniques used in this paper to the computation of other notions that are built on top of dominance. These include, e.g., skyline variants, based on modified notions of dominance, as well as other indicators of the strength of skyline tuples, either novel or already proposed in the pertinent literature.  
This research received no external funding.