基于Flink的k-支配skyline体并行求解算法

计算机工程与科学 ›› 2023, Vol. 45 ›› Issue (01): 17-27.

基于Flink的k-支配skyline体并行求解算法

孙国璋1,2,3，黄山1,2,3，艾力卡木·再比布拉1,2,3，徐浩桐1,2,3，段晓东1,2,3

（1.大连民族大学计算机科学与工程学院，辽宁大连 116600;
2.大数据应用技术国家民委重点实验室(大连民族大学)，辽宁大连116600;
3.大连市民族文化数字技术重点实验室(大连民族大学)，辽宁大连116600）

收稿日期:2022-09-05 修回日期:2022-10-21 接受日期:2023-01-25 出版日期:2023-01-25 发布日期:2023-01-25
基金资助:
国家重点研发计划（2018YFB1004402）

A k-dominant skyline body parallel solving algorithm based on Flink

SUN Guo-zhang1,2,3,HUANG Shan1,2,3 ,ALKAM Zabibul1,2,3,XU Hao-tong1,2,3,DUAN Xiao-dong1,2,3

（1.College of Computer Science and Engineering,Dalian Minzu University,Dalian 116600;
2.State Ethnic Affairs Commission Key Laboratory of Big Data Applied Technology (Dalian Minzu University),Dalian 116600;
3.Dalian Key Laboratory of Digital Technology for National Culture (Dalian Minzu University),Dalian 116600,China)

Received:2022-09-05 Revised:2022-10-21 Accepted:2023-01-25 Online:2023-01-25 Published:2023-01-25

摘要/Abstract

摘要： k-支配skyline算法弱化了数据点之间的支配关系，更适合高维数据。k-支配skyline体适应于多名用户使用k-支配skyline算法查询，而现有的求解算法在时间效率和代码扩展性方面都有待提高。因此，提出了面向多用户的k-支配skyline体求解优化算法MKSSOA，该算法对每名用户的候选集和中间集分别进行存储，同时在k-支配检查过程中利用2集合中数据点出现的先后次序将候选集中的非k-支配skyline点存储到对应用户的中间集中，以便下一名用户筛选使用，这样可以减少数据点之间的比较次数，避免重复计算，从而提升查询效率。同时，提出了面向多用户的k-支配skyline体并行求解算法MKSPSA，通过Apache Flink并行处理框架有效减少了数据点的比较时间。理论研究和实验结果显示，提出的算法具有较高的效率，能很好地处理多用户k-支配skyline问题。

关键词: k-支配, skyline查询, 多用户, Apache Flink, 并行查询

Abstract: The k-dominated skyline algorithm weakens the domination relationship between data points and is more suitable for high-dimensional data. k-dominated skyline bodies are suitable for multiple users to query with the k-dominated skyline algorithm, but the existing solution algorithms need to be improved in terms of time efficiency and code scalability. Therefore, this paper proposes an optimization algorithm for solving k-dominated skyline bodies. This algorithm stores the candidate set and the intermediate set for each user separately, and stores the non-k-dominated skyline points in the candidate set to the intermediate set of the corresponding user in the order of appearance of data points in the two sets during the k-domination checking process, so that the next user can filter and use them, which can reduce the number of comparisons between data points, avoids double counting, and improve query efficiency. A multi-user k-dominated skyline body parallel solving algorithm is also proposed, which effectively reduces the comparison time of data points through the Apache Flink parallel processing framework. The theoretical study and experimental data show that the proposed algorithm is highly efficient and can handle the multi-user k-dominated skyline problem well.

Key words: k-dominant, skyline query, multi-user, Apache Flink, parallel query

孙国璋, 黄山, 艾力卡木·再比布拉, 徐浩桐, 段晓东, . 基于Flink的k-支配skyline体并行求解算法[J]. 计算机工程与科学, 2023, 45(01): 17-27.

SUN Guo-zhang, HUANG Shan, , ALKAM Zabibul, XU Hao-tong, DUAN Xiao-dong, . A k-dominant skyline body parallel solving algorithm based on Flink[J]. Computer Engineering & Science, 2023, 45(01): 17-27.

参考文献［29］

