向量数据库与知识库检索架构图

向量数据库作为现代知识库检索系统的核心组件，扮演着至关重要的角色。以下是对向量数据库及其在知识库检索中应用的详细介绍，以及不同索引方法的解析。

1. 向量数据库介绍

向量数据库是存储和检索高维向量数据的系统，它能够支持复杂的查询操作，如相似性搜索等。

2. 索引方法概览

索引方法对于提高向量数据库的检索效率至关重要。以下是一些常见的索引技术：

• 倒排索引：一种将文档中出现的词语与文档ID关联起来的索引结构。
• KNN 搜索：K最近邻搜索，用于找到与查询点距离最近的K个点。
• 近似 KNN 搜索：在保证一定精度的前提下，提高KNN搜索的效率。
• Product Quantization (PQ)：一种将高维向量量化到较低维度的技术，以加速相似性搜索。
• NSW 算法搜索：一种基于图的搜索算法，用于高效地进行向量搜索。
• HNSW：分层导航小世界图，一种改进的图搜索算法，提供更快的搜索速度和更好的可扩展性。

3. 知识库检索架构图

下图展示了构建知识库检索的架构图，其中包含了向量数据库和其他组件的交互方式。 该架构图清晰地展示了向量数据库在知识库检索系统中的位置和作用，以及如何与其他组件协同工作以实现高效的检索。

在处理自然语言处理任务时，向量数据库扮演着至关重要的角色。以下是对向量数据库及其索引方法的介绍：

向量数据库概述

向量数据库的核心功能是将文档数据转换为向量形式，并存储于数据库中。用户查询时，系统会将查询语句转换为向量，然后在数据库中检索与查询向量相似度最高的TOP N条数据。

查询流程

1. 数据向量化：首先，将文档数据转换为向量嵌入形式，并存储于向量数据库中。2. 查询向量化：用户输入查询语句后，系统将其转换为向量形式。3. 相似度检索：在向量数据库中检索与查询向量相似度高的TOP N条数据。4. 结果排序与构造：对检索结果进行排序，并选取部分数据构造成prompt，用于与大型语言模型（LLM）进行交互查询。

索引方法

向量数据库使用多种索引方法来提高检索效率，以下是一些常见的索引技术：

• 倒排索引：一种索引结构，用于存储文档中单词与其出现位置的映射关系。- KNN：K-最近邻算法，用于找到与查询向量距离最近的K个点。- Approximate KNN：近似K-最近邻算法，用于在大规模数据集中快速找到近似的最近邻。- Product Quantization：一种用于大规模向量压缩和索引的技术，通过量化技术减少存储需求。- HSNW：Hierarchical Navigable Small World图，一种用于高效近似最近邻搜索的图结构。

算法设计理念

每种索引方法都有其独特的设计理念和方法，例如：

• 倒排索引通过建立倒排表来加速关键词的检索。- KNN算法通过计算欧氏距离或余弦相似度来确定最近邻。- Approximate KNN通过牺牲一定的精度来换取检索速度。- Product Quantization通过量化向量空间来减少存储和计算成本。- HSNW通过构建层次化的小世界网络来快速导航至目标区域。 这些方法在不同的应用场景下各有优势，选择合适的索引技术对于提高系统性能至关重要。
  

开源向量数据库概述

在大数据时代，向量数据库作为处理高维数据的关键技术，越来越受到重视。目前，开源向量数据库领域中，Chroma、Milvus 和 Weaviate 这三种技术尤为突出。本文将对这三种技术进行介绍，并分析它们之间的区别。

ChromaChroma 是一个高性能的向量数据库，专为处理大规模向量数据而设计。它支持多种数据类型，并提供高效的索引和搜索功能。

MilvusMilvus 是一个开源的向量数据库，它提供了丰富的API接口，支持多种编程语言，便于开发者集成和使用。

WeaviateWeaviate 是一个具有创新性的向量数据库，它不仅支持向量搜索，还支持机器学习模型的集成，使得数据检索更加智能化。

发展历程开源向量数据库的发展经历了多个阶段，从最初的基础功能到现在的多样化和智能化，这一过程见证了技术的不断进步和创新。

推荐阅读如果你对开源向量数据库感兴趣，可以阅读以下文章深入了解：三大开源向量数据库大比拼。

