-
题名过滤器数据结构研究综述
被引量：1
- 1
-
-
作者
王瀚橙
戴海鹏
陈树森
陈志鹏
陈贵海
-
机构
计算机软件新技术国家重点实验室(南京大学)
-
出处
《计算机科学》
CSCD
北大核心
2024年第1期35-40,共6页
-
基金
国家自然科学基金(62272223)。
-
文摘
过滤器数据结构可以近似地判断某个元素是否属于给定集合。典型的过滤器数据结构,如布隆过滤器、布谷鸟过滤器、商过滤器,以牺牲查询准确性为代价换取更低的内存空间消耗和查询时间开销。因此,得益于空间时间高效性,过滤器数据结构现已被广泛应用于计算机网络、物联网、数据库系统、文件系统、生物信息学、机器学习等领域的近似成员资格查询操作中。自20世纪70年代以来,过滤器数据结构受到了广泛的研究,在诸多领域取得了重要的进展,其研究思路也在不断变化。文中整理了近五十年来关于过滤器数据结构的经典研究成果,从过滤器数据结构的原理出发对已有工作进行分类总结,并比较不同工作之间的引证关系和改进思路,最后讨论了过滤器数据结构的未来研究方向。
-
关键词
过滤器
近似成员资格查询
概率数据结构
布隆过滤器
布谷鸟过滤器
商过滤器
-
Keywords
Filter
Approximate membership query
Probabilistic data structure
Bloom filter
Cuckoo filter
Quotient filter
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
-
题名跳跃滤波:一种面向大数据治理的动态数据摘要设计
被引量：2
- 2
-
-
作者
符鹏涛
罗来龙
郭得科
赵翔
李尚森
王怀民
-
机构
国防科技大学系统工程学院
国防科技大学计算机学院
-
出处
《软件学报》
EI
CSCD
北大核心
2023年第3期1193-1212,共20页
-
基金
国家自然科学基金(U19B2024,62002378,61772544)
国防科技大学科研基金(ZK20-30)。
-
文摘
随着信息技术的迅速发展,数据体量维持指数增长,数据价值挖掘困难,这为数据采集、清洗、存储、共享等数据生命周期中各环节的高效管控带来极大的挑战.数据摘要技术利用哈希表/矩阵/位向量对数据的频数、基数、成员关系等核心基础特性进行追踪,使得数据摘要自身成为元数据,并在共享、传输、更新等场景得到广泛应用.大数据的快速流转特性更是催生了动态数据摘要技术.现有的动态数据摘要技术通过动态维护链状或树状结构的概率数据结构列表,具有其容量随数据流大小而扩增或缩减的优势,然而也存在空间开销过大以及时间开销随数据基数增加而增长的缺陷.基于先进的跳跃一致性哈希理论,设计了一种面向大数据治理的动态数据摘要技术.该方法可以同时实现随数据基数线性增长的空间开销以及数据处理分析常数级别的时间开销,能够有效地支撑要求苛刻的多种大数据处理分析任务.在多种合成和真实数据集上,通过与传统方法实验对比,验证了所提方法的有效性和高效性.
-
关键词
大数据
大数据治理
元数据
动态数据摘要
概率数据结构
-
Keywords
big data
big data governance
metadata
dynamic sketch
probabilistic data structure
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
