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

作者简介:

通讯作者:

罗来龙,E-mail:luolailong09@nudt.edu.cn;郭得科,E-mail:dekeguo@nudt.edu.cn

中图分类号:

基金项目:


Jump Filter:A Dynamic Sketch 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 min.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 characteristics 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 paper 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):0

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

京公网安备 11040202500063号