它们用到的索引方法如下：

索引方法

倒排索引

在处理大规模文本数据时，倒排索引是一种高效的数据组织方式。以下是对倒排索引及其优化方法的详细解析：

1. 倒排索引原理： - 倒排索引将文本数据切分为单词，并记录每个单词出现的位置。 - 例如，对于文本“大模型”，其对应的倒排索引可能包含所有包含该词的文档索引集合。
2. 查询过程： - 将查询语句“大模型的应用会在2024年有哪些发展？”切分为关键单词：“大模型”，“2024年”，“发展”。 - 通过求这些单词索引集合的交集，实现数据的初步召回。
3. 召回后处理： - 召回的数据与查询语句的相似度可能不同，需要进一步排序以选取最相关的TOP N结果。
4. 向量化检索： - 为了提高检索效率，可以将文本数据转化为向量。 - 通过计算向量间的相似度和距离，实现更精确的相似度检索。
5. 优化方法： - 向量化检索通过减少直接文本匹配的复杂度，加速了相似度检索过程。
6. 实际应用： - 在大数据环境下，向量化检索可以有效提升检索效率和准确性。 以上是对倒排索引及其优化方法的概述。通过向量化处理，我们可以在保持检索准确性的同时，显著提高检索速度。
   

KNN 搜索

KNN 搜索叫做 K 近邻搜索，将查询语句转换为向量，然后再求该向量与数据库中的向量相似度最高，距离最近的向量集。

在处理大规模数据集时，我们经常会遇到需要快速检索相似性或距离度量的问题。本文将介绍两种检索方法：精确检索和近似KNN搜索，并分析它们的时间和空间复杂度。

精确检索精确检索是一种直接在数据集中寻找与查询向量最相似或距离最近的向量的方法。其时间复杂度为O(N)*O(d)，其中N是数据集中向量的数量，d是向量的维度。以一个数据库为例，如果存储了10000个维度为1024向量，那么查询最相似向量maxSim(q,v)或最近距离向量minDist(q,v)的时间复杂度将是O(10000)*O(1024)。

优点- 精确度高：能够找到与查询向量最接近的向量。

缺点- 速度慢：随着数据集的增大，检索时间显著增加。

近似KNN搜索近似KNN搜索是一种优化的检索方法，它通过将搜索空间划分为多个块，先确定最接近的块，然后在该块内进一步寻找最相似或最近的点。这种方法可以显著减少搜索时间，但可能会牺牲一些精度。

过程1. 将数据空间划分为多个块。2. 确定查询点所在的块或最接近的块。3. 在选定的块内进行KNN搜索。

优点- 速度快：通过减少搜索范围来加速检索过程。

缺点- 精度可能降低：由于搜索空间的划分，可能错过最优解。

结论选择精确检索还是近似KNN搜索取决于具体应用场景的需求。如果对精度要求极高，可以选择精确检索；如果对检索速度有较高要求，可以选择近似KNN搜索。

其中每个块中都会有一个中心点，计算查询点与块的距离就是计算查询点到每个块的中心点的距离：

在进行空间查询时，我们经常会遇到需要确定查询点与特定区域块的关系。以下是对上述查询步骤的重新梳理和描述：

1. 确定查询点的最近块：首先，我们需要找到查询点距离最近的块。在这个例子中，C6块是距离查询点最近的块。
2. 查询块内最近点：接下来，我们需要在C6块内找到距离查询点最近且相似度最高的点。
3. 考虑块外点：然而，通过观察我们发现，尽管红色和橙色块的中心点距离查询点较远，但它们块内的某些点可能更接近查询点。这就需要我们扩大搜索范围，考虑这些块内的点。
4. 扩大搜索范围：为了更准确地找到与查询点距离近且相似度高的点，我们需要调整搜索策略，不仅局限于最近的块，还要考虑其他可能包含更近点的块。 通过上述步骤，我们可以更全面地评估查询点与各个块内点的关系，从而得到更准确的查询结果。
   

下边是求相似度最高和距离最近的算法公式，其中相似度最高（COS_SIM）是通过余弦计算，距离最近有两种算法，欧式算法和曼哈顿算法，这里就不展开讲解了：