［1］	Brzsonyi S,Kossmann D,Stocker K.The skyline operator［C］∥Proc of the 17th International Conference on Data Engineering,2001:421-430.
［2］	Chan C Y,Jagadish H V,Tan K L,et al.Finding k-dominant skylines in high dimensional space［C］∥Proc of the 2006 ACM SIGMOD International Conference on Management of Data,2006:503-514.
［3］	Yuan Y D,Lin X M,Liu Q,et al.Efficient computation of the skyline cube［C］∥Proc of the 31st International Conference on Very Large Data Bases,2005:241-252.
［4］	Dong Lei-gang,Liu Guo-hua,Cui Xiao-wei,et al.Sharing-based algorithm to find the k-dominant skyline cube［J］.Journal of Chinese Computer Systems,2009,30(6):1072-1076.(in Chinese)
［5］	Siddique M A,Morimoto Y.K-dominant skyline computation by using sort-filtering method［C］∥Proc of Pacific-Asia Conference on Knowledge Discovery and Data Mining,2009:839-848.
［6］	Yin Jian,Yao Shu-yu,Xue Shao-e,et al.An index based efficient k-dominant skyline algorithm［J］.Chinese Journal of Computers,2010,33(7):1236-1245.(in Chinese)
［7］	Siddique M A,Morimoto Y.K-dominant and extended k-dominant skyline computation by using statistics［J］.International Journal on Computer Science and Engineering,2010,2(5):1934-1943.
［8］	Huang Rong-yue,Zhao Lei.K-dominant skyline computation using simplified presort［J］.Journal of Chinese Computer Systems,2013,34(5):1054-1059.(in Chinese)
［9］	Siddique M A, Morimoto Y.Efficient k-dominant skyline computation for high dimensional space with domination power index［J］.Journal of Computers,2012,7(3):608-615.
［10］	Wu Jun-jie,Xin Jun-chang,Wang Guo-ren,et al.The k-dominating ranking skyline algorithm［J］.Journal of Computer Research and Development,2009,46(Suppl.):133-139.(in Chinese)
［11］	Huang Jin-jing,Zhao Lei.Search on experimental data using k*-dominate skyline query［J］.Research and Exploration in Laboratory,2018,37(4):117-122.(in Chinese)
［12］	Tian H,Siddique M A,Morimoto Y.An efficient processing of k-dominant skyline query in mapreduce［C］∥Proc of the 1st International Workshop on Bringing the Value of “Big Data” to Users,2014:29-34.
［13］	Peng Y W, Chen W M.Parallel k-dominant skyline queries in high-dimensional datasets［J］.Information Sciences,2019,496:538-552.
［14］	Siddique M A,Hao T,Morimoto Y.K-dominant skyline query computation in mapreduce environment［J］.IEICE Transactions on Information and Systems,2015,98(5):1027-1034.
［15］	Ding L L, Wang S, Zhang X,et al.Efficient k-dominant skyline query based on dominate hierarchical tree in mapreduce［C］∥Proc of the 14th International Conference on Natural Computation,Fuzzy Systems and Knowledge Discove- ry,2018:933-939.
［16］	Ding L L,Wang S,Song B Y.Efficient k-dominant skyline query over incomplete data using MapReduce［J］.Frontiers of Computer Science,2021,15(4):1-14.
［17］	Kontaki M,Papadopoulos A N,Manolopoulos Y.Contin- uous k-dominant skyline computation on multidimensional data streams［C］∥Proc of the 2008 ACM Symposium on Applied Computing,2008:956-960.
［18］	Siddique M A,Morimoto Y.Continuous k-dominant skyline computation by using divide and conquer strategy［J］.IPSJ Online Transactions,2010,3:97-109.
［19］	Siddique M A, Morimoto Y. Efficient maintenance of k- dominant skyline for frequently updated database［C］∥Proc of the 2nd International Conference on Advances in Databases,Knowledge,and Data Applications,2010:107-110.
［20］	Dong L G,Cui X W.Finding k-dominant skyline for combined dataset［J］.Applied Mechanics and Materials,2014,568-570:1534-1538.
［21］	Miao X Y,Gao Y J,Chen G,et al.K-dominant skyline queries on incomplete data［J］.Information Sciences,2016,367:990-1011.
［22］	Liao Zai-fei,Luo Xiong-fei,Lü Xin-jie,et al.Querying k-dominant skyline for incomplete data stream over sliding window［J］.Journal of Computer Research and Development,2009,46(Suppl.) 254-262.(in Chinese)
［23］	Lai C C,Lin H Y, Liu C M.Highly efficient indexing scheme for k-dominant skyline processing over uncertain data streams［C］∥Proc of the 30th Wireless and Optical Communications Conference,2021:97-101.
［24］	Li X Y,Liu J,Ren K J,et al.Parallel k-dominant skyline queries over uncertain data streams with capability index［C］∥Proc of the 21st IEEE International Conference on High Performance Computing and Communications; the 17th IEEE International Conference on Smart City;the 5th IEEE International Conference on Data Science and Systems,2019:1556-1563.
［25］	Awasthi A,Bhattacharya A,Gupta S,et al.K-dominant skyline join queries:Extending the join paradigm to k-dominant skylines［C］∥Proc of the 33rd IEEE International Confe- rence on Data Engineering,2017:99-102.
［26］	Li Song,Dou Ya-nan,Hao Xiao-hong,et al.The method of the k-dominant space skyline query in road network［J］.Journal of Computer Research and Development,2020,50(1):227-239.(in Chinese)
［27］	Tripathy P K,Rath S K.Computing the k-dominant skyline efficiently in the dynamic environments［C］∥Proc of 2020 International Conference on Computer Science,Engineering and Applications,2020:1-11.
［28］	Zheng Z Y,Ruan K,Yu M Y,et al.K-dominant skyline query algorithm for dynamic datasets［J］.Frontiers of Computer Science,2021,15(1):1-9.
［29］	Dong Lei-gang,Cui Xiao-wei,Liu Guo-hua.An algorithm to update k-dominant skyline［J］.Science Technology and Engineering,2014,14(22):235-239.(in Chinese)
	附中文参考文献：
