# MapReduce Algorithm for Variants of Skyline Queries: Skyband and Dominating Queries
## 1 Introduction  
The utilization of large data repositories is a crucial factor in improving various types of businesses. Such a kind of massive data repositories is defined as \"big data\". Extracting the skyline objects is a vital task for understanding the dataset in the early stage of the knowledge discovery process from large data repositories. Skyline objects in a database are objects that are not dominated by any other object in the database and the skyline query [1] is a function to find a set of skyline objects. Given an \(m\)-dimensional dataset \(DS\), an object \(O_{i}\) is said to be in the skyline of \(DS\) if there is no other object \(O_{j}\) (\(i\
eq j\)) in \(DS\) such that \(O_{j}\) is better than \(O_{i}\). If there exists such an \(O_{j}\), then we say that \(O_{i}\) is dominated by \(O_{j}\), or \(O_{j}\) dominates \(O_{i}\). Figure 1 presents an example skyline. The table in the figure contains a list of hotels, each of which has two numerical attributes: distance and price. If we assume that a smaller value is better, then the skyline query retrieves objects \(\{O_{2},O_{3},O_{7}\}\) as in Figure 0(b). Objects \(O_{1}\) and \(O_{5}\) are dominated by object \(O_{2}\). Objects \(O_{4}\) and \(O_{6}\) are dominated by object \(O_{3}\). Top-\(k\) dominating query [2] is a variant of the skyline query. In the query, a scoring function \(\mu(O)\) is used for evaluating strongness of an object \(O\in DS\): \(\mu(O)=\ \mid\{O^{\prime}\in DS\ \mid O\prec O^{\prime}\}\mid.\)  
The scoring function \(\mu(O)\) returns how many objects the object \(O\) dominate in the dataset. In the above example, \(\mu(O_{2})=2\) because \(O_{2}\) dominates two objects: \(O_{1}\) and \(O_{5}\). Similarly, \(\mu(O_{3})=2\). The top-\(k\) dominating query selects \(k\) objects based on \(\mu(O)\). For example, a top-2 dominating query for the example in Figure 1 retrieves \(O_{2}\) and \(O_{3}\). The skyband query, also known as \(K\)-skyband query [3], is another well known variant of the skyline query. A \(K\)-skyband query returns a set of objects, each object of which is not dominated by \(K\) other objects. For the dataset in Figure 1a, the skyband query for \(K=2\) retrieves objects \(\{O_{1},O_{2},O_{3},O_{4},O_{7}\}\). Object \(O_{5}\) is not in the skyband because it is dominated by two objects: \(O_{2}\) and \(O_{1}\). Similarly, object \(O_{6}\) is not in the skyband result because it is also dominated by two objects: \(O_{3}\) and \(O_{4}\). We illustrate this procedure in Figure 2.  
As mentioned above, recent \"big data\" is too large to analyze intensively. Instead of analyzing raw big data, we propose using a relatively small subset, i.e., the results of skyband and dominating queries that contain the important features of the raw data. However, conventional algorithms for computing such skyline variants are not designed for parallel distributed environments. In recent years, the MapReduce framework has been applied for parallel processing of huge amounts of data on large-size clusters of commodity computers in a reliable manner. MapReduce and Hadoop, which is a popular open source variant of MapReduce, has attracted significant research attention. Our parallel algorithm utilizes the MapReduce framework. In this paper, we propose a MapReduce algorithm, i.e., a parallel algorithm that simultaneously computes skyband and dominating query. Figure 1: Skyline example. Figure 2: Skyband example. The contributions of this paper can be summarized as follows:  
* We examine the skyband and dominating queries for processing \"big data\". * We develop a scalable parallel algorithm to compute the queries. The proposed algorithm simultaneously computes skyband and dominating queries. Exploiting the MapReduce framework for the skyband as well as dominating queries is an innovative approach that utilizes the advantage of parallel distributed computing environment.