产品量化（Product Quantization，PQ）

概述 产品量化（PQ）算法是一种用于高效处理高维向量数据的量化技术。其核心思想是将高维空间划分为多个子空间，并在每个子空间内确定一个中心点（centroid），类似于K近邻（KNN）算法中的K个最近邻。 步骤一：子空间划分 PQ算法首先将整个高维空间划分为多个较小的子空间。每个子空间都拥有一个特定的中心点，这个中心点是该子空间内所有点的代表。 步骤二：向量分解 接下来，算法将原始的高维向量分解为多个低维的向量子向量。每个子向量都与一个子空间相对应。 步骤三：PQ ID 计算 对于每个子向量，算法会计算它与子空间中心点的距离，并使用最近的中心点来标识该子向量。这样，原始的高维向量就可以通过多个PQ ID来表示。 优势 通过PQ算法，原始的高维向量可以被压缩为较短的PQ ID序列，从而大大减少了存储空间的需求，同时保持了向量之间的相对距离关系。 应用场景 PQ算法广泛应用于大规模向量检索、机器学习特征压缩等领域，特别是在需要处理大量数据且对存储空间有限制的情况下，PQ算法提供了一种有效的解决方案。

Product Quantization（PQ）算法是一种用于高效检索高维向量的近似最近邻搜索技术。以下是使用PQ算法进行向量数据库查询的步骤：

1. 查询向量的转换：首先，将查询语句转换为一个查询向量。这个查询向量是用户希望在数据库中查找相似度最高的向量的表示。
2. PQ编码：将查询向量拆分成多个子向量。例如，一个1024维的查询向量可以被拆分为4个256维的子向量。
3. 中心点距离计算：对于每个子向量，计算其与最近中心点的距离。假设这四个子向量到它们各自最近中心点的距离分别是50、118、29和47。
4. PQ码生成：将这些距离值组合起来，形成查询向量的PQ码，例如V=(50,118,29,47)。
5. 数据库存储：向量数据库需要保存所有中心点的信息以及所有高维向量的PQ码。
6. 相似度查询：进行查询时，将查询向量的PQ码与数据库中所有向量的PQ码进行比较。这涉及到将查询向量的每个子向量与数据库中相应子向量的中心点距离进行计算，并将结果相加。
7. 结果排序：根据计算得到的总距离，对数据库中的向量进行排序，找出与查询向量相似度最高的向量。 这个过程可以有效地减少计算量，并加快搜索速度，特别是在大规模的向量数据库中。
   

• 然后按照上边这种方式，和每一个子向量的 PQ code 进行计算，就可以算出距离最近的向量了，但是这种和中心点进行计算的算法会存在误差，如下图所示：

在进行向量计算时，误差的控制是一个关键因素。通常情况下，我们可以观察到两种情况：一种是误差较小，另一种是误差较大。在实际应用中，尽管存在一些较大的误差，但大多数误差通常是较小的。

使用缓存加速计算的策略

如果我们在原始查询向量与每个子向量的PQ码之间进行距离计算，这与近似KNN算法相比并没有显著优势，因为它们的空间复杂度都是O(n)*O(k)。那么，这种算法的真正意义何在呢？难道仅仅是为了通过压缩来减少存储空间吗？

子空间划分与缓存的利用

我们可以考虑一种策略：将所有向量划分为K个子空间，每个子空间包含n个点。在这种情况下，我们可以预先计算每个子空间中点到其中心点的距离，并将这些距离存储在一个二维矩阵中。这样，当查询向量需要与每个子向量进行距离比较时，我们可以直接从这个矩阵中获取所需的距离值，从而加速计算过程。

结构化内容

1. 误差分析：首先，我们分析误差的分布情况，理解误差对计算结果的影响。2. 算法意义：探讨在近似KNN算法中，采用PQ码进行距离计算的意义，以及它与空间复杂度的关系。3. 子空间划分：介绍如何将向量划分为多个子空间，并解释这样做的目的。4. 缓存机制：详细说明如何利用预先计算的距离矩阵来加速查询向量与子向量之间的距离计算。 通过上述步骤，我们不仅能够理解误差对算法性能的影响，还能探索如何通过缓存机制来优化计算过程，提高效率。
   
   在处理大规模向量数据集时，我们经常需要快速检索出与查询向量相近的K个向量，即K-Nearest Neighbor（KNN）问题。然而，由于KNN算法的计算成本较高，我们通常采用近似近邻（Approximate Nearest Neighbor，ANN）算法来解决这一问题。下面将介绍两种常用的ANN算法：近似KNN和PQ算法的结合使用，以及NSW算法的搜索策略。

