可逆概要数据结构  

Reversible sketch data structure

作　　者：冯文峰[1] 黄永峰[1] 李星[1] 

机构地区：[1]清华大学电子工程系

出　　处：《清华大学学报（自然科学版）》2008年第10期1625-1628,共4页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金资助项目(60703053);国家“九七三”基础研究基金项目(2007CB310806)

摘　　要：由于随机哈希函数不可逆,目前的概要数据结构不得不遍历关键字地址空间以查找和估计频繁项集。该文基于多项式域上的中国剩余定理,设计可逆Hash函数族,进而实现了一类可逆概要数据结构。它遍历哈希地址空间查找和估计频繁项集,并利用随机哈希函数的可逆性反推出频繁项对应的关键字。实验结果表明,与目前具有代表性的Count-Min概要数据结构相比,可逆概要数据结构以相同的存储空间和估计精度,将查找速度提高了约4个量级。Due to the irreversibility of random hash mapping, current sketch data structures have to traverse the key address space to find frequent items. The Chinese remainder theorem for a polynomial field was used to design a family of reversible Hash functions on the polynomial field, with a reversible sketch data structure, which only needs to traverse the hash address space to find and evaluate frequent items and then computes the responsible keys by reverse hash mapping. Experimental results show that the reversible sketch improves the finding speed by about four magnitudes over the Count-Min sketch with almost the same storage space and accuracy.

关 键 词：数据结构 随机映射 多项式域 中国剩余定理 频繁项集 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP311.12[自动化与计算机技术—计算机科学与技术]