应用多索引加法量化编码的近邻检索算法

目的 海量图像检索技术是计算机视觉领域研究热点之一,一个基本的思路是对数据库中所有图像提取特征,然后定义特征相似性度量,进行近邻检索。海量图像检索技术,关键的是设计满足存储需求和效率的近邻检索算法。为了提高图像视觉特征的近似表示精度和降低图像视觉特征的存储空间需求,提出了一种多索引加法量化方法。方法 由于线性搜索算法复杂度高,而且为了满足检索的实时性,需把图像描述符存储在内存中,不能满足大规模检索系统的需求。基于非线性检索的优越性,本文对非穷尽搜索的多索引结构和量化编码进行了探索新研究。利用多索引结构将原始数据空间划分成多个子空间,把每个子空间数据项分配到不同的倒排列表中,然后使用压缩编码的加法量化方法编码倒排列表中的残差数据项,进一步减少对原始空间的量化损失。在近邻检索时采用非穷尽搜索的策略,只在少数倒排列表中检索近邻项,可以大大减少检索时间成本,而且检索过程中不用存储原始数据,只需存储数据集中每个数据项在加法量化码书中的码字索引,大大减少内存消耗。结果 为了验证算法的有效性,在3个数据集SIFT、GIST、MNIST上进行测试,召回率相比近几年算法提升4%~15%,平均查准率提高12%左右,检索时间与最快的算法持平。结论 本文提出的多索引加法量化编码算法,有效改善了图像视觉特征的近似表示精度和存储空间需求,并提升了在大规模数据集的检索准确率和召回率。本文算法主要针对特征进行近邻检索,适用于海量图像以及其他多媒体数据的近邻检索。     

MapReduce框架下基于R-树的k-近邻连接算法

针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理。首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了 R-树索引快速构建算法和基于 R-树的并行 k-近邻连接算法。在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达。在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用 R-树索引进行 k-近邻连接查询,提高了查询效率。从理论上分析了所提出算法的通信和计算代价。实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值。     

量化编码的分层可通航小世界图算法

随着大数据和人工智能的高速发展,针对多媒体数据的结构化处理与基于内容的检索受到极大的关注,面对多媒体数据结构化后的海量高维特征向量,如何快速、准确地检索是人工智能处理大规模数据所必须解决的问题。最近提出的分层可通航小世界图HNSW检索算法在多个公开数据集取得了最佳的性能表现,但该算法存在内存开销大的问题。而基于量化编码的检索算法能够压缩数据集向量,大幅度降低内存占用。将量化编码和分层可通航小世界图算法结合,提出了2种基于量化编码改进的HNSW算法,分别是使用标量量化编码向量的HNSWSQ算法和使用乘积量化编码向量的HNSWPQ算法,2种算法使用不同的量化策略存储原始向量编码,以降低内存开销,再通过HNSW算法建立索引达到缩短检索耗时的目的。其中HNSWSQ算法在多个数据集上获得了与HNSW算法相近的查全率和平均检索耗时,而内存开销大幅降低。实验结果表明,HNSWSQ算法在SIFT-1M和GIST-1M数据集上的内存开销比HNSW算法分别降低了45.1%和70.4%。     

基于Simhash的安全密文排序检索方案

针对密文检索中存在的计算量大、检索效率不高的问题，提出一种基于Simhash的安全密文排序检索方案。该方案基于Simhash的降维思想构建安全多关键词密文排序检索索引（SMRI），将文档处理成指纹和向量，利用分段指纹和加密向量构建B+树，并采用"过滤-精化"策略进行检索和排序，首先通过分段指纹的匹配进行快速检索，得到候选结果集；然后通过计算候选结果集与查询陷门的汉明距离和向量内积进行排序，带密钥的Simhash算法和安全k近邻（SkNN）算法保证了检索过程的安全性。实验结果表明，与基于向量空间模型（VSM）的方案相比，基于SMRI的排序检索方案计算量小，能节约时间和空间成本，检索效率高，适用于海量加密数据的快速安全检索。     

一种基于VARdnn-Tree的反向最近邻查询方法*

空间数据库中反向最近邻查询在低维查询时一般利用基于R-Tree的改进树作为索引结构,由于树型索引结构本身的限制,R-Tree等索引结构的查询在高维中都会出现维数灾难。针对这个问题,提出了一种基于VARdnn-Tree的索引结构,采用量化压缩的方法存储数据,能够有效地支持高维查询。     

基于流形空间的交互式人脸图像索引

