基于ρ-支配轮廓及n-of-Nρ-支配轮廓的数据流中关键数据计算方法

doi:10.3969/j.issn.1000-1093.2021.05.013

摘要/Abstract

摘要： 目前数据采集手段不断丰富和发展，但是数据采集区域往往网络状况受限，比如网络时断时续、网络带宽较小，采集的数据难以实时准确的传输到数据应用方，因此如何计算出采集数据中关键数据减少数据传输过程中网络占用量至关重要。以装甲车辆的状态数据传输为背景，重新对数据流中ρ-支配关系的性质进行分析，并对数据流中ρ-支配轮廓查询算法进行更改和扩展；在此基础上，提出了数据流中n-of-Nρ-支配轮廓查询算法，进一步满足网络受限环境中关键数据选择传输的要求。仿真实验结果表明，改进的数据流中ρ-支配轮廓查询算法以及数据流中n-of-Nρ-支配轮廓查询算法能够计算出相对关键的数据，进而减小数据传输的网络代价，并且数据流中n-of-Nρ-支配轮廓查询相比于数据流中ρ-支配轮廓查询具有更广泛的应用。

关键词: 数据流, 轮廓查询, ρ-支配轮廓, n-of-Nρ-支配轮廓, 数据传输

Abstract: The data collection method has constantly been enriched and developed, but the network in the data collection area is often limited, such as intermittent network and small network bandwidth, so the collected data is difficult to be accurately transmitted to the application side in real time. It is very important to ensure how to calculate the key data to reduce the network usage during data transmission. Based on the state data transmission of armored vehicles,the nature of the ρ-dominant relationship in the data stream is reanalyzed,and the query algorithm of ρ-dominant skyline in the data stream is changed and expanded. On this basis, a query algorithm of n-of-Nρ-dominant skyline in the data stream is proposed to further meet the requirements of the selection and transmission of key data in the network-restricted environment. Through the experiment, it is found that the improved ρ-dominant skyline query algorithm and the n-of-Nρ-dominant skyline query algorithm can calculate the relatively critical data, thereby reducing the network cost of data transmission,and n-of-Nρ-dominant skyline query has wider application than ρ-dominant skyline query in the data stream.

Key words: datastream, skylinequery, ρ-dominantskyline, n-of-Nρ-dominantskyline, datatransmission

中图分类号:

TP312.8

霸建民，郭永红，彭龙，赵东阳，邵鹏志，杜宏博. 基于ρ-支配轮廓及n-of-Nρ-支配轮廓的数据流中关键数据计算方法[J]. 兵工学报, 2021, 42(5): 1004-1015.

BA Jianmin, GUO Yonghong, PENG Long, ZHAO Dongyang, SHAO Pengzhi, DU Hongbo. A Calculation Method for Key Data of Data Stream Based on ρ-dominant and n-of-Nρ-dominant Skylines[J]. Acta Armamentarii, 2021, 42(5): 1004-1015.

参考文献

