MapReduce Skyline Query Processing with A New Angular Partitioning Approach

被引：21
作者：
Chen, Liang [1 ]
Hwang, Kai [2 ]
Wu, Jian [1 ]
机构：
[1] Zhejiang Univ, Hangzhou 310003, Zhejiang, Peoples R China
[2] Univ So Calif, Los Angeles, CA USA
来源：
2012 IEEE 26TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS & PHD FORUM (IPDPSW) | 2012年
基金：
中国国家自然科学基金;
关键词：
Web services; skyline query processing; MapReduce; Hadoop programming; WEB; EFFICIENT; ALGORITHMS; SELECTION;
D O I：
10.1109/IPDPSW.2012.279
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Fast skyline selection of high-quality web services is of critically importance to upgrade e-commerce and various cloud applications. In this paper, we present a new MapReduce Skyline method for scalable parallel skyline query processing. Our new angular partitioning of the data space reduces the processing time in selecting optimal skyline services. Our method shortens the Reduce time significantly due to the elimination of more redundant dominance computations. Through Hadoop experiments on large server clusters, our method scales well with the increase of both attribute dimensionality and data-space cardinality. We define a new performance metric to assess the local optimality of selected skyline services. By experimenting over 10,000 real-life web service applications over 10 performance attribute dimensions, we find that the angular-partitioned MapReduce method is 1.7 and 2.3 times faster than the dimensional and grid partitioning methods, respectively with a higher probability to reach the local optimality. These results are very encouraging to select optimal web services in real-time out of a large number of web services.
引用
收藏
页码：2262 / 2270
页数：9
相关论文
共 33 条
  • [1] A-Masri E, 2007, IEEE IC COMP COM NET, P529
  • [2] Al-Masri Eyhab., 2007, Proceedings of the 16th international conference on World Wide Web, P1257, DOI DOI 10.1145/1242572.1242795
  • [3] Alrifai Mohammad, 2010, P 19 INT C WORLD WID, P11, DOI DOI 10.1145/1772690.1772693
  • [4] [Anonymous], 2010, P 19 ACM INT S HIGH, DOI DOI 10.1145/1851476.1851593
  • [5] [Anonymous], 2003, SIGECOM EXCH
  • [6] Balke WT, 2004, LECT NOTES COMPUT SC, V2992, P256
  • [7] The Skyline operator
    Börzsönyi, S
    Kossmann, D
    Stocker, K
    [J]. 17TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING, PROCEEDINGS, 2001, : 421 - 430
  • [8] Candan K. S., 2011, P 14 INT C EXT DAT T, V11, P574
  • [9] Cardellini V, 2007, 2007 IEEE INTERNATIONAL CONFERENCE ON WEB SERVICES, PROCEEDINGS, P743
  • [10] Dean J, 2004, USENIX ASSOCIATION PROCEEDINGS OF THE SIXTH SYMPOSIUM ON OPERATING SYSTEMS DESIGN AND IMPLEMENTATION (OSDE '04), P137
1234