应用程序越来越多地利用混合模态数据，并且必须对向量数据（如图像、文本和视频的嵌入表示）以及结构化数据（如属性和关键词）进行联合搜索。针对这种混合搜索场景提出的方法，要么性能欠佳，要么仅支持极为有限的搜索谓词集，这使得它们在许多应用中难以实际使用。为了解决这些问题，本文提出了ACORN，一种实现高性能且无谓词依赖的混合搜索方法。ACORN基于分层可导航小世界（Hierarchical Navigable Small Worlds,HNSW）（一种最先进的基于图的近似最近邻索引），并且可以通过扩展现有的HNSW库来高效实现。ACORN引入了谓词子图遍历的概念，以模拟一种理论上理想但不切实际的混合搜索策略。ACORN的无谓词依赖构建算法旨在实现这种高效的搜索策略，同时支持各种谓词集和查询语义。实验结果表明，ACORN在所有数据集上都达到了最先进的性能。

1. 研究背景与动机

1.1 混合搜索场景的兴起

如今深度学习模型强大的表示能力令向量嵌入已成为广泛应用中的一种强大的基础数据类型，这些应用使用检索增强生成或基于相似性的搜索技术。因此，向量数据库和索引在许多生产场景中得到了越来越多的应用。这些系统为嵌入的非结构化数据（如图像、文本、视频或用户画像）提供了高效的近似最近邻（ANN）搜索接口。

然而，许多应用必须同时查询非结构化和结构化数据，这就需要将ANN搜索与谓词过滤结合起来。比如电商网站的用户可以在筛选价格的同时，搜索与参考图像相似的T恤。为了利用多样化的数据模态，应用程序需要能够有效支持混合搜索查询（即带有结构化谓词的相似性搜索）的数据管理系统。这样的系统一般需要具备以下两点：

1. 查询性能：即在工作负载特征（如选择性、属性相关性和规模）存在差异的情况下，仍能进行高效准确的搜索。

2. 丰富的查询语义：即支持各种可能事先未知的查询谓词（例如用户输入的关键词、范围搜索或正则表达式匹配）。

1.2 现有混合搜索系统的局限性

目前的三种常用的方法是预过滤、后过滤，以及针对低基数谓词集的专用数据结构。预过滤首先在数据集中找到所有满足查询谓词的记录，然后对过滤后的向量集进行暴力相似性搜索。这种方法扩展性较差，在处理大型数据集上的中高选择性谓词时效率较低。

相比之下，后过滤首先在ANN索引中进行搜索，然后去除不满足查询谓词的结果。由于与查询向量最接近的数据库向量可能不满足谓词，后过滤方法通常需要扩大搜索范围。这通常需要较高的成本，特别是对于选择性较低或与查询向量相关性较低的搜索谓词。

1.3 提出ACORN的动机

许多应用具有庞大或无界的谓词集，而且这些谓词集事先未知。一般来说，可能的谓词集的基数会随着每个属性的基数呈指数增长，而属性基数本身可能就很大。因此，本文提出了一种无谓词依赖的索引，它可以支持任意和无界的谓词集。作者提出了ACORN（ANN Constraint-Optimized Retrieval Network，近似最近邻约束优化检索网络），用于实现高性能且无谓词依赖的混合搜索，能够处理高基数和无界的谓词集。同时提出了两种索引：ACORN-γ，旨在实现高效搜索性能；ACORN-1，在资源受限的环境中，在近似ACORN-γ搜索性能的同时，进一步降低算法的索引构建时间（TTI）和空间占用。这两种方法都对HNSW索引进行了修改。HNSW是一种最先进的基于图的ANN搜索索引，并且很容易在现有的HNSW库中实现。

ACORN解决了预过滤和后过滤的性能限制，以及专用索引的语义限制。它提出了在搜索过程中遍历索引的谓词子图的概念；设计索引，使这些任意谓词子图近似于HNSW索引。

2. 背景知识

现有的近似最近邻（ANN）搜索方法大致可分为基于树的方法、基于哈希的方法、基于量化的方法和基于图的方法。HNSW是一种基于图的方法，在高维数据集上的实际表现是最好的之一，本文对其进行了改进以支持混合搜索。

