在线密度敏感哈希算法研究

摘要 哈希算法在大规模的数据检索中得到了越来越广泛的应用,但目前无论是基于学习的哈希还是基于随机投影的哈希都是为静态数据集设计的,无法对动态的数据库或者动态的网页进行近邻搜索.为了解决这一问题,本文提出了基于在线k均值聚类的密度敏感哈希算法ODSH (Online Density Sensitive Hash).首先给出了固定聚类个数的在线k均值聚类公式;然后,根据在线k均值聚类量化后数据簇的表示点来划定超平面,并根据动态超平面推出该哈希算法的哈希函数以及对应的投影向量;最后根据投影向量划分的数据集求得各投影向量的信息熵值,根据其大小选出最合适的投影向量,并通过投影向量对数据集进行映射来获取对应的哈希编码.实验结果表明,与局部敏感哈希、谱哈希等哈希算法相比,本文算法在准确性和效率上均具有一定的优势