高维数据下近似K近邻查询的研究

• 作 者: 杜帅剑
• 出 处: 哈尔滨工业大学
• 发表日期: 2004年期
• 关键词: 高维数据 局部敏感哈希 近似近邻搜索 谱哈希 神经网络

近年来,随着互联网的迅速普及,人类日常生活产生的数据也越来越大。数据的爆炸不仅体现在数据量上的增长,也体现在数据维度上的增长,在高维数据上的一些操作成为越来越重要的研究课题,比如本文关注的近似近邻查找问题。本文中我们主要针对于高维数据空间下的近似近邻查询问题进行了较深入的分析与研究。对近似近邻查找领域的查询感知的检索方式进行了一系列优化与改进。具体的工作有以下两点:对于近似近邻搜索,查询感知LSH是一种非常新颖的检索方式,这种方式不同于一般LSH中所使用的直接哈希分桶,它是通过先确定哈希投影再确定检索范围的方式,使得查询效果明显提升。本文首先对查询感知LSH进行改进,通过改进算法中的一些缺陷然后结合使用谱方法进行哈希,使得算法在时间和IO性能上都得到了一定的提升。深度哈希是基于深度神经网络的一类哈希算法,我们希望借助神经网络来建立一种优秀的哈希结构。我们首先提出了一种新的激活函数,然后建立了一种卷积自编码器网络结构,并提出了适用于该类网络的预训练方法。通过神经网络强大的表示能力,将数据哈希降维到低维数据,得到了非常精简的编码。最后我们联合深度哈希和查询感知检索方式,建立了一个基于深度哈希的近似近邻检索模型。虽然离线训练模型需要占用一定时间,但是这种方式缩短了在线处理时间和并且可以得到更加优良的检索结果。最后在公开数据集上的实验表明我们提出的激活函数和训练策略都非常有用,同时我们在实验中证明了卷积自编码器网络的高效性和实用性。