CB-LSH:基于压缩位图的高性能LSH索引算法

作者：吴羽; 寿黎但; 陈刚

来源：浙江大学学报(工学版), 2012, 46(03): 377-385.

• 位图索引
• 局部敏感散列
• 高维索引
• 在线更新

由于传统局部敏感散列(LSH)算法的删除性能不足,阻碍了LSH算法在实际产品中的应用.提出一种基于压缩位图的改进方法,通过引入压缩位图改良传统LSH算法的桶中数据结构,以及使用标记清除策略进行算法流程优化,解决传统LSH索引实时删除性能差的问题.理论分析证明:基于压缩位图的LSH(CB-LSH)算法可以显著降低算法的空间复杂度和时间复杂度.实验结果支撑了理论分析的结论,相对于传统LSH算法,CB-LSH在降低内存消耗的同时,可显著提高索引删除、数据插入和数据查询的性能.在大型项目中的应用实践验证了在线实时更新的海量多媒体数据检索系统中,CB-LSH索引算法对于多媒体数据的高维索引是有效可行的,并显著提升了性能、降低了资源消耗.

• 出版日期2012
• 单位浙江大学