# Parallelizing the Computation of Grid Resistance to Measure the Strength of Skyline Tuples
## 4 Parallel Algorithms
### Partitioning Strategies  
We now review three of the main partitioning strategies available in the literature: grid partitioning, angle-based partitioning, and sliced partitioning. Figure 1 illustrates the different partitioning strategies as applied to a uniformly distributed dataset of 90 tuples with 9 partitions, where different partitions are represented with different colors. Grid partitioning[3] (Grid) partitions the space into a grid of equally sized cells, resulting in a total of \(p=m^{d}\) partitions, where \(d\) denotes the total number of dimensions and \(m\) the number of slices in which each dimension is split. This strategy additionally entails a dominance relationship applied to grid cells (and thus to partitions), which allows us to avoid processing certain partitions completely. We identify a given cell \(c_{i}\) with its _grid coordinates_, \(\langle c_{i}[1],\ldots,c_{i}[d]\rangle\), with \(1\leq c_{i}[j]\leq m\), \(j=1,\ldots,d\). With this, we can introduce grid dominance. **Definition 3** (Grid dominance). : _For grid cells \(c_{i}\) and \(c_{h}\), \(c_{i}\) grid-dominates \(c_{h}\), denoted \(c_{i}\prec_{G}c_{h}\), if, for every dimension \(j,j=1,\ldots,d\), we have \(c_{i}[j]<c_{h}[j]\)._  
If \(c_{i}\) grid-dominates \(c_{h}\), then all tuples in \(c_{i}\) dominate all tuples in \(c_{j}\), so, if \(c_{i}\) is not empty, \(c_{j}\) can be disregarded altogether when computing the skyline. Assigning a partition number, shown in Figure 0(a) for grid partitioning, to a tuple \(t\) can be performed as follows, assuming, for simplicity, all values to be in \([0,1)\):  
\[p(t)=\sum_{i=1}^{d}\lfloor t[A_{i}]\cdot m\rfloor\cdot m^{i-1}\]  
Figure 1: Partitioning strategies illustrated on a uniform dataset. where \(A_{i}\) is the \(i\)-th attribute. As an example of grid dominance that can be seen in the figure, partition 1 grid-dominates partitions 5 and 8. Angle-based partitioning[23] (henceforth, Angular) partitions the space with regard to angular coordinates, after converting Cartesian to hyper-spherical coordinates, which provides a better workload balance across partitions than with Grid. The partition number (shown in Figure 0(b) for Angular) is computed for every tuple \(t\) based on hyper-spherical coordinates, including a radial coordinate \(r\) and \(d-1\) angular coordinates \(\varphi_{1},\ldots,\varphi_{d-1}\), obtained through standard geometric considerations from the Cartesian coordinates. The partition number of \(t\) is then computed as follows:  
\[p(t)=\sum_{i=1}^{d-1}\left\lfloor\frac{2\varphi_{i}}{\pi}m\right\rfloor m^{i-1} \tag{1}\]  
where \(m\) is, again, the number of slices into which each (angular) dimension is divided, which essentially amounts to grid partitioning on angular coordinates. Sliced partitioning[6] (Sliced) first sorts the dataset with respect to one chosen dimension and then (unlike Grid and Angular) determines any given number \(p\) of equi-numerous partitions. The partition number (shown in Figure 0(c) for Sliced) of the \(i\)-th tuple \(t\) in the ordering is simply computed as follows:  
\[p(t)=\left\lfloor\frac{(i-1)\cdot p}{N}\right\rfloor,\]  
where \(N\) is the number of tuples in the dataset. We observe that all the partitioning strategies can be improved by resorting to several optimization opportunities. We reconsider here the so-called _representative filtering_, as presented in [6]. Representative filtering consists of pre-computing a few potentially \"strong\" tuples to be shared across all partitions, since they may have strong potential to dominate other tuples, thus further removing redundant tuples in the local skylines of each partition. A simple technique to select representative tuples consists of choosing the top-\(k\) results according to any given monotone scoring function \(f\) of the dataset's attributes.