# Parallelizing the Computation of Grid Resistance to Measure the Strength of Skyline Tuples
## 3 Preliminaries  
We refer to datasets consisting of numeric attributes. Without loss of generality, the domain that we consider is the set of non-negative real numbers \(\mathbb{R}^{+}\). A schema \(S\) is a set of attributes \(\{A_{1},\ldots,A_{d}\}\), and a tuple \(t=\langle v_{1},\ldots,v_{d}\rangle\) over \(S\) is a function associating each attribute \(A_{i}\in S\) with a value \(v_{i}\), also denoted as \(t[A_{i}]\), in \(\mathbb{R}^{+}\); a relation over \(S\) is a set of tuples over \(S\).  
A _skyline_ query [1] takes a relation \(r\) as input and returns the set of tuples in \(r\) that are dominated by no other tuples in \(r\), where dominance is defined as follows.  
Definition 1: Let \(t\) and \(s\) be tuples over a schema \(S\); \(t\) _dominates_\(s\), denoted \(t\prec s\), if, for every attribute \(A\in S\), \(t[A]\leq s[A]\) holds and there exists an attribute \(A^{\prime}\in S\) such that \(t[A^{\prime}]<s[A^{\prime}]\) holds. The _skyline_\(\textsc{Sky}(r)\) of a relation \(r\) over \(S\) is the set \(\{t\in r\mid\
exists s\in r\). \(s\prec t\}\).  
We shall consider attributes such as \"cost\", where smaller values are preferable; however, the opposite convention would also be possible.  
A tuple can be associated with a numeric score via a _scoring function_ applied to the tuple's attribute values. For a tuple \(t\) over a schema \(S=\{A_{1},\ldots,A_{d}\}\), a scoring function \(f\) returns a score \(f(t[A_{1}],\ldots,t[A_{d}])\in\mathbb{R}^{+}\), also indicated as \(f(t)\). As for attribute values, we set our preference for lower scores (but the opposite convention would also be possible).  
Although skyline tuples are unranked, they can be associated with extra numeric values by computing appropriate indicators and ranked accordingly. To this end, we consider a robustness indicator.  
The indicator called _grid resistance_, denoted as \(\mathsf{gres}(t;r)\), measures how robust skyline tuple \(t\) is with respect to a perturbation of the attribute values of the tuples in \(r\), i.e., whether \(t\) would remain in the skyline. In [20], this is achieved by restricting the tuple values to a grid divided into \(g\) equally sized intervals in each dimension: the more a skyline tuple resists larger intervals, the more robust it is. The _grid projection_\(\mathsf{gproj}(t,g)\) of \(t\) on the grid is defined as \(\mathsf{gproj}(t,g)=\left\langle\frac{|t|\|_{S}}{g},\ldots,\frac{|t|\{g,g\}} {g}\right\rangle\), and this corresponds to the lowest-value corner of the cell that contains \(t\). When tuples are mapped to their grid projections, we obtain a new relation \(\mathsf{gproj}(r,g)=\{\mathsf{gproj}(t,g)\mid t\in r\}\), in which new dominance relationships may occur. The _grid resistance_\(\mathsf{gres}(t;r)\) of \(t\) is the smallest value of \(g^{-1}\) for which \(t\) is no longer in the skyline.  
Definition 2: Let \(r\) be a relation and \(t\in\textsc{Sky}(r)\). The grid resistance \(\mathsf{gres}(t;r)\) of \(t\) in \(r\) is \(\min_{g\in\mathbb{N}^{+}}\{g^{-1}\mid\mathsf{gproj}(t,g)\
otin\textsc{Sky}( \mathsf{gproj}(r,g))\}\). We set \(\mathsf{gres}(t;r)=1\) if \(t\) never exits the skyline.