今天为大家分享一篇SIGMOD 2024年的向量检索论文：ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data
ACORN:嵌入向量和结构化数据上的高性能混合搜索
论文作者来自斯坦福大学、DBOS和UC Berkeley。
论文地址：https://dl.acm.org/doi/pdf/10.1145/3654923
代码地址：https://github.com/TAG-Research/ACORN论文概述
嵌入向量和结构化数据的混合查询是当前知识检索问题下的一个重要问题。具体来说，非结构化数据，比如文本、图像，通常通过神经网络嵌入成向量数据，同时这类数据也具有结构化的标签，比如文本的作者、发表日期、语言，更复杂的如图像的文本摘要。在查询时，用户往往希望在对向量进行语义相似性查询的同时加入一些标签限制，比如在一定日期内的最相似图片，某一指定作者发表的相关文章，这就涉及到了标量与向量的混合搜索。
在混合搜索问题中，查询的选择率是一个关键。如果选择率较低，比如只有几条数据可以符合查询指定的标签，那么先通过标签过滤，再进行相似度计算会比较高效（即pre-filtering，先过滤）；反之，如果选择率较高，则首先使用向量索引快速获得足量的最近邻，然后再用标量筛选则更为合理（即post-filtering，后过滤）。
现有向量数据库普遍采用二者之一，但在选择率发生变化时则性能会大幅退化。学术界提出的一些定制索引如Filtered-DiskANN，NHQ，HQANN，一般会限制查询类型为等值查询，且标签基数普遍较小。本文提出的ACORN方法，构建了更密的HNSW，也是定制化混合索引的一种，无需先/后过滤。ACORN不仅在查询性能上有提升，而且不限制查询类型和标签基数，等值、范围、正则表达式均可以查询，且对标量标签的基数没有限制。关键算法
ACORN对HNSW的结构进行微调，使得在多种选择率下均可以获得足够的图连通度，保证召回率。
对混合查询中的裁边规则的思考
HNSW中的RNG裁边规则对HNSW的高效图结构起到了重要作用，可以在保证连通度的同时，让图变得更加稀疏以提高查询效率。然而，在混合查询中，RNG裁边规则有可能破坏图的连通性。如下图，在RNG规则中，v到b的边可以被裁剪，因为一般认为a到b会有边，所以v到b可以通过a作桥梁。但是在混合查询中，如果a没有满足标量标签，v就无法到达b。
因此，在ACORN中，没有采用RNG裁边，而是以二阶邻居的方式对邻居进行压缩。ACORN构建算法
ACORN的整体构建流程与HNSW基本一致，主要区别在选边上。HNSW插入点时仅保留M个最近邻，ACORN保留个邻居。在裁剪时，ACORN不使用RNG规则，而是首先保留个邻居，对于剩下的邻居，如果它们是已保留邻居的邻居（二阶邻居），那么不保留，否则保留下来。通过这种方式，ACORN可以在查询时通过访问二阶邻居的方式，访问到个原本的邻居。参数和查询集的最小选择率有关，通常设为，以保证在任何查询中，都有足量的邻居可以访问。
ACORN查询算法
在查询时，访问每个点时都会访问（部分）二跳邻居，并从中选择前M个进入候选队列，以此保证连通性。
ACORN-1
由于M倍的HNSW邻居压缩是较为耗时的，ACORN的另一种方式是采用HNSW的方案进行
构建，但不做任何裁边。在查询时访问所有的二跳邻居作为候选。
这种方式不保证的邻居压缩，但是构建足够快，也不占用额外的空间，实现也很简单。精彩段落
<<< 左右滑动见更多 >>>
总结与思考
ACORN通过简单的邻居压缩，给出了任意谓词条件下的混合检索方案。以十至数十倍的构建时间为代价，获得了任意谓词条件下的查询性能提升，实用性很强。其中，对于裁边策略的设计和考虑是一个突出的创新点，但在技术方案的设计上仍然有较大提升空间，比如高效的邻居压缩算法等。延伸阅读
[1] WWW'24：Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters
(https://dl.acm.org/doi/pdf/10.1145/3543507.3583552)
[2] NeurIPS'23: NHQ Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints
(https://arxiv.org/pdf/2203.13601)编者简介
王泽宇
复旦大学与巴黎西岱大学联合培养博士生，研究领域为高维数据（向量、序列等）管理和分析。以第一作者在SIGMOD,VLDB,VLDBJ,TKDE等数据库领域会议/期刊发表多篇论文，并担任审稿人。
个人主页：https://zeyuwang.top/
谷歌学术：https://scholar.google.com.hk/citations?hl=zh-CN&user=XXGhABIAAAAJ
技术博客：https://www.jianshu.com/u/d015902c6d09
