面向海量数据的快速查询服务需要智能化的数据检索结构和实现机制，这对于提高大规模云存储系统的整体性能至关重要。Cuckoo hashing机制因其简单易用的特性被广泛应用于支持查询服务。然而传统的Cuckoo hashing机制无法解决元素插入过程中存在的踢出路径无限循环的问题，这将导致较高的索引表构建时延，严重影响系统性能。

信息存储与光显示功能实验室博士生孙园园在华宇教授的指导下，提出了一种高效的Cuckoo hashing方法 （SmartCuckoo），能够在实际插入操作之前准确预测操作结果。SmartCuckoo将哈希关系表示为有向图并利用其跟踪记录元素位置，来准确预测无限循环的发生，避免了执行逐步探测昂贵的成本开销。其将索引表中每个桶看作是图的一个节点，将索引表中每个元素看作是图的一条边，每次插入操作将新增的探测桶加入到对应子图中，图边数同时加1。该有向图中每个子图至多存在一个回路，当子图中有且只有一个回路（子图边数等于节点数）时，该子图为满载子图；反之为非满载子图。当执行插入操作时，若子图满载，即插入该元素的踢出路径会形成回路导致无限循环，因此插入操作会失败；待子图非满载时，该子图中存在一个空位，经过有限次踢出操作时，所有元素都将插入索引表中，则插入操作会成功。大量实验结果表明，SmartCuckoo能够准确预测元素插入操作的结果，并且能够在保持其高效的查询性能的同时显著提高系统的插入操作吞吐量。

该研究成果“SmartCuckoo: A Fast and Cost-Efficient Hashing Index Scheme for Cloud Storage Systems (SmartCuckoo：一种云存储系统中的快速高效的哈希检索方法)”，在2017年7月召开的USENIX年度技术会议上 （USENIX Annual Technical Conference, ATC 2017），被作为长文全文录用。USENIX ATC 2017是中国计算机学会推荐的A类国际学术会议，是计算机系统结构领域的旗舰会议。

该研究工作得到了国家重点研发计划项目(No.2016YFB1000202)的支持。

面向有向森林结构图的分析 插入数据元素吞吐量