一种动态数据场景下的向量索引方法

本发明属于软件算法，具体涉及一种动态数据场景下的向量索引方法。

背景技术：

1、最近一段时间，向量作为一种表达图片、视频和文字等非结构化数据的数据类型受到越来越多关注。电商平台通过将图像转换成向量实现图片搜索功能，自然语言科学将文本转换成向量实现语义分析，机器视觉、语音识别和个性化广告等领域也广泛使用向量数据类型。

2、众多针对不同使用场景特性的近似最近邻搜索引擎诞生，这些近似最近邻搜索引擎使用的近似最近邻算法主要分为4种，分别是基于hash、基于pq(productquantization)、基于图和基于树的方法。但是现有的近似最近邻算法对动态添加和删除数据支持的并不完善，大部分算法虽然可以同时获得很高的召回率和搜索效率，但是在构建索引时需要提前知道数据集或训练集，即大概知道数据集中数据的分布规律。大部分算法即使实现了删除功能，其实现方式也只是简单的标记被删除数据，并没有真正删除索引中的数据。当这些算法被引入到数据库应用场景时，已知的做法是暂存新添加的向量，标记被删除的向量，然后周期性的进行全量更新，这样做的代价非常大，当数据规模很大时显然不是一种优雅的方法。

3、基于图的近似最近邻算法自提出以来收到了大量关注。文献“hajebi k，abbasi-yadkori y，shahbazi h，et al.fast approximate nearest-neighbor search with k-nearest neighbor graph twenty-second international joint conference onartificial intelligence.2011”提出了k-nn图。文献“malkov y，ponomarenko a，logvinov a，et al.approximate nearest neighbor algorithm based on navigablesmall world graphs.information systems，2014，45：61-68”提出了一种基于可导航的小世界(navigable small world，nsw)图的近似最近邻搜索算法，图中顶点对应向量，边对应于它们之间的连接，在搜索最近邻时使用贪心搜索算法。文献“malkov y a，yashunin da.efficient and robust approximate nearest neighbor search using hierarchicalnavigable small world graphs.ieee transactions on pattern analysis andmachine intelligence，2018，42(4)：824-836”基于nsw提出分层的可导航小世界(hierarchical nsw，hnsw)图的近似最近邻搜索方法，极大的加速了搜索效率。文献“fu c，xiang c，wang c，et al.fast approximate nearest neighbor search with thenavigating spreading-out graph.arxiv preprint arxiv：1707.00143，2017.”在观察先前的基于图的近似最近邻算法之后，首先明确四个方面：确保图的连通性；降低图的平均出度；缩短搜索路径；减少索引大小。然后，提出了一种满足上述四个方面的新的图结构：导航展开图(navigating spreading-out graph，nsg)。文献“jayaram subramanya s，devvritf，simhadri h v，et al.diskann：fast accurate billion-point nearest neighborsearch on a single node.advances in neural information processing systems，2019，32”提出了一种新的图构建算法：vamana，并将其扩展到ssd(固态硬盘)上。

4、大量的实验和文献表明，基于hash的算法简单、高效、容易实现，但是准确度低。基于pq的算法简单且准确性好，但是当数据量大时几乎不可用。基于图的算法虽然没有理论的保证，但是在搜索效率和召回率方面取得了非常好的平衡，缺点是构建图的时间很长且内存消耗大。基于树的算法在低纬度时效率更高，维度增大时效率会降低。

5、随着大数据的广泛应用和对向量数据管理需求增加，向量数据与传统数据库结合势在必行，主要工作内容集中在面向使用场景对现有近似最近邻搜索算法进行改造，例如，在与传统结构化数据结合后进行混合查询，或是搜索引擎与数据库结合后的层次化系统设计。

6、综上所述，许多高效、灵活的近似最近邻搜索算法与近似最近邻搜索引擎被提出，但是仍然缺失支持动态数据流的高效近似最近邻算法。因此迫切需要一种支持实时添加和删除数据的索引结构，为大数据和人工智能等应用提供高效灵活的向量索引方式。

技术实现思路

1、为解决上述技术问题，本发明提供了一种动态数据场景下的向量索引方法，旨在突破当前主流算法仅支持静态数据集的不足，实现近似最近邻算法在动态数据流模式下的应用，探索高性能的向量索引关键技术，为人工智能、大数据等技术更大范围的应用提供有效支撑。

2、本发明采用的技术方案为：一种动态数据场景下的向量索引方法，具体步骤如下：

3、s1、构建一种基于覆盖率的混合步长索引结构：混合步长图hsg；

4、s2、基于步骤s1，在混合步长图hsg中进行近似最近邻搜索；

