Simultaneous Processing of Multi-Skyline Queries with MapReduce

Junsu Kim, Kyong-Ha Lee, Myoung-Ho KimIEICE Trans. Information and Systems 2017 · OpenReview

Abstract

With rapid increase of the number of applications as well as the sizes of data, multi-query processing on the MapReduce framework has gained much attention. Meanwhile, there have been much interest in skyline query processing due to its power of multi-criteria decision making and analysis. Recently, there have been attempts to optimize multi-query processing in MapReduce. However, they are not appropriate to process multiple skyline queries efficiently and they also require modifications of the Hadoop internals. In this paper, we propose an efficient method for processing multi-skyline queries with MapReduce without any modification of the Hadoop internals. Through various experiments, we show that our approach outperforms previous studies by orders of magnitude.

Introduction

Skyline queries are essential tools for multi-criteria decision analysis, identifying data points that are not "dominated" by any other point across multiple dimensions (e.g., finding products that are both cheaper and better-rated). As datasets grow to petabyte scales, executing these queries efficiently within distributed frameworks like MapReduce becomes critical.

Traditional MapReduce implementations often process multiple queries by either running separate jobs—leading to redundant data scans—or sharing a single scan but failing to optimize the subsequent computation and shuffle phases. Furthermore, many existing optimizations require intrusive modifications to Hadoop's core, hindering their adoption in standard production environments. This paper introduces SH-adv (Skyline Handler - advanced), a method designed to process multiple skyline queries simultaneously using "vanilla" MapReduce.

The SH-adv Methodology

The proposed SH-adv approach optimizes multi-skyline processing through a two-stage MapReduce workflow preceded by a preprocessing step.

1. Preprocessing and Fragmentation

The system first analyzes the ranges of all concurrent queries to divide the multi-dimensional data space into disjoint fragments. For instance, overlapping price ranges like [$30, $70] and [$40, $80] are decomposed into three non-overlapping segments: [$30, $40), [$40, $70), and [$70, $80]. A mapping table (FMAP) is then constructed to associate each fragment with its corresponding queries.

2. Fragment-level Processing (1st MR Job)

Instead of computing a skyline for each query immediately, the first MapReduce job calculates the skyline for each individual fragment. Since fragments are disjoint, each data point is processed exactly once, significantly reducing the volume of data passed to the shuffle phase by discarding dominated points early.

3. Query-level Processing (2nd MR Job)

The final step merges the pre-computed fragment skylines to produce the result for each query. This leverages the "skyline of skylines" property: the skyline of a set is equivalent to the skyline of the union of the skylines of its subsets.

The SH-adv workflow, illustrating the use of FMAP and the two-stage MapReduce process.

Experimental Evaluation

The researchers evaluated SH-adv against a "Naive" approach (separate jobs) and "SH-scan" (shared scan but separate computations) using synthetic datasets up to 80GB (240 million tuples) across 2 to 5 dimensions. Tests were conducted on an 11-node Hadoop cluster.

Key Results

The experiments demonstrated that SH-adv provides massive performance gains. In scenarios with 80 concurrent queries, SH-adv achieved a speedup of approximately 1,410% over the naive approach. This efficiency stems from a drastic reduction in the shuffle volume; while baseline methods generate redundant outputs proportional to query overlap, SH-adv's output scale is logarithmic relative to the overlap.

Execution time comparison showing SH-adv's superior scalability as the number of concurrent queries increases.

Conclusion

SH-adv offers a highly efficient, "plug-and-play" solution for multi-skyline query processing in standard MapReduce environments. By eliminating redundant scans and computations through space fragmentation, it achieves order-of-magnitude speedups. Future work will address performance on anti-correlated datasets, where fragment skylines remain large, by developing advanced "thinning" techniques to prune non-essential tuples earlier in the pipeline.

Summary updated

Abstract

With rapid increase of the number of applications as well as the sizes of data, multi-query processing on the MapReduce framework has gained much attention. Meanwhile, there have been much interest in skyline query processing due to its power of multi-criteria decision making and analysis. Recently, there have been attempts to optimize multi-query processing in MapReduce. However, they are not appropriate to process multiple skyline queries efficiently and they also require modifications of the Hadoop internals. In this paper, we propose an efficient method for processing multi-skyline queries with MapReduce without any modification of the Hadoop internals. Through various experiments, we show that our approach outperforms previous studies by orders of magnitude.
BibTeX
@article{kim2017simultaneous,
  author = {Junsu Kim and Kyong-Ha Lee and Myoung-Ho Kim},
  title = {{Simultaneous Processing of Multi-Skyline Queries with MapReduce}},
  journal = {IEICE Trans. Information and Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=gK1sPdOpOz},
}
Figure