数据依赖的多索引哈希算法_马艳萍_姬光荣_邹海林_谢洪涛.pdfVIP

2015 年 8 月 西安电子科技大学学报（自然科学版） Aug.2015 第 42 卷 第 4 期 JOURNAL OF XIDIAN UNIVERSITY Vol.42 No.4 doi：10.3969/j.issn.1001-2400.2015.04.026 数据依赖的多索引哈希算法 1,2 1 2 3 马艳萍 ，姬光荣 ，邹海林 ，谢洪涛 (1. 中国海洋大学信息科学与工程学院，山东 青岛 266100； 2．鲁东大学信息与电气工程学院，山东 烟台 264025 3．中国科学院信息工程研究所 信息内容安全技术国家工程实验室，北京，100093) 摘要：多索引哈希是目前使用最广泛的针对二进制码的索引算法. 由于多索引哈希基于数据集中的二进 制码呈均匀分布这一假设，不能有效处理非均匀分布的数据集. 针对这一问题，提出数据依赖的多索引 哈希算法. 首先把二进制码划分为多个连续不重合的子串，并通过计算二进制码每位之间的相关性为每 一个子串学习得到自适应投影向量. 在为每个子串建立哈希表时，使用投影向量对子串进行投影从而得 到哈希表中的下标. 采用自适应投影的方法可以使得哈希表中的元素接近于均匀分布，进而提升查询速 度. 此外，提出一个基于熵的分布度量方法，以评价哈希表中数据元素的分布情况. 在大规模数据集上的 实验表明，与多索引哈希算法相比数据依赖的多索引哈希算法可以使查询速度提升36.9%–87.4%. 关键词：最近邻查询；二进制码；索引；多索引哈希 中图分类号：TP183 文献标识码：A 文章编号：1001-2400(2015)04-0177-07 Data-oriented multi-index Hashing 1,2 1 2 3 MA Yanping , JI Guangrong , ZOU Hailin , XIE Hongtao 1 ( School of Information Science and Engineering, Ocean University of China, Qingdao, 266100 2 Scholol of Information and Electrical Engineering, Ludong University, Yantai, 264025 3 Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100093) Abstract: Multi-index hashing (MIH) is the state-of-the-art method for indexing binary codes. However, MIH is based on the dataset codes uniform distribution assumption, and will lose efficiency in