# MapReduce Algorithm for Variants of Skyline Queries: Skyband and Dominating Queries
## 3 Preliminaries  
Consider an \(m\)-dimensional dataset \(DS\)\(\{a_{1},a_{2},\cdots,a_{m}\}\). We assume that the dataset is distributed into \(n\) subsets \(\{DS_{1},DS_{2},\cdots,DS_{n}\}\) in different locations. Without loss of generality, we assume that the dataset contains non-negative numerical values. We also assume that smaller values are preferable in each dimension/attribute. \(O_{i,j}.a_{p}\) denotes that the \(p\)-th dimension's/attribute's value for object \(O_{i,j}\), where \(i,j\) is an object \(ID\) which means object \(j\) in dataset \(i\) (\(DS_{i}\)). Assume that the dataset \(DS\) shown in Figure 1 is distributed into three subsets, \(DS_{1},DS_{2}\), and \(DS_{3}\), each of which has two attributes, \(a_{1}\) and \(a_{2}\), as shown in Table 1.  
**Definition 1**. : _(Dominance) For two objects \(O\) and \(O^{\prime}\), object \(O\) is said to dominate object \(O^{\prime}\), denoted \(O\prec O^{\prime}\), if \(O.a_{s}\leq O^{\prime}.a_{s}\) for all attributes (\(s=1,\cdots,m\)) and \(O.a_{s}<O^{\prime}.a_{s}\) for at least one attribute (\(1\leq x\leq m\))._  
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & \(DS_{1}\) & \multicolumn{4}{c}{\(DS_{2}\)} & \multicolumn{4}{c}{\(DS_{3}\)} \\ \hline ID & \(a_{1}\) & \(a_{2}\) & ID & \(a_{1}\) & \(a_{2}\) & ID & \(a_{1}\) & \(a_{2}\) \\ \hline \(O_{1,1}\) & 3 & 8 & \(O_{2,1}\) & 7 & 3 & \(O_{3,1}\) & 5 & 10 \\ \(O_{1,2}\) & 2 & 7 & \(O_{2,2}\) & 8_We refer to such an \(O\) as a dominant object and such a \(O^{\prime}\) as \(A\) dominated object. If \(O\) dominates \(O^{\prime}\), then \(O\) is preferable to \(O^{\prime}\)._  
In Table 1, object \(O_{1,2}\) dominates object \(O_{1,1}\) (\(O_{1,2}\prec O_{1,1}\)). This is because object \(O_{1,2}\) has a smaller value for both attributes than object \(O_{1,1}\). **Definition 2**. : _(Skyline) An object \(O\in DS\) is in a skyline of \(DS\) (i.e., a skyline object in \(DS\)) if \(O\) is not dominated by any other object in \(DS\). The skyline of \(DS\), denoted \(Sky(DS)\), is the set of skyline objects in \(DS\). For the dataset \(DS\), objects \(O_{1,2}\), \(O_{2,1}\), and \(O_{3,3}\) can dominate all other objects and are not dominated by any other object. Therefore, a skyline query on dataset \(DS\) will retrieve \(Sky(DS)=\{O_{1,2},O_{2,1},O_{3,3}\}\)._  
**Definition 3**. : _(The \(\mu\) score) The \(\mu\) score of an object shows how many objects the object dominate in the dataset. We use \(\mu(O)\) to denote the \(\mu\) score of an object \(O\). In Table 1, object \(O_{1,2}\) dominates objects \(O_{1,1}\) and \(O_{3,1}\). Therefore, the \(\mu\) score of \(O_{1,2}\) is 2 (i.e., \(\mu(O_{1,2})=2\))._  
**Definition 4**. : _(The \(SB\) score). The \(SB\) score of an object is the number of objects dominating that object. We use \(SB(O)\) to denote the \(SB\) score of an object \(O\). In Table 1, object \(O_{3,2}\) is dominated by objects \(O_{2,1}\) and \(O_{2,2}\). Therefore, the \(SB\) score of \(O_{3,2}\) is 2 (i.e., \(SB(O_{3,2})=2\))._  
**Definition 5**. : _(Dominating query) Given a positive integer \(k\) and a dataset \(DS\), the top-\(k\) dominating query returns the \(k\) objects that have the top-\(k\)\(\mu\) scores in \(DS\). For the dataset in Table 1, a top-two dominating query retrieves \(O_{1,2}\) and \(O_{2,1}\)._  
**Definition 6**. : _(Skyband query) Given a positive integer \(K\), the \(K\)-skyband is the set of objects that are not dominated by \(K\) other objects. For the dataset \(DS\) in Table 1, the skyband query for \(K=2\) retrieves objects \(\{O_{1,1},O_{1,2},O_{2,1},O_{2,2},\text{and }O_{3,3}\}\). Intuitively, \(K\) represents the thickness of the skyline. A \(1\)-skyband query is the same as a conventional skyline query._  
**Definition 7**. : _(Worst rank) For an object \(O\), assume \(r_{1}(O)\) and \(r_{2}(O)\) are the rank values of attributes \(a_{1}\) and \(a_{2}\), respectively. For example, in Figure 1, \(r_{1}(O_{4})=6\) and \(r_{2}(O_{4})=2\).