基于图的ANN方法因其在各种ANN基准测试中的领先性能而受到广泛关注。这些方法通常使用贪婪路由策略进行搜索，从预定义的入口点开始遍历图索引。索引本身形成一个邻近图，其中每个数据集点由一个顶点表示，用边连接相邻的点。索引构建算法通常旨在近似Delaunay德洛内图的子图。虽然德洛内图保证了贪婪路由算法的收敛性，但对于任意度量空间，都无法高效构建。因此，基于图的方法侧重于更易于处理的德洛内子图近似，如相对邻域图（RNG）和最近邻图（NNG）。

2.1 分层可导航小世界HNSW

HNSW索引搜索示意图

如图所示，HNSW形成了一个具有有界度的分层多层图索引。HNSW构建算法通过迭代地将每个点插入图索引中，构建一个可导航的有界度图，由参数
指定。HNSW搜索算法从多层图最上层的预定义入口点开始遍历。然后，遍历过程采用从顶层向下的迭代搜索策略。在每一层，使用贪婪搜索选择一个节点，该节点成为进入下一层的入口点。到达最底层后，搜索算法不是贪婪地选择单个节点，而是贪婪地选择个最近的元素作为返回结果。算法中，搜索参数通过控制底层贪婪搜索期间存储的动态候选列表的大小，在搜索质量和效率之间进行权衡。

HNSW搜索算法

3. 问题定义和挑战

3.1 混合搜索定义

设是一个数据集，由n个实体组成，每个实体都有一个向量分量和一个与实体相关联的结构化属性元组。设表示数据集中的向量集，是任意两点之间的度量距离。设是数据集中的结构化属性集。作者将表示为数据集中满足给定谓词P的实体所对应的向量子集。我们将谓词P的选择性s定义为数据集中满足该谓词的实体比例，其中。

考虑混合搜索问题，文章中描述如下：

给定一个数据集D、目标数量K和查询，其中且是一个谓词，检索满足谓词的的K个最近邻。将特别关注相对于的近似最近邻搜索问题。这里，本文的目标是最大化搜索准确性和搜索效率，将通过召回率（recall@K）来衡量准确性，公式为，其中G是满足的的K个最近邻的真实集合，R是检索到的集合。

3.2 基线方法的搜索性能

文章分析两种主要基线方法（预过滤和后过滤）的搜索复杂度，将考虑不同的工作负载特征如何影响这些方法的搜索行为。HNSW的未过滤搜索复杂度为。

1. 预过滤：线性扫描，对每个满足搜索谓词的点计算距离。这导致混合搜索复杂度为。虽然预过滤总是能实现完美召回，但其搜索复杂度在数据集规模较大或选择性较高时扩展性较差，会随其中任何一个变量线性增长。

2. 后过滤：在X上执行ANN搜索，以找到与最接近的查询向量，然后扩大搜索范围以找到K个满足查询谓词p的向量。当中的向量与查询向量接近时，基于HNSW的后过滤搜索复杂度为。如果中的向量在X中均匀分布，那么后过滤的预期搜索复杂度为。然而，中的向量可能与查询向量相距较远，导致最坏情况下的搜索性能为。

这两种基线方法的搜索性能都对选择性、数据集大小和查询相关性的变化不具有鲁棒性。

3.2.1 形式化查询相关性

查询向量相关性

在基于后过滤的系统中，面临的一个关键挑战。当中的向量在X中分布不均匀，而是相对于X中的向量聚集在一起时，就会出现查询相关性。我们将这种现象称为谓词聚类。当谓词聚类发生时，查询向量可能与包含其搜索目标的谓词聚类接近或远离，从而引发查询相关性。

定义（查询相关性）：将给定数据集的查询到目标的距离，与假设不存在聚类的情况下的预期查询到目标的距离进行比较。形式上，将数据集D上的混合搜索工作负载Q的查询相关性定义为：

