向量数据库是如何检索的？基于 Feder 的 HNSW 可视化实现

从向量检索说起

我们日常生活中常见的图片和声音都是非结构化数据，通过使用各种机器学习的模型，可以提取出不同的特征向量。每个非结构化的对象，都能够作为提取特征向量的集合，由一个高维向量进行表示。比如，苹果可以用 [圆球形，红色，水果，酸甜，...] 来表示。

与标量数据查询不同，在向量数据库中进行近似查询时，我们的目的并不是找到和目标完全一致的对象，而是找到和目标相似度更高的对象。同时，在比较两个向量相似度的过程中，我们所花费的成本相对于标量也要高得多，如果每次查询都需要遍历整个数据库的话，整体计算量将非常大，时间代价也将非常昂贵。

这个时候，通过使用一些向量检索算法，可以帮助我们解决上面的难题。例如，近似最近邻搜索算法(Approximate Nearest Neighbor Search, ANNS)。

ANNS 是什么

ANNS 又叫做近似最近邻算法，是一种加速向量相似性查询的方法。这种算法其实就是为给定的集合构建一种数学模型(或数据结构)，当输入一个检索对象时，可以在集合中快速找到与其最近的对象。

业界目前有许多不同“版本”的 ANNS 算法，比如 ivf_flat, hnsw, scann 等等，这些算法的本质是通过构建索引，减少数据查询过程中对数据库的遍历，来提高查询的效率，但代价是会降低向量相似性搜索的精度。

如何选择索引类型、设置索引参数来平衡精度损失和查询效率，是向量数据库构建的重要内容。

想要解决上面的问题，不免需要用户熟悉各类复杂的索引以及繁多的参数，这都需要耗费大量的时间来进行学习和掌握，并且在神经网络算法中存在大量的黑盒状况，在向量索引场景中想要观察和调试业务也同样面临着巨大的挑战：我们如何知道与某个数据相似的向量都是什么呢？

Feder - ANNS 算法的可视化神器

为了解决上面的难题，让生产环境中的向量数据具备一定的可观测性，我们推出了一款基于 ANNS 算法的可视化工具—— Feder，它可以将算法处理数据的过程可视化，并将清晰的结果快速可靠地呈现在用户面前。有了 Feder，神经网络算法场景下的向量检索将不再是黑盒！

使用 Feder 可以帮助我们更容易地理解不同的索引类型及参数：Feder 可以支持用户观察不同索引的数据组织结构，以及不同参数对索引结构的影响；Feder 也可以向用户展示单次搜索任务中完整的搜索过程，包括详细的数据访问记录。
我们已经支持了两种主流索引: hnsw (from hnswlib) 和 ivf_flat (from faiss)，我们正在对项目进行积极的开发，让 Feder 能支持更多索引的类型，如果你有具体的索引需求，或者对项目感兴趣，欢迎前往 Github（https://github.com/zilliztech/feder）参与项目的讨论。如果你觉得我们的项目还不错，请给我们的项目点赞和关注！

hnsw 可视化 - 基于 VOC 数据集的案例分析

我们使用机器学习领域中经典的图片数据集 VOC 2012（ 17,000+ 张照片）为例，通过 Towhee（https://github.com/towhee-io/towhee）可以将这些照片高效地转换为向量，然后通过 hnswlib 完成索引的构建，最后通过 Feder 实现结果的可视化。

我们实现了一个开箱即用的在线 demo，你可以在 colab 上快速体验 hnsw 的可视化结果。（https://colab.research.google.com/drive/12L_oJPR-yFDlORpPondsqGNTPVsSsUwi?usp=sharing）

洞悉 hnsw 索引的整体结构

接下来，我们为 VOC 数据集构建 hnsw 索引，如下图所示，一共有 5 层。为了方便演示，我们仅展示最上面 3 层的结构。

hnsw 索引具有多层结构，其中每层都是一个联通网络。在上面的图片中，我们可以观察到，上层的节点比较稀疏，但是节点间的跨度比较大，而层数越往下，节点越稠密。这个空间结构类似真实世界中的交通网络，从上往下，依次可以看作：航空网络、铁路网络，以及高速公路网络。

当我们利用 hnsw 索引进行向量搜索时，会优先使用上层的网络，就像乘坐飞机一样，它提供更快的速度（更少的中转），但是单靠上层网络并不能直接找到与输入对象相似的目标对象。这时，我们需要继续向下层网络进行数据查找，来获得更高的数据精度。同样地，我们在现实生活中也需要换乘其他交通工具，例如铁路、高速公路、普通公路等等。（这里有一个细节，hnsw 在构建时会选取最上层的一个节点作为固定入口，每次查询都将从该入口出发）

Feder 支持用户进行交互，用户可以选择任意一个数据节点进行观察，高亮的黄色轨迹表示从入口出发到最终抵达该节点的最短路径（最少的中转），白色路径代表了该节点能抵达的其他节点。通过交互查看该路径上更多细节，我们可以看到，随着层数的增加，连接对象的相似度会越来越高。

左上角的“数据概览面板”提供了一些参数信息:

参数 M : 每层网络中的每个节点可以抵达节点的数量取决于参数 M 。当前，M 的值为 8，那么从任意一个节点出发，能抵达的节点数目不会超过 8 个（在最底层 level-0 是 2M=16 个）。我们可以修改不同的参数，以观察在不同参数下的索引结构。随着 M 的增加，hnsw 的整体结构将会越倾向于“扁平”。
参数 ef : ef 对索引结构的影响并不如 M 那么明显，它实际影响的是索引构建时 link 的生成。具体可以参考论文[1]。

洞悉 hnsw 索引的搜索过程

当我们给定了搜索目标后，就可以在 Feder 中以动画的形式了解到完整的向量搜索过程。

上图展示了实际搜索任务中数据访问的过程，其中包括了参与向量相似性计算的对象。

首先，从（固定的）入口出发，先在第一层逐步访问所有能抵达的节点，然后跳转到距离目标最近的一个，每次跳转都在逐步靠近目标节点，当本层的节点不足以更加靠近目标时，将进入下一层不断搜索。

在最后一层的搜索过程中，其搜索路径是多线展开的，ef 参数将影响搜索路径的选择。

通过交互，我们也可以发现，虽然最开始搜索路径上的节点相关性都较低，但随着搜索的进行，搜索的精度迅速变高。从左侧的统计面板中，我们可以发现，总量超过 17,000 张的图片，实际被访问到的向量（即参与距离计算的向量）只有 143 个，约占总量的 1%，这大大加速了查询的效率，这也是 hnsw 的魔力所在。

用户可以调整参数，生成不同的索引文件，来观察不同索引结构下的搜索效率和结果对比。

关于 Feder

Feder 的诞生离不开强大的向量数据库软件 Milvus [2] 和先进的向量数据 ETL 框架 Towhee [3]，如果你对 Feder 感兴趣，欢迎访问 GitHub，查看文档，了解 Feder 的更多信息 (https://github.com/zilliztech/feder)

Feder 基于 JavaScript 构建，我们只需要准备好数据的索引文件，就可以实现“向量的可视化”。

除此之外，我们还提供了 Python 工具包：federpy，可以通过 IPython 生成可视化结果。