浅谈实值向量的近邻检索方案

人工智能的飞速发展需要依靠大规模的数据,作为一个重要的无监督场景,如何从海量的数据中寻找最相近的部分数据受到广泛关注。数十年的研究表明,树形索引、哈希散列与近邻图三类方案能够保证次线性的检索时间。该文介绍了针对实值向量的近邻检索问题的定义,并对三类方案中主流的方法及其发展过程进行梳理。

高维空间近邻检索的双层组合量化GPU加速算法

在大规模视频、图像、文本检索等许多实际应用中,高维空间内海量数据的索引及近邻检索一直是难点和关键问题之一.传统的K-D树等树形索引方法在高维空间中容易陷入"维度灾难",而主流的哈希散列方法(如局部敏感哈希)空间复杂度较高,在大规模数据下难以应用.本文总结了近年来基于向量量化的检索算法的相关研究,提出了一种基于GPU优化的高维数据近似近邻检索算法,在组合量化算法的基础上融合双层索引树结构与局部子空间最优化思想,在提高算法准确率的同时针对GPU模型优化算法,极大改善了检索性能,在单张GPU上实现了十亿量级高维数据的高效近似近邻检索.

基于密文KNN检索的室内定位隐私保护算法

在定位请求服务中,如何保护用户的位置隐私和位置服务提供商(Localization service provider,LSP)的数据隐私是关系到WiFi指纹定位应用的一个具有挑战性的问题。基于密文域的K-近邻(K-nearest neighbors,KNN)检索,本文提出了一种适用于三方的定位隐私保护算法,能有效提升对LSP指纹信息隐私的保护强度并降低计算开销。服务器和用户分别完成对指纹信息和定位请求的加密,而第三方则基于加密指纹库和加密定位请求,在隐私状态下完成对用户的位置估计。所提算法把各参考点的位置信息随机嵌入指纹,可避免恶意用户获取各参考点的具体位置;进一步利用布隆滤波器在隐藏接入点信息的情况下,第三方可完成参考点的在线匹配,实现对用户隐私状态下的粗定位,可与定位算法结合降低计算开销。在公共数据集和实验室数据集中,对两种算法的安全、开销和定位性能进行了全面的评估。与同类加密算法比较,在不降低定位精度的情况下,进一步增强了对数据隐私的保护。

稠密向量实体检索模型的二值化提速压缩

在实体检索任务中,为了从大规模实体库中高效筛选与查询相关的候选实体,可使用稠密向量检索模型.然而在现有的稠密向量检索模型中,由于实体向量维度较高,导致实时计算效率较低、存储空间较大.文中通过实验发现这些实体向量存在大量的冗余信息:一方面,绝大多数实体向量分布在互不相同的象限里;另一方面,语义相近的实体所在的象限也更近.因此,文中提出二值化的实体检索方法,用于压缩实体向量,加速相似度计算.具体而言,方法利用符号函数(sign),二值化压缩高维稠密的浮点向量,并通过汉明距离加快检索.从理论上分析文中方法保证检索性能的原因.通过定性、定量的分析实验验证理论的正确性,并给出基于随机升维旋转的二值检索性能改善方法.

量化误差的索引检索方法

为了提高乘积量化的近邻检索方法的检索精度,本文提出了量化误差的索引检索方法。该方法以子空间量化误差为依据进行子空间码字的选择,以获取高质量的乘积量化候选码字,提高基于乘积量化的近邻检索方法的检索精度。最后,通过把索引检索方法应用于5种基于乘积量化的索引结构上,在3个基准数据集上进行实验。实验结果表明,索引检索方法可以提高检索精度的有效性。

开放环境多分布特性的局部敏感哈希检索方法

基于局部敏感哈希的检索方法能够较好地解决高维大规模数据的近似近邻检索问题.但在开放环境下针对多种分布特性时,迄今尚未有令人满意的解决方案.利用Laplacian算子对数据分布剧烈变化敏感的特性,提出一种具有全局性、适用于开放环境下多种分布特性的基于Laplacian算子的局部敏感哈希搜索方法(LPLSH).该方法把Laplacian算子应用于数据投影的概率密度分布,找到数据投影分布的剧烈变化位置作为超平面的偏移量.从理论上证明了精简维度的哈希函数能够保持局部敏感性及低投影密度区间分割的有效性,分析了利用Laplacian算子计算的二阶导数对超平面偏移量设置的指导意义.与其他8种方法对比,LPLSH算法的F1值是其他方法最优值的0.8倍-5倍,耗费时间也大幅减少.通过对具有多种分布特性数据集上的实验验证,结果表明:LPLSH方法能够同时兼顾效率、精度和召回率,可满足开放环境下多分布特性的大规模高维检索的鲁棒性需求.