令是从X中均匀抽取的个向量的随机集合变量，为每个混合查询定义。作者定义为将查询向量x映射到给定向量集中最近邻距离的函数。就平均而言，查询向量在混合搜索目标的真实数据集中比在无聚类数据集中更接近其目标，那么该工作负载具有正查询相关性。如果情况相反，则该工作负载具有负查询相关性。

4. 基于HNSW数据结构的理论理想混合搜索性能

对于给定的混合搜索查询，作者将使用HNSW数据结构的理论理想搜索性能定义为：如果在构建过程中知道搜索谓词，则可实现的性能。在这种情况下，可以在上构建一个HNSW索引，将其称为该查询的权威分区索引。搜索此索引的复杂度为。值得注意的是，在谓词选择性、数据大小和查询相关性发生变化时，权威分区索引的搜索性能均优于预过滤和后过滤。

5. ACORN概览

ACORN的核心思想是在索引的谓词子图上进行搜索，即对于给定的搜索谓词p，由诱导的子图。通过修改了HNSW构建算法，使得任意谓词子图都能模拟HNSW权威分区索引，而无需显式构建。ACORN-γ通过构建一个更密集的HNSW版本来实现这一点，同时，ACORN-1通过在搜索期间而不是构建期间扩展邻居列表，来近似ACORN-γ的密集图结构，而无需实际构建它。

总体而言，ACORN提出了一个基于谓词子图遍历思想的、简单而通用的高性能混合搜索框架。本文提出的核心技术是在构建过程中进行无谓词依赖的邻居列表扩展和剪枝，以及在搜索过程中进行基于谓词的过滤。

5.1 ACORN-γ搜索算法

ACORN算法

上述算法概述了ACORN从顶层预定义入口点开始，在每一层使用的贪婪搜索算法。ACORN搜索算法与HNSW搜索算法的主要区别在于，在每个访问节点
处如何进行邻居查找（第9行）。HNSW只是简单地检查邻居列表，而ACORN则执行额外的步骤，以获取适合给定搜索谓词的邻居。

ACORN-γ使用两种邻居查找策略

具体来说，ACORN-γ使用两种邻居查找策略：一种是简单的过滤方法，如上图（a）所示；另一种是基于压缩的启发式方法，如上图（b）所示。

对于每个访问节点，基于过滤的邻居查找只是扫描邻居列表，以找到满足谓词的邻居子列表。如果包含超过M个节点，我们取前M个节点并将其作为v的邻居。

基于压缩的邻居查找则在进行过滤和截断之前，部分扩展邻居集，以包括v的两跳邻居的一个子集。这个过程分为两个阶段。第一阶段遍历的前个节点，与之前的策略一样进行简单过滤。第二阶段遍历邻居列表的其余部分，扩展搜索邻居以包括邻居的邻居，然后再次根据查询谓词进行过滤。

5.2 ACORN-γ构建算法

作者通过对HNSW索引算法进行两个核心修改来构建ACORN-γ索引：首先，扩展每个节点的邻居列表；然后，应用一种新颖的无谓词依赖剪枝方法来压缩索引。

HNSW和ACORN-γ索引构建的区别

1. 邻居列表扩展：HNSW为索引中的每个节点收集M个近似最近邻作为候选边，而ACORN为每个节点收集个近似最近邻作为候选边。在构建过程中，ACORN通过对其图索引进行无元数据搜索来找到这些候选节点。

具体来说，在每一层l的每个节点v处，ACORN的邻居查找策略只是访问邻居列表并返回前M个节点。注意，虽然每个节点最多包含个邻居，但在构建时假设每个节点有M个邻居就足以维持图索引的可导航性。因此，在遍历图时考虑截断的邻居列表，能够避免不必要的距离计算和索引构建时间TTI减慢。

对于，一个简单的选择是，其中是采用预过滤之前计划处理的最小谓词选择性。ACORN的索引构建时间和空间占用与成比例增加。

2. 压缩：ACORN-γ邻居扩展步骤的一个关键挑战是它会增加索引大小和TTI。增加的索引大小对于像HNSW这样的内存驻留图索引来说是一个重大问题。为了解决这个问题，本文引入了一种无谓词依赖的剪枝技术。剪枝过程的核心思想是在索引中精确保留每个节点的附近邻居，同时在搜索期间近似较远的邻居。

