跳跃滤波:一种面向大数据治理的动态数据摘要设计
作者:
作者单位:

作者简介:

符鹏涛(1998-),男,硕士,CCF学生会员,主要研究领域为数据摘要技术,网络测量;赵翔(1986-),男,博士,教授,CCF高级会员,主要研究领域为知识图谱,先进数据分析;罗来龙(1991-),男,博士,副研究员,CCF高级会员,主要研究领域为数据摘要技术,分布式网络系统;李尚森(1997-),男,博士生,主要研究领域为网络测量,软件定义网络,数据摘要技术;郭得科(1980-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为网络计算与系统,分布式计算与系统,网络空间安全,边缘计算,软件定义网络,移动计算,网络大数据;王怀民(1962-),男,博士,教授,博士生导师,中国科学院院士,CCF会士,主要研究领域为分布计算,软件技术,云际计算,群体智能.

通讯作者:

罗来龙,luolailong09@nudt.edu.cn;郭得科,dekeguo@nudt.edu.cn

中图分类号:

基金项目:

国家自然科学基金(U19B2024,62002378,61772544);国防科技大学科研基金(ZK20-30)


Jump Filter: Dynamic Sketch Design for Big Data Governance
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    随着信息技术的迅速发展,数据体量维持指数增长,数据价值挖掘困难,这为数据采集、清洗、存储、共享等数据生命周期中各环节的高效管控带来极大的挑战.数据摘要技术利用哈希表/矩阵/位向量对数据的频数、基数、成员关系等核心基础特性进行追踪,使得数据摘要自身成为元数据,并在共享、传输、更新等场景得到广泛应用.大数据的快速流转特性更是催生了动态数据摘要技术.现有的动态数据摘要技术通过动态维护链状或树状结构的概率数据结构列表,具有其容量随数据流大小而扩增或缩减的优势,然而也存在空间开销过大以及时间开销随数据基数增加而增长的缺陷.基于先进的跳跃一致性哈希理论,设计了一种面向大数据治理的动态数据摘要技术.该方法可以同时实现随数据基数线性增长的空间开销以及数据处理分析常数级别的时间开销,能够有效地支撑要求苛刻的多种大数据处理分析任务.在多种合成和真实数据集上,通过与传统方法实验对比,验证了所提方法的有效性和高效性.

    Abstract:

    With the rapid development of information technology, the volume of data maintains an exponential growth, and the value of data is hard to mine. It brings significant challenges to the efficient management and control of each link in the data life cycle, such as data collection, cleaning, storage, and sharing. Sketch uses a hash table/matrix/bit vector to track the core characteristics of data, such as frequency, cardinality, membership, etc. This mechanism makes sketch itself metadata which has been widely used in the sharing, transmission, update and other scenarios. The rapid flow characteristic of big data has spawned the dynamic sketches. The existing dynamic sketches have the advantage of expanding or shrinking in capacity with the size of the data stream by dynamically maintaining a list of probabilistic data structures in a chain or tree structure. However, there are defects of excessive space overhead and time overhead increasing with the increase of the dataset cardinality. This study designs a dynamic sketch for big data governance based on the advanced jump consistent hash. This method can simultaneously realize the space overhead that grows linearly with the dataset cardinality and the constant time overhead of data processing and analysis, effectively supporting the demanding big data processing and analysis tasks for big data governance. The validity and efficiency of the proposed method are verified by comparing it with traditional methods on various datasets, including synthetic and natural datasets.

    参考文献
    相似文献
    引证文献
引用本文

符鹏涛,罗来龙,郭得科,赵翔,李尚森,王怀民.跳跃滤波:一种面向大数据治理的动态数据摘要设计.软件学报,2023,34(3):1193-1212

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2022-05-14
  • 最后修改日期:2022-07-29
  • 录用日期:
  • 在线发布日期: 2022-10-26
  • 出版日期: 2023-03-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号