近似KNN与PQ算法结合1. 近似KNN算法：首先，使用近似KNN算法将数据集划分为多个子空间。这一步骤可以大幅减少需要搜索的向量数量。2. 子空间定位：将查询向量定位到一个特定的子空间中，以缩小搜索范围。3. PQ算法应用：在定位到的子空间内，应用PQ算法进一步加速向量的近似搜索。

NSW算法搜索策略1. 随机选择：NSW算法在构建图的过程中，每次随机选择一个数据点加入到图中。2. 查找最近邻：对于新加入的点，算法会查找与其距离最近的m个点，并与这些点建立边。3. 图结构形成：通过上述步骤，最终形成一个高效的图结构，便于快速搜索近似近邻。

通过上述方法，我们可以在保持一定精度的同时，显著提高大规模向量数据集的搜索效率。

在搜索 NSW 图时，我们从预定义的入口点开始。这个入口点连接到附近的几个顶点。我们确定这些顶点中的哪一个最接近我们的查询向量并移动到那里。

如从A开始，A的临近点C离P的距离更近更新。然后C的临近点D距离P更近，然后D的临近点B和F没有更近，程序停止，即为D点。

HNSW 图构建算法解析

一、算法概述HNSW（Hierarchical Navigable Small World）是一种高效的近似最近邻搜索算法，适用于高维数据。

二、构建过程### 2.1 初始阶段- 图的构建从顶层开始。- 算法通过贪婪搜索遍历边，寻找与插入向量q最接近的邻居，此时的搜索精度参数ef设置为1。

2.2 局部最小值确定- 一旦找到局部最小值，算法将向下移动到下一层。- 这个过程与搜索期间的移动类似。

2.3 选择插入层- 重复上述过程，直到达到预设的插入层。

三、第二阶段构建### 3.1 增加搜索精度- 在第二阶段，ef值增加到设定的efConstruction参数，这将返回更多的最近邻居。

3.2 邻居链接候选- 这些邻居成为新插入元素q的链接候选，并作为进入下一层的入口点。

四、链接添加策略### 4.1 参数考虑- 经过多次迭代后，添加链接时还需考虑两个参数： - M_max：定义一个顶点可以拥有的最大链接数。 - M_max0：定义针对第0层中顶点的最大连接数。

4.2 链接限制- 这两个参数确保了图的层次结构和搜索效率。

五、总结HNSW算法通过分阶段构建图结构，并在不同阶段应用不同的搜索精度和链接策略，以实现高效的近似最近邻搜索。

HNSW 简介HNSW，即 Hierarchical Navigable Small World，是一种多层图结构，用于实现高效的相似性搜索。在这种结构中，数据库中的对象首先在最低层（第 0 层）中被捕捉和良好地连接。随着层级的提升，数据点的数量逐渐减少，但它们仍然与下层的数据点保持匹配。

搜索过程1. 最高层搜索：搜索查询首先在最高层进行，以快速找到接近的数据点。2. 逐层深入：从最高层找到的数据点开始，逐层向下搜索，直至找到最接近的邻居。3. 最低层匹配：在最深层，搜索将定位到与查询最接近的实际数据对象。

性能优势- 速度：HNSW 通过在高层快速定位数据点，显著提高了搜索速度。- 内存效率：由于只有最高层的数据点被缓存，而最低层的数据点仅在需要时才加载，HNSW 显著减少了内存的使用。

应用场景HNSW 适用于需要快速且内存高效相似性搜索的场景，例如大规模数据库的索引和检索。

结构特点- 多层结构：HNSW 通过多层结构优化了数据点的连接和搜索效率。- 数据点减少：随着层级的增加，数据点数量呈指数级减少，优化了搜索过程。

总结HNSW 是一种有效的相似性搜索方法，它结合了多层图的优势，提供了快速且内存高效的解决方案。