ACORN使用可调的压缩参数，其中。在构建过程中，ACORN通过自动保留最近的个候选边，并积极修剪其余候选边来选择每个节点的最终邻居列表。在搜索过程中，ACORN可以直接从邻居列表中恢复每个节点v的前个邻居，并通过在搜索期间查看两跳邻居来近似其余邻居。

如图的在应用于节点v的候选邻居列表的剪枝过程中，该算法遍历有序的候选边列表，并保留前个候选边。对于其余的候选边子列表，该算法在每个节点处应用以下剪枝过程。令H是v选择的两跳邻居的动态集合，初始化为空集。如果候选边c包含在H中，则将其修剪；否则，保留c并将其所有邻居添加到H中。剪枝过程在遍历完所有候选边后停止，或者当H的大小加上已选边的数量超过时停止。修剪后的有序邻居列表随后存储在ACORN索引中，H被丢弃。

5.3 ACORN-1

ACORN-1是一种替代方法，旨在近似ACORN-γ的搜索性能，同时进一步最小化索引大小和TTI。ACORN-1通过仅在搜索期间而不是构建期间执行邻居扩展步骤来实现这一目标。ACORN-1的构建过程对应于原始的HNSW索引构建，不进行剪枝。这种构建过程对应于ACORN-γ的构建算法，其中固定参数和。

ACORN-1在搜索期间与ACORN-γ的主要区别在于其邻居查找策略。具体来说，在贪婪搜索期间，在每个访问节点v处，ACORN-1在应用谓词过滤器并将结果邻居列表截断为大小M之前，使用完整的邻居列表扩展来考虑v的所有一跳和两跳邻居。如图（c）概述了这个过程。

ACORN三种邻居查找策略：基于过滤，基于压缩，ACORN-1

6. 讨论

6.1 索引大小

假设每条边的字节数恒定，

● ACORN-γ索引每个节点的平均内存消耗为：。

● HNSW索引每个节点的平均内存消耗为：。

总体而言，ACORN-γ使底层每个节点的内存消耗增加了，并使较高层每个节点的内存消耗增加了倍。

6.2 构建复杂度

对于固定参数：、和，

ACORN-γ的总体预期构建复杂度为：。

HNSW预期构建复杂度为：。

相比而言，ACORN-γ由于生成的扩展边列表，使索引构建时间TTI增加了倍。

6.3 搜索分析

6.3.1 索引和搜索属性

直观地说，对于给定的查询，当谓词子图形成分层结构、子图中的每个节点的度接近M、子图在其最大层索引处有一个在搜索期间可以高效找到的固定入口点，并且子图是连通的时，ACORN的谓词子图将模拟HNSW权威分区索引。由于ACORN的无谓词依赖剪枝，ACORN的谓词子图与HNSW之间存在一个主要区别：ACORN的每一层近似于一个KNN图，而HNSW的每一层近似于一个RNG图。

1. 层次结构：首先，观察到任意谓词子图形成了一个类似于在上构建的具有参数M的HNSW权威分区索引的可控层次结构。ACORN-γ的构建固定了M，因此也固定了层归一化常数。结果，ACORN-γ索引中的节点以与HNSW分区的层概率相等的速率进行采样。

2. 有界度：接下来，本文将描述度界，这是影响贪婪搜索效率和收敛性的一个重要因素。虽然HNSW在构建过程中将每个节点的度上限设为M，但ACORN-γ在搜索过程中强制实施这个上限。这确保了ACORN的搜索在每个访问节点处执行固定数量的距离计算。

如果谓词子图中的一个节点的度远低于M，这可能会对搜索收敛性产生不利影响，从而影响召回率。对于一个没有谓词聚类的数据集和查询谓词，对于中的任何节点v，有：

对于存在谓词聚类的数据集，这个式子同样是节点度的下限，在这种情况下，对于中的任意节点x

，有。因此，作者在无谓词聚类的最坏情况下继续对节点度进行下限分析。可以证明，对于任意谓词子图上的搜索路径：