［4］	董雷刚,刘国华,崔晓微,等.基于共享策略的k-支配轮廓体的求解算法［J］.小型微型计算机系统,2009,30(6):1072-1076.
［6］	印鉴,姚树宇,薛少锷,等.一种基于索引的高效k-支配Skyline算法［J］.计算机学报,2010,33(7):1236-1245.
［8］	黄荣跃,赵雷.一种使用简化预排序的k-支配Skyline查询算法［J］.小型微型计算机系统,2013,34(5):1054-1059.
［10］	吴俊杰,信俊昌,王国仁,等.支配能力排序轮廓查询算法［J］.计算机研究与发展,2009,46(Suppl.):133-139.
［11］	黄金晶,赵雷.k*-支配Skyline查询在实验数据检索中的应用［J］.实验室研究与探索,2018,37(4):117-122.
［22］	廖再飞,罗雄飞,吕新杰,等.一种面向不完整数据流上的k-支配skyline查询算法［J］.计算机研究与发展,2009,46(Suppl.):254-262.
［26］	李松, 窦雅男, 郝晓红, 等.道路网环境下K-支配空间Sky-line查询方法［J］.计算机研究与发展,2020,57(1):227-239.
［29］	董雷刚,崔晓微,刘国华.一种更新k-支配轮廓的算法［J］.科学技术与工程,2014,14(22):235-239.

[1]	吕鹤轩, 黄山, 艾力卡木·再比布拉, 吴思衡, 段晓东, . Flink水位线动态调整策略[J]. 计算机工程与科学, 2023, 45(02): 237-245.
[2]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[3]	郎晓丽，曹素珍，刘祥震，张玉磊，王斐. 公开信道下多服务器多关键词多用户可搜索加密方案[J]. 计算机工程与科学, 2019, 41(12): 2154-2159.
[4]	池鹏可，苏成悦，谢广泉，柳丁. Android平台上的多用户无线投影控制系统设计[J]. J4, 2015, 37(11): 2148-2153.
[5]	刘婷1，张立毅1,2，张晋斌3. 基于分布估计蜂群算法的多用户检测器[J]. J4, 2014, 36(07): 1316-1323.
[6]	程荣峰，肖迎元. 数据广播环境下基于数据共享的位置相关skyline查询[J]. J4, 2012, 34(10): 177-181.
[7]	乔少杰，杨燕，葛永明，张翠芳，戴齐. 基于B/S架构的多用户在线程序评判系统设计与实现[J]. J4, 2011, 33(增刊A1): 28-61.
[8]	鲁修卓谢长生任劲. 跨平台、多用户iSCSI存储系统的实现与管理[J]. J4, 2005, 27(1): 93-95.
[9]	王慧华朱娜. 多用户协作环境下的递归建模及合理决策[J]. J4, 2004, 26(12): 94-96.