倒插入分段哈希算法

计算机应用 ›› 2011, Vol. 31 ›› Issue (02): 514-516.

倒插入分段哈希算法

唐铭¹,史长琼¹,周恺卿¹,张大方²

1. 长沙理工大学
2. 湖南大学

收稿日期:2010-07-21 修回日期:2010-09-14 发布日期:2011-02-01 出版日期:2011-02-01
通讯作者: 唐铭
基金资助:
湖南省自然科学基金

Inverse insert algorithm based on segment hash

Received:2010-07-21 Revised:2010-09-14 Online:2011-02-01 Published:2011-02-01
Supported by:
This research work is supported by Provincial Natural Science Fund of Hunan under grants No. 07JJ6137

摘要/Abstract

摘要： 受到孔雀哈希与分段哈希算法的启发，提出了一种新的倒插入分段哈希表。该算法从改变表的操作顺序及修改孔雀哈希数据结构着手，保证了片外访问的平均次数接近于1。分析与实验表明，该算法具有较高的效率，降低了内存开销。

关键词: 孔雀哈希, 分段哈希, 位图数组, 布鲁姆过滤器, 内存

Abstract: A segment hash with inversed insertion based on peacock hash and segment hash was proposed. This algorithm ensured the average times of off-chip access close to 1 through changing the operating sequence and data structure of peacock hash. The analysis and experimental results show that the algorithm has high efficiency and can reduce the memory overhead.

Key words: peacock hash, segment hash, bitmap array, Bloom Filter (BF), memory

唐铭史长琼周恺卿张大方. 倒插入分段哈希算法[J]. 计算机应用, 2011, 31(02): 514-516.

[1]	廖佳, 陈扬, 包秋兰, 廖雪花, 朱洲森. 计算密集型大流量数据的接力计算与动态分流处理[J]. 计算机应用, 2021, 41(9): 2646-2651.
[2]	汤晨, 黄国锐, 金培权. 非易失性内存友好的线性哈希索引——NVM-LH[J]. 计算机应用, 2021, 41(3): 623-629.
[3]	董豪宇, 陈康. 纯用户态的网络文件系统——RUFS[J]. 计算机应用, 2020, 40(9): 2577-2585.
[4]	王成, 叶保留, 梅峰, 卢文达. 基于远程直接内存访问的高性能键值存储系统[J]. 计算机应用, 2020, 40(2): 316-320.
[5]	崔晨, 郑林江, 韩凤萍, 何牧君. 基于内存的HBase二级索引设计[J]. 计算机应用, 2018, 38(6): 1584-1590.
[6]	杨顺, 陈志广, 肖侬. Pmfs中目录项索引的实现[J]. 计算机应用, 2017, 37(5): 1241-1245.
[7]	姚小强, 刘昌云, 郭相科. 基于数据截获和欺骗式注入的通用记录重演方法[J]. 计算机应用, 2017, 37(4): 1153-1156.
[8]	卞琛, 于炯, 修位蓉, 英昌甜, 钱育蓉. 基于迭代填充的内存计算框架分区映射算法[J]. 计算机应用, 2017, 37(3): 647-653.
[9]	丁梦苏, 陈世敏. 轻量级大数据运算系统Helius[J]. 计算机应用, 2017, 37(2): 305-310.
[10]	侯伟凡, 樊玮, 张宇翔. 改进的Spark Shuffle内存分配算法[J]. 计算机应用, 2017, 37(12): 3401-3405.
[11]	赵永彬, 陈硕, 刘明, 王佳楠, 贲驰. 流计算与内存计算架构下的运营状态监测分析[J]. 计算机应用, 2017, 37(10): 3029-3033.
[12]	王跃飞, 于炯, 鲁亮. 面向内存云的协调器选举策略[J]. 计算机应用, 2016, 36(9): 2402-2408.
[13]	许川佩, 王光. 基于OpenCL的尺度不变特征变换算法的并行设计与实现[J]. 计算机应用, 2016, 36(7): 1801-1806.
[14]	褚征, 于炯, 鲁亮, 英昌甜, 卞琛, 王跃飞. 基于内存云的大块数据对象并行存取策略[J]. 计算机应用, 2016, 36(6): 1526-1532.
[15]	王跃飞, 于炯, 鲁亮. 面向内存云的数据块索引方法[J]. 计算机应用, 2016, 36(5): 1222-1227.