5、s3、基于步骤s1，实现基于相对距离的顶点添加算法；

6、s4、基于步骤s1，实现基于入边权重的hsg顶点删除算法；

7、s5、基于步骤s1，基于覆盖率进行索引图评价和迭代优化；

8、s6、基于步骤s2-s5，近似最近邻算法在动态数据流模式下实时添加、删除数据，迭代优化索引结构，实现高性能的向量索引。

9、进一步地，所述步骤s1具体如下：

10、所述hsg中，同时存在长边和短边，长边和短边通过相对距离划分；短边来自k-ann图，即对索引图中任意顶点，连接索引图中距离其最近的k个顶点作为邻居；同时，若存在一条边，该边的任意一个顶点不属于另外一个顶点的k近似最近邻，则这条边是长边。

11、其中，短边负责搜索与目标相似度最高的k个近似最近邻，长边负责从图的起始顶点开始快速搜索与查询目标相似度较高的顶点；所述hsg选择单独限制短边与长边的平均度数，不需要数据集全局信息，且支持索引图增量更新。

12、进一步地，所述步骤s2具体如下：

13、s21、输入查询向量，添加起始顶点到等待队列，并添加等待队列队头顶点的长边邻居到等待队列中；

14、对于任意一次近似最近邻搜索，输入查询向量，添加起始顶点到等待队列，从起始顶点开始，通过长边快速搜索距离查询目标距离较近的顶点，且只计算当前等待队列队头顶点的长边邻居和目标顶点的距离，并添加等待队列队头顶点的长边邻居到等待队列。

15、s22、当一轮迭代后，判断等待队列队头顶点是否改变，若有改变则重复步骤s21直至无改变，若无改变则进入步骤s23；

16、s23、取出等待队列队头顶点，添加队头顶点的短边邻居到等待队列，将队头顶点添加到top队列，并判断top队列是否添加成功；

17、通过短边搜索高质量的k个近似最近邻，若结果队列小于k或等待队列队头顶点和目标顶点的距离小于结果队列的最大值，则将等待队列队头顶点添加到结果队列中并从等待队列中删除，否则添加失败，搜索结束，返回结果队列。若添加成功，将队头顶点的短边邻居添加到等待队列中，重复步骤s23直至添加失败。

18、进一步地，所述步骤s3具体如下：

19、s31、输入添加的向量，对目标向量进行近似最近邻搜索；

20、从起始顶点开始搜索距离目标顶点最近的k个顶点；返回的结果包括：k个近似最近邻、整个搜索过程中全部被访问过的顶点。

21、其中，top-k列表中的顶点即被添加为目标顶点的短边邻居，在搜索过程中被访问过的且不在top-k列表中的顶点被添加为目标顶点的长边邻居。

22、s32、根据步骤s31返回的结果添加短边邻居；

23、在添加短边时，判断top-k列表中的顶点是否要添加新的顶点作为它们的邻居，当top-k列表中的顶点的短边邻居数已达到度数限制，即需要删除距离最大的邻居，然后再添加新的顶点作为邻居。

24、其中，删除边会导致两个问题，具体如下：

25、(1)连通图变成非连通图；

26、(2)早期添加的短边因后添加的顶点被裁剪，而早期添加的短边应该作为一条长边而存在。

27、若出现问题(1)，通过广度优先遍历判断图的连通性，若因为删除该边导致图的不连通，将这条边保存到一个特殊的集合中，即用于保持图的连通性。若出现问题(2)，调整参数在裁剪长边时让老的长边被保留，而对于被删除的短边，不实际删除，将其移动到长边集合中。

28、s33、根据步骤s31返回的结果添加长边邻居；

29、所述返回的结果为一个按照与新添加顶点距离从大到小排序的有序队列，分为两部分，队列一是在搜索过程中通过长边遍历到的顶点，队列二是通过短边遍历到的顶点。

30、若队列二中顶点数量小于x，则不添加长边；若队列二中的顶点数量等于x，则添加一条从队列一队尾顶点指向新添加顶点的长边；若队列二中的顶点的数量大于x，则先添加一条从队列一队尾顶点指向队列二中第x个顶点的长边，然后从队列二中的第x顶点开始，每隔x个顶点添加一条从上一被添加长边入边的顶点指向该顶点的长边。

31、其中，x表示可选参数。

32、进一步地，所述步骤s4具体如下：

33、s41、输入删除向量，首先删除目标顶点的所有短边，对目标顶点的短边邻居以其自身和被删除顶点为起点做一次1-ann搜索；