认知科学表明基于流形学习的人脸图像检索能准确反映人脸图片的内在相似性和人类的视觉感知本质. 提出一种基于相关反馈的人脸高维索引方法--NDL,以提高人脸图像检索的性能.同时在该索引基础上提出一种流形空间下的相似查询--虚拟k近邻查询(Vk-NN), 该查询方法特别为基于NDL的人脸检索而设计.首先通过在一定阈值约束下计算任何两个人脸图片的相似度,建立一个称为邻接距离表(NDL)的二维距离图. 同时将距离值用B+-树建立索引.最后, 高维流形空间的Vk-NN查询转化为一维空间的基于B+树的查询. 实验表明:NDL索引在流形空间的检索效率明显优于顺序检索,特别适合海量人脸图片的检索.     

大型网络中近似子图匹配研究

为降低噪声对近似子图匹配准确率的影响,提出一种改进的近似子图匹配方法。在预处理阶段,利用k-近邻顶点集为数据图中的每个顶点建立标签-权重向量索引。在查询过程中,基于单个近邻标签的权重距离和所有近邻标签的整体匹配程度进行两级过滤,生成顶点候选集,采用生成树匹配和图匹配的方式确定查询图在大型网络中的位置。在真实数据集上的实验结果表明,该方法具有较高的执行效率和匹配准确率。     

哈夫曼编码乘积量化的图像哈希检索方法

目的 基于哈希编码的检索方法是图像检索领域中的经典方法。其原理是将原始空间中相似的图片经哈希函数投影、量化后,在汉明空间中得到相近的哈希码。此类方法一般包括两个过程：投影和量化。投影过程大多采用主成分分析法对原始数据进行降维,但不同方法的量化过程差异较大。对于信息量不均衡的数据,传统的图像哈希检索方法采用等长固定编码位数量化的方式,导致出现低编码效率和低量化精度等问题。为此,本文提出基于哈夫曼编码的乘积量化方法。方法 首先,利用乘积量化法对降维后的数据进行量化,以便较好地保持数据在原始空间中的分布情况。然后,采用子空间方差作为衡量信息量的标准,并以此作为编码位数分配的依据。最后,借助于哈夫曼树,给方差大的子空间分配更多的编码位数。结果 在常用公开数据集MNIST、NUS-WIDE和22K LabelMe上进行实验验证,与原始的乘积量化方法相比,所提出方法能平均降低49%的量化误差,并提高19%的平均准确率。在数据集MNIST上,与同类方法的变换编码方法（TC）进行对比,比较了从32 bit到256 bit编码时的训练时间,本文方法的训练时间能够平均缩短22.5 s。结论 本文提出了一种基于多位编码乘积量化的哈希方法,该方法提高了哈希编码的效率和量化精度,在平均准确率、召回率等性能上优于其他同类算法,可以有效地应用到图像检索相关领域。     

基于相对距离哈希方法的一种高维索引

人们设计了许多索引以有效地处理高维空间中的近邻查询和区域查询。已经证明,维数较高时利用高维索引处理这两类查询几乎不可能比线性扫描快。提出了一种两层索引以自适应地识别数据集中的聚簇;数据集具有聚簇特性时,用该索引处理邻近查询和区域查询比现有的索引结构快;对其他数据集,利用该索引处理邻近查询和区域查询与线性扫描大致相当。该索引的上层结构将一些参考点组织成一棵二叉树,下层结构是一系列动态哈希表。数据集中的数据点根据它们到参考点的相对距离被哈希到相应的哈希桶中。查询处理时用查询点到参考点的距离进行剪除搜索。实验表明,提出的索引结构具有良好的性能。     

基于相对距离哈希方法的一种高维索引

人们设计了许多索引以有效地处理高维空间中的近邻查询和区域查询。已经证明,维数较高时利用高维索引处理这两类查询几乎不可能比线性扫描快。提出了一种两层索引以自适应地识别数据集中的聚簇;数据集具有聚簇特性时,用该索引处理邻近查询和区域查询比现有的索引结构快;对其他数据集,利用该索引处理邻近查询和区域查询与线性扫描大致相当。该索引的上层结构将一些参考点组织成一棵二叉树,下层结构是一系列动态哈希表。数据集中的数据点根据它们到参考点的相对距离被哈希到相应的哈希桶中。查询处理时用查询点到参考点的距离进行剪除搜索。实验表明,提出的索引结构具有良好的性能。     

Batch Nearest Neighbor Search for Video Retrieval

