An Efficient MapReduce-based Skyline Query Processing Method with Two-level Grid Blocks

Hyeongcheol Ryu, Sungwon Jung

http://doi.org/10.5626/JOK.2017.44.6.613

Skyline queries are used extensively to solve various problems, such as in decision making, because they find data that meet a variety of user criteria. Recent research has focused on skyline queries by using the MapReduce framework for large database processing, mainly in terms of applying existing index structures to MapReduce. In a skyline, data closer to the origin dominate more area. However, the existing index structure does not reflect such characteristics of the skyline. In this paper, we propose a grid-block structure that groups grid cells to match the characteristics of a skyline, and a two-level grid-block structure that can be used even when there are no data close to the origin. We also propose an efficient skyline-query algorithm that uses the two-level grid-block structure.