神经嵌入相似性查询的高效处理：综述

22年4月佛罗里达大学的论文“A Survey on Efficient Processing of Similarity Queries over Neural Embeddings”。

相似性查询是基于某些相似性度量的一类查询，例如 top-k 查询（其中结果按其与查询目标的相似性进行排序）和相似性连接查询（其中两个数据集中的记录按彼此之间的相似性而不是特定Key进行连接）。与主要基于Value相等的传统数据库查询不同，相似性查询旨在根据某些相似性度量（例如欧几里得距离、余弦相似性等）找到与给定数据目标（object）“足够相似”这个目标（target）。相似性查询广泛应用于数据集成（例如实体解析和模式匹配）、信息检索、问答和数据科学的许多其他领域。

为了测量数据目标之间的相似性，传统方法通常针对低级或语法特征（例如图像上的基本视觉特征或文本的词袋特征），这使得它们无法计算目标之间的语义相似性（semantic similarity）。因此，为了从语义上测量数据相似性，应用了神经嵌入。嵌入技术的工作原理是将原始数据目标表示为向量（由于它们大多由神经网络模型生成，因此称为“嵌入”或“神经嵌入”），从而揭示原始数据的隐藏语义，基于此，嵌入在捕获数据相似性方面确实表现出色，使其成为相似性查询处理研究中最先进最广泛使用和研究的技术之一。但是，基于嵌入的相似性查询处理效率仍存在许多未解决的挑战，这些挑战没有像有效性那样得到充分研究。

本文首先概述“相似性查询”和“相似性查询处理”问题。然后，讨论在嵌入（或更一般地说，高维数据）之上设计索引和算子以实现高效相似性查询处理的方法。最后，研究在选定的相似性查询应用领域中使用和不使用嵌入的具体解决方案，包括实体解析和信息检索。通过比较解决方案，展示神经嵌入如何使这些应用受益。

相似性查询是基于数据的近似语义而不是精确语义的查询[184]。或者可以将其定义为涉及相似性算子的查询[166,184]，包括相似性选择（例如，k最近邻搜索）、相似性连接、相似性聚类等。简而言之，任何基于记录之间的相似性而不是精确数值匹配来寻找答案的查询都是相似性查询。

一般来说，嵌入是原始数据目标的多维向量表示，其中向量揭示原始数据的语义信息，并且可以通过计算相应向量上的某些相似度/距离度量来测量原始数据目标之间的语义相似度。

索引是数据库和搜索系统中最关键的组件之一，因为它可以快速访问检索目标。典型的索引包括 B 树、B+ 树、日志结构合并树 (LSM-tree) 等。不同的索引结构适用于不同的场景，例如，KD-tree 适用于低维空间数据搜索，但在高维空间中表现较弱。对于通常是高维向量的神经嵌入，适当的指标主要包括四类：基于hashing的[34、121、134、138、180、203、206]、基于积量化（product quantization）的[90、99、105、109、119、144、210、231]、基于图的[58、122、188]、基于分区/树的[61、63、91、94]，其中最先进的方法通常属于相关研究领域的前三类。

高维数据的相似性查询处理涉及的算子包括但不限于相似性搜索/选择、相似性连接、相似性聚类、排名/排序、聚合（例如，求和和最大值）等。

如图说明相似性查询处理的工作流程。粉色框代表数据和相似性查询的来源以及答案被发送到的客户端。蓝色框表示处理过程中的主要组件。与数据库系统中的查询类似，相似性查询经过查询解析器、查询规划生成器、查询优化器并最终物理执行，而数据在查询之前被索引，索引将用于算子、优化和执行。在某些情况下，如果查询很简单，则可以跳过查询解析和优化，例如，只需询问给定查询目标的 K-NN。因此，解析器和优化器框使用虚线绘制。

索引是快速访问数据的最关键工具之一，几十年来一直被研究。传统的基于相似性/距离的索引，如 KD 树，在低维数据上效果很好，但由于维数灾难的问题，其在高维数据上表现不佳。由于神经嵌入通常是高维向量（比如几百维），因此它们需要基于高维相似性的索引方法。而且因为大多数最先进的基于嵌入方法 [56, 93, 101, 117, 146, 148, 179] 依赖余弦相似性或欧几里得距离来准确测量嵌入相似性。

基于hashing的相似性索引 是通过对搜索空间中的所有数据目标进行哈希处理来构建的。为了回答查询，它会对查询进行哈希处理，然后在哈希查询所在的哈希桶中查找并验证候选目标。基于哈希的高维相似性索引方法主要有两类 [203, 206]：局部敏感哈希（LSH）和学习哈希。

矢量量化 (VQ) [79] 是一种减少高维NN搜索计算量的有力工具。它的工作原理是使用多对一映射将高维向量编码为码字，从而降低表示空间的基数。这些码字被称为质心。所有质心的集合构成了此类 VQ 的码本。然后在相似性搜索中，任何两个原始向量之间的距离可以通过相应码字之间的距离来近似。但是当 VQ 应用于大规模数据时，它仍然需要大量的内存占用，因为码本的大小随着每个码字的长度呈指数增长（即，k 位码字导致码本具有最多 2𝑘 个质心）。 积量化（PQ） [70，79，99] 就是来解决此问题。PQ 将每个原始向量划分为 M 个低维子向量，然后分别量化每个子向量，PQ 实际上将原始向量空间分解为 M 个子空间的笛卡尔积 [70]。并且每个子空间对应的码本比 VQ 所需的码本小得多。其方法分为两种：穷尽法和非穷尽法。

基于图的相似性索引 是这样一个图（有向或无向）：𝐺（𝑉，𝐸），其顶点𝑉是搜索空间中所有数据点的集合，边集𝐸由数据点之间的距离决定。具体而言，如果两个数据点足够接近，根据某种距离度量可以被认为是邻居，那么在𝐺中会有一条边连接它们相应的顶点，否则在𝐸中就不会存在这条边。根据索引中基图的类型，将索引分为四类：Delaunay 图、相对邻域图、K-NN图和最小生成树。其方法分为两类：图构建（侧重于有效构建基础图）和图遍历（研究现有图索引结构上的高性能搜索）。

基于树（或基于空间划分）的索引 是相似性搜索最常用的索引之一，例如 KD 树。经典的 KD 树在每一步将空间递归地划分为两个子空间。分区枢轴是沿其中一个坐标轴最大方差的中值。随机 KD 树是 KD 树的一种变型，它在方差最大的前几个维度中随机选择分割方向，而不是总是在方差最大的维度上进行切割。为了获得更好的搜索精度，索引通常包含多个随机 KD 树（也称为随机 KD 树森林）。森林中的搜索在每棵树中并行执行，并使用优先级队列来维护所有树的结果，这些结果按它们与相应决策边界的距离升序排列。这保证了所有树中最近的叶子将被首先探索。

如表总结了所有研究的索引方法。而接下的一个表给出了每个缩写的含义。