在当今人工智能领域，向量搜索是一种热门技术：通过模型创建嵌入向量并存储起来，然后根据用户查询找到最相关的存储向量，无论是相似的产品还是文本。目标是找到真正最近的向量，而无需进行全面的数据扫描。所有这些近似最近邻算法都在追求这个目标。
在Daxe，我们致力于构建结构化语义搜索——一个完整的AI搜索堆栈。我们的团队利用来自OpenAI、Google、Lyft、AWS、哈佛、伯克利和达登等机构的经验，开发创新技术，帮助开发者和组织充分利用数据潜力。我们热衷于AI主权，坚持本地数据所有权——我们在自家地下室的GPU集群上测试一切，并将其部署到大型企业解决方案中。
虽然Daxe和结构化语义搜索远不止于向量搜索，但我们确实拥有向量相关性信号这一工具箱。由于这个问题已经相当成熟，市面上有许多选择，今天，我们决定开源我们的向量索引库，并解释其工作原理以及它在开源AI社区中的位置。
为什么要做？
在Daxe，我们使用多种语言，后端通常使用Go和Rust。当我们构建自己的数据存储时，排除了使用外部向量数据库的可能，我们需要一个索引库。像FAISS、Annoy（或Arroyo）、USearch这样的优秀库能满足部分需求，但没有一个能完全满足所有要求。
最大的挑战在于规模：我们需要处理数十亿个向量，同时保持低的索引构建时间。这意味着内存解决方案不再适用，我们只想比较向量，其中一些可能需要存储在磁盘上，但不希望频繁进行寻道操作。这也意味着量化和压缩技术同样重要，以避免向量填满磁盘。当然，这有取舍：最先进的算法（如HNSW）召回率更高，但扩展性较差。
我们需要不同的解决方案。因此，我们为Go和Rust开发者实现了一个新的向量索引库，基于我们设计的新算法，我们称之为BBQvec，现在已经在GitHub上开源，采用Apache许可。
BBQvec算法
一个二维Voting Parable
想象一下，你是一个向量，住在一座城市的街区里，这座城市政治活动非常活跃。每周都有城市议会选举，选举结束后，城市会重新划分选区，随机重绘选区边界。
这挺烦人的。你和附近的邻居们都希望街道上有新的自行车道，并且想一起投票，但有时你们投票给同一组议员，有时则不然。城市的理念是，平均来说，你的街区会投票给相同的议员，得到应有的代表。假设你是房子A，B是你的邻居，C离你几个街区，而D在城市的另一边。你可能参与的选区编号可能会这样变化：
这意味着你的邻居们每周都会在相同的（或非常接近的）选区投票。你没搬家，周围的界线变了，但由于物理上的接近，你在选区中的频率更高。（第二周，你可能“意外”被划分到了另一个选区）
算法简介
Annoy算法无疑启发了BBQvec；它在空间中随机划分，并多次进行。然而，与通过分割平面构建B树森林不同，这里的随机性首先出现。
步骤
- 随机选择一组正交基来覆盖向量空间。
- 对每个向量及其数字ID，记录其最大分量的索引，这是它的“选区”，也是向量在每次变换基时指向的单位超立方体的面。
- 将这些集合作为位图存储。
- 对向量进行量化，并按ID保存在磁盘上。
- 查询时，对查询向量执行相同操作：找出最大分量的索引列表。
- 找出每个集合中最常出现的其他向量ID（即“在一起的时间总周数”）。
- 对查询向量进行量化，直接比较和排名匹配项。
参数设置
另一个需求是我们能够动态调整每个向量子查询对整体查询评估的代价。这也是BBQvec的一个优势。
创建索引时，参数较少：
- 向量维度：定义你工作的空间，通常由嵌入源或模型决定。
- 量化策略：该算法的一个优点是，它对量化方式完全不敏感。一旦向量在位图中标记，存储和比较可以使用任何量化技术，便于在这个主题上进行实验。这取决于你愿意牺牲多少磁盘空间来换取原始向量的准确性。
- 基准集数量：不需要太多——对于数十亿个向量，几十个基集就足够好，但更多的基集会更精确，但占用更多空间，检查速度也更慢（类似于Annoy的多个森林策略）。
其中，基集的数量需要调整，但在测试中，所需的基数量通常与你希望存储在索引中的最大向量数量成对数关系。
查询时，参数也很直观，允许我们控制所需的灵活性。
K：返回的最近邻数量（毕竟这是AKNN）
SearchK：最大考虑向量数：在足够多的“选区”位图相交后，如果候选者不多，我们可以停止并扫描所有，当达到这个最大值时，我们会强行完成最后一程。为了获得更准确但较慢的搜索，你可以调整这个数值，以进行更多或更少的潜在磁盘查找。
Spill：扩大搜索范围：我们不仅查看最大分量的集合，还可以合并前三个或四个分量（就像“在最近的N个选区中投票”）。
基集数量：虽然我们可以构建多个基集，但由于它们独立且随机，查询时可以使用更少的基集。默认情况下，应使用最大数量，但更少的基集可以加快查询速度。
性能基准
幸运的是，AKNN算法的基准测试已经做了很多工作。现在我们开源了，我们可以在https://ann-benchmarks.com上添加我们的数据，但这里先展示一些早期图表，让你了解性能。
我们知道BBQvec在速度最快、精度最高的指标——召回率与每秒查询次数（QPS）的闪亮顶线中并不是最快的，只是表现良好，处于中间水平。然而，最大的优势在于索引构建时间：快得多。这是一个被低估的超级能力，尤其是在大规模处理数十亿个向量时。
这些图表来自在EPYC 7402上运行的测试，该机器有24个核心和128GB内存。ANN-Benchmarks在AWS的r6i.16xlarge上运行，配备Xeon处理器，64个核心和512GB内存，可以说性能相当，甚至更好。此外，测试版本是Go包，而Rust库在本地单元测试中的速度大约快1.5到2倍，所以我们期待这些基准测试会更加激动人心。
前两张图来自nytimes-256-angular数据集，K=10，维度为256（这是这些基准中存储29万个向量的最大维度）。BBQvec-Go始终显示为鲜艳的红色。
我们还测量了glove-100-angular，这是ANN-Benchmarks主图上最大的向量数量，有120万个100维向量（K=10）。
结论
我们期待看到你如何使用BBQvec，也欢迎参加我们的未来活动和黑客马拉松，讨论我们如何在AI搜索和检索方面进行创新。