# MapReduce Algorithm for Variants of Skyline Queries: Skyband and Dominating Queries
## 2 Related Works  
Skyline query and its variants have been widely used in several multi-criteria decision support applications. [PERSON] et al., who first introduced the skyline query, proposed three basic algorithms for the skyline computation [1]. Those algorithms are known as block-nested-loops (BNL), divide-and-conquer (D&C), and B-tree-based schemes. [PERSON] et al. proposed a sort-filter-skyline (SFS) algorithm, which improved the efficiency of the skyline computation by presorting the database attributes [4]. To optimize the average-case running time, [PERSON] et al. proposed linear elimination sort for skyline (LESS) algorithm [5]. To filter the dominated objects efficiently through recursively partitioning the dataset based on the nearest objects, [PERSON] proposed the nearest neighbor (NN) algorithm for computing the skyline [6]. On the other hand, instead of computing skyline from the original objects' attributes, several algorithms have proposed to use the index of the objects' attributes for computing skyline. [PERSON] et al. has proposed two progressive algorithms to compute skyline based on attributes' bitmap and index [7]. The recent state-of-the-art algorithm is the _Branch-and-Bound Skyline\((BBS)\)_, proposed by [PERSON] et al., which is shown to be I/O optimal for computing skylines on datasets indexed by R-trees [3]. Meanwhile, various approaches have been proposed for effective skyline querying from the high dimensional dataset. [PERSON] et al. proposed a _skycube_ structure to reduce the cost of skyline computation over all possible subspaces [8]. Later, [PERSON] et al. revised the _skycube_ structure and proposed CSC structure as a more promising alternative for removing identical skyline objects in the _skycube_ by storing each skyline object only to its minimum-subspace [9]. As a variant of the skyline query, [PERSON] et al. introduced the concept of top-\(k\) frequent skyline queries [10]. They suggested that a metric, called _skyline frequency_, can be used to rank and select skyline objects by their interesting-ness. [PERSON] et al. proposed a data-cube structure to speed up the query evaluation by analyzing the dominance relationship [11]. On the other hand, [PERSON] et al. have considered extracting k most representative skyline objects [12]. They have introduced the concept of a representative object by the population it dominates. According to their definition, a skyline object is more representative than other skyline objects, when it dominates more objects than others. [PERSON] et al. illustrated \(k\)-dominant skyline based on the measure of the \(k\)-dominance relationship. The \(k\)-dominant skyline query can control the number of retrieved objects by changing \(k\). If we set a larger \(k\) value, an object more likely to be dominated by another object. They developed specialized algorithms to compute the \(k\)-dominant skyline [13]. \(K\)-skyband query, which is another variant of skyline query, selects those objects which are dominated by at most (\(K\)-1) other objects. It has been noticed that, for any increasingly monotone aggregate function, the top-\(k\) objects belong to the k-skyband, where \(k\leq K\)[3,14]. There exist more spontaneous techniques for skyline query formalization. [PERSON] et al. proposed \(n\)-of-\(N\) skyline query to support online query on data streams, i.e., to find the skyline of the set composed from the most recent \(n\) elements. The proposed method considers a very widely distributed dataset, which is impossible to process in a centralized fashion [15]. [PERSON] et al. has also investigated skyline computation over a vertically distributed database [16]. [PERSON] et al. examined skyline query in arbitrary subspaces [17]. [PERSON] et al. studied on dynamic skyline query [18]. [PERSON] et al. proposed the reverse skyline query, which selects the number of users who like the given object most based on the dominance relationship among the objects [19].