34、s42、若顶点的度数小于k则做短边邻居补偿操作，补偿短边完成后删除目标向量的所有长边；

35、s43、根据搜索算法，在步骤s21后不再使用长边，所以要避免非连通长边图的产生，判断被删除的目标顶点长边的入边数和出边数相乘是否大于预先设定的阈值t；

36、其中，t表示用户指定的参数；若目标顶点长边的入边数和出边数相乘小于t，则使用长边补偿算法一；若目标顶点长边的入边数和出边数相乘大于t，则使用长边补偿算法二，具体如下：

37、(1)长边补偿算法一：基于权重的补偿算法；

38、对被删除顶点的长边的入边的距离进行加和，记为ds，任意一条入边的距离记为di，按照di/ds的概率连接被删除顶点的入边邻居和被删除顶点的出边邻居。

39、(2)长边补偿算法二：用距离最近的顶点代替目标顶点；

40、找到一个顶点代替被删除顶点，挑选与被删除顶点距离最近的顶点，转移被删除顶点的所有长边到该顶点上。

41、进一步地，所述步骤s5具体如下：

42、s51、输入参数x，从起始顶点开始进行广度优先遍历；

43、设顶点集vr为可通过长边到达的顶点的集合，以vr中的顶点为起始顶点做x轮广度优先遍历获得可覆盖顶点的集合vc，输出覆盖率|vr+vc|/|v|。

44、其中，x表示可选参数，顶点集v表示全部顶点的集合。

45、若覆盖率大于预先设定的覆盖率阈值，则遍历结束后输出覆盖率，若覆盖率小于预先设定的覆盖率阈值，则进入步骤s52。

46、s52、基于步骤s51得到的覆盖率，进行迭代优化；

47、在计算覆盖率时，得到顶点集vm＝v-vr-vc，即被遗漏顶点的集合，对vm中的所有顶点，以其自身为起点通过短边进行x轮广度优先遍历，记录下vm中每一个顶点在遍历时遇到的属于vm中的顶点的数量，选择数量最大的顶点重新添加长边，再以该顶点为起始点进行x轮广度优先遍历，重复步骤s52直至覆盖率达标。

48、本发明的有益效果：本发明的方法通过构建一种基于覆盖率的混合步长索引结构hsg，提出基于hsg索引结构的近似最近邻搜索算法、基于相对距离的顶点添加算法、基于入边权重的hsg顶点删除算法，并基于覆盖率进行索引图评价和迭代优化，最后基于hsg索引结构，近似最近邻算法在动态数据流模式下实时添加、删除数据，迭代优化索引结构，实现高性能的向量索引。本发明的方法解决了当前主流算法仅支持静态数据集的文艺，能在动态数据流模式下实时添加、删除数据，且能够迭代优化索引结构，提升搜索效率和召回率，为人工智能、大数据等技术更大范围的应用提供了有效支撑，为更广泛，更大规模的向量相似度检索机制研究提供了理论参考和实践依据。

技术特征：

1.一种动态数据场景下的向量索引方法，具体步骤如下：

2.根据权利要求1所述的一种动态数据场景下的向量索引方法，其特征在于，所述步骤s1具体如下：

3.根据权利要求1所述的一种动态数据场景下的向量索引方法，其特征在于，所述步骤s2具体如下：

4.根据权利要求1所述的一种动态数据场景下的向量索引方法，其特征在于，所述步骤s3具体如下：

5.根据权利要求1所述的一种动态数据场景下的向量索引方法，其特征在于，所述步骤s4具体如下：

6.根据权利要求1所述的一种动态数据场景下的向量索引方法，其特征在于，所述步骤s5具体如下：

技术总结
本发明公开了一种动态数据场景下的向量索引方法，通过构建一种基于覆盖率的混合步长索引结构HSG，提出基于HSG索引结构的近似最近邻搜索算法、基于相对距离的顶点添加算法、基于入边权重的HSG顶点删除算法，并基于覆盖率进行索引图评价和迭代优化，最后基于HSG索引结构，近似最近邻算法在动态数据流模式下实时添加、删除数据，迭代优化索引结构，实现高性能的向量索引。本发明的方法解决了当前主流算法仅支持静态数据集的文艺，能在动态数据流模式下实时添加、删除数据，且能够迭代优化索引结构，提升搜索效率和召回率，为人工智能、大数据等技术更大范围的应用提供了有效支撑，为更广泛，更大规模的向量相似度检索机制研究提供了理论参考和实践依据。

技术研发人员：卞浩文,薛瑞尼,张德申
受保护的技术使用者：电子科技大学
技术研发日：
技术公布日：2024/9/23