信息存储系统教育部重点实验室

博士生孙园园的论文被会议MSST 2015录用


实验室博士生孙园园的论文《MinCounter: An Efficient Cuckoo Hashing Scheme for Cloud Storage Systems》被第31届海量存储系统与技术国际会议(31st International Conference on Massive Storage Systems and Technology(MSST 2015))录用。

随着信息数量的快速发展,云计算服务器需要实时和准确地处理和分析大规模高维无结构化数据,其中包括大量的查询操作。Cuckoo hashing机制因其易于实现和使用的特性被广泛应用于与云相关的应用中。然而,cuckoo hashing机制无法避免传统哈希算法中都会存在的哈希冲突现象,使得数据插入时踢除路径形成无限环路,这将造成较高的插入时延,甚至导致整个哈希表重构的高风险,严重影响系统性能。

孙园园等博士生在华宇副教授的指导下,设计了一种新的基于cuckoo hashing算法(MinCounter)来缓和在数据插入操作中无限循环的发生。我们发现在数据插入操作中,对哈希表中buckets的访问次数是不均匀分布的,发生哈希冲突选择路径时,bucket的访问越频繁,导致无限循环的概率越大。MinCounter机制利用这一特性,控制发生哈希冲突时选择“cold”buckets而不是随机选择buckets,来最终减轻无限循环的发生。我们的实验结果证明MinCounter机制能够很大程度地提高系统的空间利用率和降低数据插入时延。这项研究成果发表在中国计算机学会推荐的B类国际会议MSST 2015(2015年5月30日-6月5日,美国加州圣克拉拉)。MSST是全球存储系统与技术领域学者的盛会,同时也是国际计算机存储系统领域的一大标志性会议。本届会议收到100多篇投稿,收录长文14篇,短文9篇,录用率约为23%。

注:本文为原创,如转载请注明出处。

分享文章

Share