To retrieve similar videos to a query clip from a large database, each video is often represented by a sequence of high- dimensional feature vectors. Typically, given a query video containing m feature vectors, an independent nearest neighbor (NN) search for each feature vector is often first performed. After completing all the NN searches, an overall similarity is then computed, i.e., a single content-based video retrieval usually involves m individual NN searches. Since normally nearby feature vectors in a video are similar, a large number of expensive random disk accesses are expected to repeatedly occur, which crucially affects the overall query performance. Batch nearest neighbor (BNN) search is stated as a batch operation that performs a number of individual NN searches. This paper presents a novel approach towards efficient high-dimensional BNN search called dynamic query ordering (DQO) for advanced optimizations of both I/O and CPU costs. Observing the overlapped candidates (or search space) of a pervious query may help to further reduce the candidate sets of subsequent queries, DQO aims at progressively finding a query order such that the common candidates among queries are fully utilized to maximally reduce the total number of candidates. Modelling the candidate set relationship of queries by a candidate overlapping graph (COG), DQO iteratively selects the next query to be executed based on its estimated pruning power to the rest of queries with the dynamically updated COG. Extensive experiments are conducted on real video datasets and show the significance of our BNN query processing strategy.     

Fast additive quantization for vector compression in nearest neighbor search

Vector quantization has been widely employed in nearest neighbor search because it can approximate the Euclidean distance of two vectors with the table look-up way that can be precomputed. Additive quantization (AQ) algorithm validated that low approximation error can be achieved by representing each input vector with a sum of dependent codewords, each of which is from its own codebook. However, the AQ algorithm relies on computational expensive beam search algorithm to encode each vector, which is prohibitive for the efficiency of the approximate nearest neighbor search. In this paper, we propose a fast AQ algorithm that significantly accelerates the encoding phase. We formulate the beam search algorithm as an optimization of codebook selection orders. According to the optimal order, we learn the codebooks with hierarchical construction, in which the search width can be set very small. Specifically, the codewords are firstly exchanged into proper codebooks by the indexed frequency in each step. Then the codebooks are updated successively to adapt the quantization residual of previous quantization level. In coding phase, the vectors are compressed with learned codebooks via the best order, where the search range is considerably reduced. The proposed method achieves almost the same performance as AQ, while the speed for the vector encoding phase can be accelerated dozens of times. The experiments are implemented on two benchmark datasets and the results verify our conclusion.     

参数自适应下基于近邻图的近似最近邻搜索

现有基于近邻图的近似最近邻搜索（ANNS）算法通常将数据库中被检索向量组织成近邻图结构,根据用户设定参数搜索查询向量的近似最近邻。为提升基于近邻图的ANNS算法在给定召回率下的搜索效率,提出一种参数自适应方法AdaptNNS。采集数据库中的被检索向量并对采样结果进行聚类,利用聚类中心向量和最近邻分类器提取查询负载特征,同时将查询负载特征与不同的召回率相结合作为输入特征训练梯度提升决策树（GBDT）模型。在查询处理过程中,根据应用程序指定的召回率获取最终输入特征,并通过GBDT模型预测最优搜索参数,提升ANNS算法的吞吐量。在Text-to-Image、DEEP和Turing-ANNS数据集上的实验结果表明,当达到相同的目标召回率时,AdaptNNS方法相比于Baseline方法最多可将DiskANN和HNSW算法的吞吐量提升1.3倍,具有更高的近似最近邻搜索效率。     

一种基于椭圆体聚类的高维索引方法

提出一种在椭圆体聚类上进行主分量排序的高维索引方法, 线性访问较少的数据点就可完成k近邻搜索过程。该方法对数据集进行椭圆体聚类划分,在KL变换域上建立近似向量。在k近邻搜索过程中,采用部分失真搜索算法,按照距离下界由小到大的顺序依次搜索各个椭圆体聚类。在大型高维图像特征库上的实验表明,与其他向量近似方法相比,该索引结构降低近似向量的访问数量,能够较显著提高k近邻搜索速度。     

面向高维数据集的近邻顺序查询方法

对顺序索引方法进行了研究,提出一种基于向量近似的高维顺序索引结构,该结构顺序访问部分文件就能完成k近邻查询。在查询过程中依据投影值来终止查询过程,依据距离来排除不匹配的数据。为进一步降低数据访问率,采用椭圆体聚类算法对数据集进行划分。新索引结构支持以多个顺序访问过程完成k近邻查询,能够同时降低查询过程中的I/O开销和CPU开销。在大型高维图像特征库上的实验表明,新的高维索引结构的查询性能优于其他高维索引方法。     

球面上的最近邻查询方法研究

球面上的最近邻查询在空间数据库最近邻查询领域具有重要的意义。为了处理球面上的最近邻查询问题,针对球面上数据对象点的特征和近邻查询的需要,给出了处理球面上最近邻查询的3种方法：利用球面voronoi图计算最近邻方法（VNS）;利用欧氏空间内的空间数据索引结构方法（SPINS）和降维方法（APNS）。进一步,在动态的密集数据集和动态的稀松数据集两种典型的组合情况下分别着重对3 种方法处理最近邻查询的性能进行了实验比较。理论分析和实验结果表明,给出的3种方法可较好地处理球面上具有不同性质特征的空间数据对象点的近邻查询问题。