基于多GPU的千万级高维空间实时检索

海量高维数据的近邻检索一直是多媒体信息领域的重要研究课题。本文提出一种基于多GPU的并行高维空间距离检索排序算法,通过并行优化空间距离计算及排序过程,并充分利用GPU硬件特性和众多的流处理器单元,算法能实现百万级的高维数据的实时检索。在此基础上,研究并利用多GPU架构,提升并行效率,拓展实时数据查询的数据规模。实验结果表明,本文算法可达到千万级别高维数据的实时精确检索,极大地拓展了高维检索的应用范围。

基于随机森林的哈希检索算法

从海量数据中进行近似数据的检索是数据挖掘领域许多应用的关键。尤其近年来,数据的规模出现爆炸式增长,数据检索需面对海量数据和“维度灾难”的叠加考验,这使得传统最近邻算法效率降低,而近似最近邻算法发挥了越来越重要的作用。其中哈希算法以其在存储空间和计算时间上的优势受到了广泛关注。提出了一种基于随机森林的哈希算法。该算法通过构建随机森林,将原始空间的样本映射为海明空间的二进制哈希码,并在哈希空间上定义了顺序敏感的海明距离,以最大程度保持数据在原空间的近邻关系不变。由于随机森林中不同决策树所使用的特征空间和学习过程是独立的,可以以增量的方式灵活地确定哈希码的长度。此外基于随机森林的哈希编码算法天然适合并行部署,从而可以大大提高算法速度。最后,在MNIST和CIFAR-10数据集对所提算法进行了实验验证,结果表明了算法的有效性和出色性能。

基于CUDA的高维空间检索排序

高维空间的近邻检索是多媒体信息领域的重要研究课题.文章提出一种基于CUDA的高维空间距离检索排序算法,通过并行优化空间距离计算及排序过程,充分利用GPU硬件特性和它的并行运算能力,能极大地提高高维空间的检索速度,并可获取精确的距离排序数据.实验结果表明,该文算法可达到百万级别高维数据的实时检索,极大地拓展了高维检索的应用范围.

基于聚类索引树的高维近似检索算法

提出了一个基于聚类索引树的高维近似检索方法,详细描述了其建树算法和检索算法。由于传统索引对高维空间的k-近邻检索效率的提高非常有限,我们把近似检索和聚类索引树结合起来,从而用很小的精度损失换取很高的检索效率。实验表明,与精确检索相比,本方法的误差非常小,而检索速度大大优于其他方法,因此具有广泛的应用前景。

基于分层索引的高维数据对象检索

随着海量信息检索技术的发展,对文本、图片和视频等高维数据对象的相似性检索要求不断提高。局部敏感哈希(LSH)是解决高维数据近邻检索的主要方法之一,但存在索引存储代价高及查询效率低等问题。提出了一种基于二级混合索引模型构造方法,先利用溢出树(Spill tree)对数据集进行划分,再对每个部分构建基于LSH的哈希表,形成混合索引,支撑高维数据检索。试验表明,该方法缩小了高维数据对象的索引存储空间,提高了查询效率和查询质量。

基于卷积神经网络和监督核哈希的图像检索方法

当前主流的图像检索方法采用的视觉特征,缺乏自主学习能力,导致其图像表达能力不强,此外,传统的特征索引方法检索效率较低,难以适用于大规模图像数据.针对这些问题,本文提出了一种基于卷积神经网络和监督核哈希的图像检索方法.首先,利用卷积神经网络的学习能力挖掘训练图像内容的内在隐含关系,提取图像深层特征,增强特征的视觉表达能力和区分性;然后,利用监督核哈希方法对高维图像深层特征进行监督学习,并将高维特征映射到低维汉明空间中,生成紧致的哈希码;最后,在低维汉明空间中完成对大规模图像数据的有效检索.在Image Net-1000和Caltech-256数据集上的实验结果表明,本文方法能够有效地增强图像特征的表达能力,提高图像检索效率,优于当前主流方法.

基于指纹权重的音频模板检索方法

针对音频模板检索方法在噪音和频谱缺失等环境下鲁棒性不够强的问题,在原有Philips检索方法的基础上,提出了一种以帧能量差作为权重的检索方法,即充分利用原方法忽略的能量信息,通过对不同音频帧的DNA设置不同的匹配权重,有效提升了音频模板匹配方法的鲁棒性。实验结果表明,在受噪音影响和频谱缺失的数据集上,对于不同长度的音频模板,音频检索的查准率和查全率均有不同程度的提升,其中在2s的短模板上,查准率可比基线提高16%。

基于数据挖掘技术的地下工程目标毁伤效应计算方法