同时作者还分析了子图遍历断开的概率，其界限为：

可以看到，这两个界限都随 γ 呈指数衰减。

3. 固定入口点：与HNSW类似，ACORN的搜索从构建期间选择的固定入口点开始。这个预定义的入口点提供了一种简单有效的策略，并且与谓词无关，对查询相关性的变化具有鲁棒性。由于ACORN在每一层以相等的概率对所有节点进行采样，因此满足给定谓词P的节点存在于某一层的概率与谓词的选择性成正比，其下限为。

4. 连通性：当HNSW权威分区连通时，我们可以期望ACORN的谓词子图也连通。有两种这样的情况是：没有谓词聚类，或者围绕单个区域聚类。在这两种情况下，每个节点的预期度至少为M，并且每一层近似于一个KNN图，当时，KNN图是连通的。实验中为了分析潜在的连通性问题，建议使用等效的M和参数，将ACORN的混合搜索性能与HNSW的ANN搜索性能进行基准测试。如果存在显著的精度差距，建议从其初始值开始逐步增加。

6.3.2 搜索复杂度

ACORN-γ的预期搜索复杂度为：

这近似于HNSW权威分区的预期搜索复杂度:。直观地说，ACORN-γ的搜索路径在进入并遍历谓词子图之前，会在较高层进行一些过滤，在此过程中，与HNSW搜索相比，ACORN为了对每个邻居列表执行谓词过滤步骤，会产生少量额外开销。

7. 实验

7.1 数据集

实验在两个具有低基数谓词集（LCPS）的数据集和两个具有高基数谓词集（HCPS）的数据集上进行实验。LCPS数据集能够对仅支持受限查询谓词集的先前工作进行基准测试。HCPS数据集包含更复杂、更现实的查询工作负载，使实验能够更严格地评估ACORN的搜索性能。

实验数据集概览

1. 具有低基数谓词集的数据集：使用SIFT1M和Paper数据集，这是用于评估近期专用索引的两个最大的公开可用数据集。对于这两个数据集：对于每个基础向量，分配一个1到12之间的随机整数来表示结构化属性；对于每个查询向量，相关的查询谓词对属性值域中随机选择的整数进行精确匹配。最终的查询谓词集的基数为12。

2 具有高基数谓词集的数据集：HCPS数据集的实验中使用TripClick和LAION数据集。

为了评估一系列微观基准测试，实验生成了四个查询工作负载。对于每个查询工作负载，从数据集中采样1000个向量作为查询向量。实验构建正则表达式查询工作负载，其谓词对图像字幕进行正则表达式匹配。对于每个查询谓词，随机选择2到10个正则表达式标记的字符串。此外，作者构建了三个与TripClick类似的查询工作负载，其谓词接受一个关键词列表，并过滤掉没有至少一个匹配关键词的实体。通过这种设置，实验能够轻松控制工作负载中的相关性，并生成无相关性（no-cor）、正相关性（pos-cor）和负相关性（neg-cor）的工作负载。

从每个工作负载中选取的一些示例查询和多模态检索结果。

7.2 实验基线

本实验中的基线有：ACORN-γ、ACORN-1、预过滤、HNSW后过滤、Filtered-DiskANN、NHQ、Milvus和Oracle Partition Index。

7.3 搜索性能结果

在LCPS和HCPS数据集上的结果，横坐标为queries per second（QPS）

7.3.1 LCPS数据集上的基准测试

上图左侧显示，ACORN-γ在SIFT1M和Paper数据集上实现了最先进的混合搜索性能，并且最接近理论上理想的权威分区策略。值得注意的是，即使与专门针对LCPS数据集的NHQ和 FilteredDiskANN相比，ACORN-γ在固定召回率值下，每秒查询数QPS始终高出2到10倍，同时保持通用性。此外，实验表明ACORN-1近似于ACORN-γ的搜索性能，在一系列召回率值上，其QPS比ACORN-γ低约1.5到5倍。

同等召回率下的距离计算次数

