基于局部敏感哈希算法的图像高维数据索引技术的研究.pdfVIP

第 33 卷第 1 期 辽宁工业大学学报(自然科学版) Vol.33, No.1 2013 年 2 月 Journal of Liaoning University of Technology(Natural Science Edition) Feb. 2013 本刊核心层次论文 基于局部敏感哈希算法的图像 高维数据索引技术的研究 曹玉东，刘福英，蔡希彪 （辽宁工业大学 电子与信息工程学院，辽宁 锦州 121001） 摘 要：局部敏感哈希(LSH)算法是有效的高维数据索引方法之一，该算法成功地解决了“维数灾难”问题。 分析了 LSH 算法中主要参数对索引性能的影响，在规模不同的图像数据集上应用了 LSH 算法，实验结果表明选 择合适的参数时，其性能接近顺序有哪些信誉好的足球投注网站方法。 关键词：高维数据索引；图像检索；局部敏感哈希算法 中图分类号：TP311 文献标识码：A 文章编号：1674-3261(2013)01-0001-03 Research on High Dimension Image Data Indexing Technology Based on Locality Sensitive Hashing Algorithm CAO Yu-dong, LIU Fu-ying, CAI Xi-biao （Electronics Information Engineering College, Liaoning University of Technology, Jinzhou 121001, China ） Abstract: Locality sensitive hashing (LSH) was quite an efficient high dimensional data indexing method, which solved the problem on “disaster of dimension”. How the key parameters of LSH affect the performance of retrieval were analyzed, and LSH is also applied to different scale image datasets. The experimental results show that the performance of LSH is near to that of linear scan with the suitable parameters selected. Key words: high data indexing; image retrieval; LSH algorithm 在理想的情况下，传统的哈希(hash)索引技术 而迅速下降[4]，这种在高维特征空间(通常在几十维 不经过任何比较，经过一次存取就能得到所查的记 以上)有哪些信誉好的足球投注网站性能会低于标准的顺序查找算法的现象 录，其时间复杂度是 O (1)[1] 。但是该技术适合查找 被称为“维数灾难”[4] ，表现为查找的准确度下降 一个确定位置的记录，不太适合查找在某个范围内 或有哪些信誉好的足球投注网站时间变长等。当前基于树的索引方法都没能 的近似记录。图像的特征数据往往呈现出高维特 完全解决“维数灾难”问题。 性，是图像的一种近似表示，以上两个特点决定了 LSH[5]是一种随机的算法，能以恒定的概率保 传统的哈希索引技术不再适合索引高维的图像数 证算法返回的是真正最近邻或者是很接近最近邻 据。在传统的索引方