[1] TATBUL N, ETINTEMEL U, ZDONIK SB, et al. Load shedding in a data stream manager[C]∥Proceedings of the 29th International Conference on Very Large Data Bases.Berlin, Germany: VLDBEndowment, 2003: 309-320.
[2] DE ASSUNCAO M D, VEITH A D S, BUYYA R. Distributed data stream processing and edge computing: asurvey on resource elasticity and future directions[J]. Journal of Network & Computer Applications, 2018, 103:1-17.
[3] BORZSONY S, KOSSMANN D, STOCKER K. The skyline operator [C]∥Proceedings of 17th International Conference on Data Engineering. Heidelberg,Germany: IEEE, 2001: 421-430.
[4] PAPADIAS D, TAO Y F, FU G, et al. An optimal and progressive algorithm for skyline queries[C]∥Proceedings of the 2003 ACMSIGMOD International Conference on Management of Data. San Diego, CA,US: ACM, 2003: 467-478.
[5] DING L L, XIN J C, WANG G R, et al. Efficient skyline query processing of massive data based on map-reduce[J]. Chinese Journal of Computers, 2011, 34(10):1785-1796.
[6] 余靖,刘盼盼. MapReduce框架下k-支配轮廓查询算法[J]. 燕山大学学报,2014, 38(6):532-537.
YU J, LIU P P. k-dominant skyline query algorithm based on Map Reduce framework[J]. Journal of Yanshan University, 2014, 38(6): 532-537. (in Chinese)
[7] LAI C C, AKBAR Z F, LIU C M, et al. Distributed continuous range-skyline query monitoring over the internet of mobile things[J]. IEEE Internet of Things Journal, 2019, 6(4):6652-6667.
[8] TIAN H, SIDDIQUE M A, MORIMOTO Y, et al. An efficient processing of k-dominant skyline query in MapReduce[C]∥Proceedings of International Workshop on Bringing the Value of Big Data to Users. Hangzhou, China:ACM, 2014:29-34.
[9] ZHENG B, LEE K C, LEE W C. Location-dependent skyline query[C]∥Proceedings of International Conference on Mobile Data Management. Beijing, China: IEEE, 2008: 148-155.
[10] LIU X, YANG D N, YE M, et al. U-Skyline: a new skyline query for uncertain databases[J]. IEEE Transactions on Know- ledge and Data Engineering, 2013, 25(4):945-960.
[11] REN W L, LIAN X, GHAZINOUR K. Skyline queries over incomplete data streams[J]. The VLDB Journal, 2019, 28(6):961-985.
[12] XIE M, WONG C W, LAL L A. An experimental survey of regret minimization query and variants: bridging the best worlds between top-k query and skyline query[J]. The VLDB Journal, 2020, 29(1):147-175.
[13] CHEN L, LIAN X. Dynamic skyline queries in metric spaces[C] ∥Proceedings of the 11th International Conference on Extending Database Technology:Advances in Database Technology. Nantes, France: ACM, 2008: 333-343.
[14] 周剑刚, 秦小麟, 张珂珩,等.基于道路网的多移动用户动态Skyline查询[J]. 计算机科学,2019, 46 (9): 73-78.
ZHOU J G, QIN X L, ZHANF K H, et al. Dynamic skyline query for multiple mobile users based on road network[J]. Computer Science, 2019, 46 (9): 73-78.(in Chinese)
[15] ZOU L, CHEN L, ZSU M T, et al. Dynamic skyline queries in large graphs[C]∥Proceedings of International Conference on Database Systems for Advanced Applications. Tsukuba, Japan: Springer, 2010:62-78.
[16] LI H, YOO J. An efficient scheme for continuous skyline query processing over dynamic data set[C]∥Proceedings of 2014 International Conference on Big Data and Smart Computing. Bangkok, Thailand: IEEE, 2014:1197-1206.
[17] 张丽，邹鹏，贾焰，等.数据流上连续动态skyline查询研究[J]. 计算机研究与发展，2015, 48(1): 77-85.
ZHANG L, ZOU P, JIA Y, et al. Continuous dynamic skyline queries over data stream[J]. Journal of Computer Research and Development, 2015, 48(1): 77-85.（in Chinese）
[18] BAI M, XIN J C, WANG G R, et al. Research on dynamic skyline query processing over data streams[J]. Chinese Journal of Computers, 2011, 34(10): 1876-1884.
[19] 信俊昌, 白梅, 东韩, 等. 一种ρ-支配轮廓查询的高效处理算法[J]. 计算机学报, 2011, 34(10): 1876-1884.
XIN J C, BAI M, DONG H, et al. An efficient processing algorithm for ρ-dominant skyline query[J]. Chinese Journal of Computers, 2011, 34(10): 1876-1884.(in Chinese)
[20] 王之琼, 霸建民, 黄达,等. 数据流中ρ-支配轮廓查询算法[J]. 计算机科学与探索, 2017, 11(7): 1080-1091.
WANG Z Q, BA J M, HUANG D, et al. ρ-dominant skyline computation on data streams[J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(7): 1080-1091.(in Chinese)