为了进一步研究ACORN-γ和ACORN-1的相对搜索效率，实验表格显示了两种方法在召回率@10等于0.8时所需的距离计算次数。权威分区方法是最有效的，在两个数据集上都需要最少的距离计算次数。ACORN-γ在距离计算次数方面次之。该表还显示ACORN-1比ACORN-γ效率低，这是由ACORN-1中使用的候选边近似方法邻居列表质量略有下降，从而影响搜索性能。最后，从表中可以看出，HNSW后过滤是所列方法中效率最低的。

实验中还发现，权威分区方法、ACORN-γ和ACORN-1的相对搜索效率（通过QPS与召回率衡量）不仅受距离计算的影响，还受向量维度的影响。同时，在Paper数据集上，ACORN-1和ACORN-γ的性能更接近权威分区方法，而在SIFT1M上，性能差距略有增大。

7.3.2 HCPS 数据集上的基准测试

上图右侧显示，在TripClick和LAION-1M数据集上，ACORN在召回率为0.9时，QPS比基线方法高出30-50倍，并且如前所述，ACORN-1 近似于ACORN-γ的搜索性能。在这两个数据集上，预过滤的成本过高，虽然能获得完美召回率，但牺牲了效率。而后过滤无法获得高召回率，这可能是由于存在不同的查询相关性和谓词选择性。

ACORN在Tripclick上在谓词选择性下的搜索性能

1. 变化的谓词选择性：实验使用Tripclick数据集评估ACORN在一系列现实谓词选择性下的搜索性能。结果表明，对于每个谓词选择性百分位数，ACORN-γ在召回率为0.9时，QPS比其他基线方法高出5到50倍。同样，ACORN-1的性能落后于ACORN-γ。对于低选择性谓词，预过滤方法最具竞争力；然而，对于高选择性谓词，预过滤的竞争力下降，而后过滤基线的吞吐量有所提高，尽管其召回率仍然较低。

查询相关性变化结果

2. 变化的查询相关性：实验控制查询相关性，并使用LAION-1M数据集在三种不同的查询工作负载上评估 ACORN。实验结果表明，ACORN-γ对查询相关性的变化具有鲁棒性，在每种情况下，在召回率为0.9时，其QPS比其他的基线方法高出28到100倍。在负相关性情况下，后过滤与ACORN方法之间的性能差距最大；在正相关性情况下，ACORN-γ再次优于基线方法，但后过滤变得更具竞争力，尽管其召回率仍无法达到0.9以上。预过滤方法的QPS相对保持不变，仅受每个查询工作负载中谓词选择性的微小变化影响。如前所述，ACORN-1的搜索性能接近ACORN-γ。

在LAION-25M数据集上无相关性查询工作负载的搜索性能

3. 扩展数据集大小：实验还展示了ACORN在LAION-25M数据集上无相关性查询工作负载的搜索性能，表明随着数据集大小的增加，ACORN与现有基线之间的性能差距只会进一步扩大，ACORN-1的搜索性能近似于ACORN-γ。

7.4 索引构建

7.4.1 TTI和空间占用

TTI结果（s）

索引大小结果（GB）

实验首先考虑ACORN-γ的构建开销。根据TTI结果显示，在所有数据集上，ACORN-γ的TTI最多比HNSW高11倍，最多比表现最佳的专用索引StitchedVamana高2.15倍。根据索引大小结果显示，ACORN-γ的索引大小最多比HNSW大1.3倍，至少比StitchedVamana小25%。同时，ACORN-1在列出的所有基线方法中实现了最低的TTI，其索引大小最多为HNSW索引大小的1.25倍，至少比StitchedVamana的索引大小小25%。虽然ACORN-γ通过在构建过程中利用邻居列表扩展实现了卓越的搜索性能，但ACORN-1通过在搜索过程中进行邻居列表扩展，在较低的TTI和空间占用下提供了接近的性能近似。这两种算法在搜索性能和构建开销之间存在权衡。

7.4.2 ACORN-γ剪枝

ACORN-γ每一层的平均出度

鉴于ACORN-γ的构建开销较高，实验研究其无谓词依赖压缩策略在降低索引构建成本同时保持搜索性能的效率。表格显示了ACORN-γ每个数据集每一层的平均出度，证实了对第0层进行压缩会导致邻居列表明显小于未压缩层，未压缩层的邻居列表可能大至。