针对毁伤试验数据少、不均匀、不连续、范围窄等带来的计算精度不高的问题。研究通过数据挖掘技术进行毁伤效应计算。利用数据库管理毁伤数据,通过数据清洗技术识别并清除数据异常点,以保证数据库中数据的质量。建立了算法评价方法以选择最优经验算法。通过特征选择对高维毁伤数据进行降维,确定毁伤效应的主要控制参数进行神经网络学习和k-近邻检索。在此基础上建立基于数据融合的“三阶段”毁伤效应计算模型,可依据试验数据、经验算法和神经网络模型进行毁伤效应计算。实际应用表明,所提出的计算方法,能够满足实际应用需求。

熵选择多重二进制编码

为了解决查询高维浮点型数据的近邻点需要计算代价昂贵的欧式距离,内存占用率较高的问题,将高维浮点型数据通过哈希映射函数映射为低维二进制编码,并保证同一样本点在两种空间内的归一化距离满足相似性。从而在实现近邻检索任务时,可使用代价较低的汉明距离替换欧式距离,达到降低检索复杂度的目的。为保证由哈希函数生成的二进制编码具有较优的近邻检索性能,本文首先基于查找机制得到数据集适应空间分布特性的二进制标签,然后利用SVM算法得到二进制标签的分类平面,并选择其中具有最大熵值的平面函数作为最终的哈希映射函数。为了进一步提高近邻检索性能,在训练阶段,初始化多种不同的编码中心点用以生成多重二进制标签,并得到与此相应的多重哈希函数和多重二进制编码。在检索过程中,建立了基于多重二进制编码的近邻检索体系,返回具有较小平均汉明距离的样本点作为最终检索结果。实验结果表明:与其他现存优秀算法相比,本文算法可以快速、有效地将浮点型数据转化为二进制编码,而且基于这些二进制编码的近邻检索性能较优。

基于改良NB树的内存高维索引算法

基于内容的图像检索是近年来的热门研究内容,其中,有效的高维索引机制是使大规模图像库的检索能够达到实时性要求的关键技术。以往大部分学者都集中研究磁盘索引,但其实在目前大内存的环境下对内存索引的研究也是非常必要。本文运用PCA原理改进了一种理想的内存索引方法NB树,经过改进以后其检索性能得到进一步提高。

模糊序列感知哈希

为了解决传统哈希算法在图像近邻检索任务中的模糊排序问题,提出了模糊序列感知哈希,旨在学习满足首位区分规则的哈希函数,其可直接利用二值编码本身信息区分模糊序列,从而在近邻检索中无需额外计算比特位权值和加权汉明距离,能以较小的代价区分与查询样本具有相同汉明距离的数据点之间的序列。建立了类似于近邻检索性能评价指标平均准确率的目标函数,其属于序列保持约束条件,能够保证数据点对在汉明空间与欧式空间内具有相同的相对相似性,可确保所提算法适应于近邻检索任务。在训练过程中,对二值编码、汉明距离以及判断函数进行了连续化松弛处理,从而可直接采用批量梯度下降算法优化目标函数,降低了训练复杂度。在三种图像数据集上的对比实验证明,模糊序列感知哈希的近邻检索性能较优。

基于双向线性回归的监督离散跨模态散列方法

跨模态散列可以将异构的多模态数据映射为语义相似度保持的紧凑二值码,为跨模态检索提供了极大的便利.现有的跨模态散列方法在利用类别标签时,通常使用2个不同的映射来表示散列码和类别标签之间的关系.为更好地捕捉散列码和语义标签之间的关系,提出一种基于双向线性回归的监督离散型跨模态散列方法.该方法仅使用一个稳定的映射矩阵来描述散列码与相应标签之间线性回归关系,提升了跨模态散列学习精度和稳定性.此外,该方法在学习用于生成新样本散列码的模态特定映射时,充分考虑了异构模态的特征分布与语义相似度的保持.在2个公开数据集上与现有方法的实验结果验证了该方法在各种跨模态检索场景下的优越性.

基于改进局部敏感哈希的协同过滤推荐算法

传统推荐系统中存在用户评分数据高维稀疏、分布不均匀和传统用户相似度计算准确性低等问题,本文提出一种基于改进局部敏感哈希的协同过滤算法。首先利用改进局部敏感哈希算法对用户评分数据进行降维处理并构建索引,并使用相似度修正系数对用户相似度计算做出改进;然后利用索引敏捷切确地计算目标对象的近邻用户集合;之后选择近邻用户聚集的高相似度用户,使用加权算法对目标对象未评分项目进行评定预估。实验结果表明,对于非均匀用户评分数据的高维稀疏问题,该算法不仅能明显缩短近邻用户检索时间,且能有效提高推荐精度。