不同剪枝策略效果比较

实验也评估在ACORN-γ邻居列表构建过程中应用的三种不同剪枝策略：ACORN的无谓词依赖剪枝策略；一种基于元数据感知的RNG剪枝方法，这是FilteredDiskANN算法所采用的；HNSW的无元数据剪枝方法。

试验结果表明，ACORN的剪枝可以通过积极修剪候选边显著降低TTI和空间占用，同时保持搜索性能。相比之下，对索引应用HNSW剪枝会导致混合搜索性能显著下降。同时，基于元数据感知的RNG剪枝在搜索性能上与ACORN-γ的剪枝相似，但在
值较小时，在TTI和空间占用方面不如ACORN的剪枝高效。

7.4.3 图质量

HNSW权威分区和ACORN-γ谓词子图比较结果

最后，实验研究ACORN-γ谓词子图的图质量，比较了HNSW权威分区和ACORN-γ谓词子图在TripClick数据集的真实混合搜索查询中，不同谓词选择性下的图连通性、图高度和出度。

首先，图a显示ACORN-γ的谓词子图连通性在经验上与HNSW权威分区相当或更好，这证明了ACORN-γ邻居扩展策略的有效性。图b检查了ACORN-γ谓词子图的可控层次结构模拟了HNSW权威分区的层次结构。最后，图c检查了对ACORN-γ索引执行搜索时过滤后得到的平均出度。总体而言，实验观察到ACORN-γ生成的谓词子图质量很高，在经验上模拟出了与搜索效率相关的HNSW的几个属性。

8. 相关工作

8.1 基于预过滤和后过滤的系统

许多混合搜索系统依赖于预过滤和后过滤。虽然一些系统开发了预处理方法以在搜索期间更快地进行过滤，但这些系统未能减少过多且昂贵的距离计算，而这正是性能的瓶颈。

● Weaviate：提前为结构化数据创建倒排索引，然后在查询时使用它在进行后过滤时创建符合条件的候选位图。

● Milvus：通过维护数据集中属性的分布来创建一个批准点列表，以便在进行预过滤或后过滤之前，将常用的查询过滤器映射到该列表。

● FAISS-IVF和LSH：在索引中存储元数据信息，使它们能够在后过滤期间快速过滤实体。

尽管这些方法中的每个都进行了优化的过滤步骤，但预过滤和后过滤的核心问题仍然存在，特别是对于低相关性或低选择性的谓词。

8.2 专用索引

最近的一些工作还开发了用于混合搜索的新颖图基算法，通常在处理受限的谓词集时提高了性能。

●  NHQ：将属性与向量一起编码，然后在搜索期间使用一种“融合距离”，该距离考虑了向量距离以及属性匹配。

●  Filtered-DiskANN：提出了FilteredVamana和StitchedVamana。这两种方法都将查询过滤器基数限制在约1000，并且仅支持等值谓词，以便索引构建步骤可以利用这些知识来适当地生成和修剪候选边列表。

●  HQI：通过假设20个查询谓词的有限基数来设计高效的分区方案，以优化批量查询处理。

●  Qdrant：提出对HNSW图进行致密化并执行过滤后的贪婪搜索。

9. 结论

作者提出ACORN，这是第一种能够在向量和结构化数据上进行高效混合搜索的方法，支持大量不同的查询谓词集。ACORN使用一种基于谓词子图遍历核心思想的简单而有效的搜索策略。本文提出了两种索引：ACORN-γ和ACORN-1，通过修改HNSW索引算法来实现这种搜索策略。实验结果表明，ACORN在先前的基准测试（涉及简单、低基数的查询谓词集）以及更复杂的基准测试（涉及新的谓词运算符和高基数谓词集）中，都实现了最先进的混合搜索性能；并且ACORN-1在资源受限的设置中，以比ACORN-γ低9到53倍的TTI来近似其搜索性能。

论文解读联系人：

刘思源

13691032906（微信同号）

liusiyuan@caict.ac.cn