输入关键词开始搜索

高维相似性查询基数估计 - PVLDB 2020

✏️ 更新于 2026年04月29日

高维相似性查询基数估计：基于自适应桶探测的方法

Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing

作者：Zhonghan Chen, Qintian Guo, Ruiyuan Zhang, Xiaofang Zhou（香港科技大学 & 香港生成式 AI 研究中心）

arXiv：2604.04603

发表：PVLDB 2020

代码仓库：https://github.com/OscarC9912/simQ_hd_card_estimator

摘要

本研究致力于解决高维空间相似性搜索中的基数估计问题。我们的目标是设计一个轻量级、易于构建且能够提供精确估计并满足在线效率要求的框架。我们利用局部敏感哈希（LSH）对向量空间进行划分，同时保持距离邻近性。在此基础上，我们借鉴经典多探针 LSH 的思想，自适应地探索相邻桶，以应对不同量级的距离阈值。为提升在线效率，我们采用渐进采样来减少距离计算的次数，并利用乘积量化中的非对称距离计算来加速高维空间中的距离计算。除了处理静态数据集外，我们的框架还包含更新算法，能够高效支持大规模动态数据更新场景。实验表明，我们的方法能够准确估计相似性查询的基数，同时获得令人满意的效率。

PVLDB 引用格式：Zhonghan Chen, Qintian Guo, Ruiyuan Zhang, and Xiaofang Zhou. Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing. PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX

PVLDB artifact 可用性：源代码、数据和/或其他 artifact 已发布于 https://github.com/OscarC9912/simQ_hd_card_estimator。

1 引言

在关系数据库系统[9]中，基数估计[6, 8, 10, 11, 16, 32, 44, 45]是查询优化[3, 13]的重要组成部分，已被研究数十年，它对查询输出行数提供快速估计，以便选择延迟最小的查询执行计划。近年来，随着向量数据库[4, 15, 19, 20, 25, 27–29, 40, 41, 43]和语义算子[2, 26]的普及，高维空间相似性查询的基数估计（CE4HD）[17, 18, 23, 30, 31, 33, 38, 39, 42]在数据库研究中受到广泛关注。其目标是：给定一个范围查询 ((x \in R_d, \tau \in R))，高效估计与查询点 (q \in R_d) 距离在阈值 (\tau \in R) 内的点的数量 (x)。在应用层面，相似性查询的基数估计器可用于优化与大型语言模型[5, 7, 12, 24, 36]交互的语义算子的执行计划，使我们能够在不实际执行的情况下高效估计与 LLM 的交互次数。

近期关于 CE4HD 的研究[18, 33, 38, 39]主要利用深度神经网络（DNN）来预测给定相似性查询的基数。从技术上讲，这些方法从查询向量、距离阈值和各种数据集属性中生成特征表示，然后用该表示训练一个学习模型，进而估计向量相似性查询的基数。然而，学习方法在实践中存在几个关键缺陷。首先，基于 DNN 的预测器性能严重依赖于训练数据的质量，如果训练数据没有经过适当调整，性能会大幅下降。其次，基于 DNN 的估计器需要大量时间的离线构建。例如，SimCard[33]将数据集划分为较小的簇（例如 100-200 个簇），其中训练标签是针对每个簇计算的，并为每个簇训练一个估计模型，以便推导当前局部区域的估计。即使使用高性能 GPU，该过程仍然耗时且需要大量计算资源。第三，基于 DNN 的估计器缺乏可解释性，且表现出不稳定性，在不同数据集上存在显著的性能差异。

受上述深度神经网络或学习框架缺陷的启发，我们的目标是设计一种轻量级解决方案，在静态和动态场景中均表现良好，并具有理论保证以支持其鲁棒性和有效性。总的来说，我们的主要设计指导原则是：估计器应该是轻量级的且需要很少的计算资源，使框架在离线构建、在线估计以及大规模动态数据更新方面都高效。为了实现这些目标，我们的框架建立在局部敏感哈希（LSH）[1]之上——这是一种用于近似最近邻（ANN）搜索的轻量级向量索引，并针对乘积量化和渐进采样进行了额外优化。在 ANN 搜索中，多探针 LSH[21]声称：给定一个被哈希到特定桶的查询，该桶包含其最近邻，则相邻的桶也很可能包含该查询的最近邻——这是 LSH 中硬边界问题的结果。在高维空间相似性查询的基数估计中，我们观察到类似趋势，如图 1 所示。图 1 中展示的总体直觉和动机是：随着相邻桶变得越来越远，邻居包含满足距离阈值内的点的可能性降低。此直觉将在第 4.3 节中形式化并详细讨论。受此观察的启发，我们提出了一种基于邻居的自适应桶探测策略，用于高效的相似性查询基数估计。

从技术上讲，给定查询 (Q = (x \in Rd, \tau \in R))，我们首先使用 LSH 函数找到查询的中心哈希桶 (B{central})，然后自适应地探测 (Nk)，即 (B{central}) 的第 (k) 步邻居，其中 (Nk) 由所有哈希码在汉明空间中距离为 (k) 的哈希桶组成。此外，(k) 的最大值由 LSH 索引中哈希函数的数目决定。在高维空间高维相似性查询的基数估计中，距离计算是效率的瓶颈。我们从两个方面进一步缓解这一瓶颈：1）采用渐进采样减少距离计算次数；2）利用乘积量化中的非对称距离计算提高距离计算效率。基数估计的一个主要特点是查询关联的距离阈值具有广泛不同的量级：有些阈值可能只返回少量结果，而有些可能返回数千个符合条件的点。在使用 LSH 索引的桶探测方案中，距离阈值的大小决定了是否应该探测远处的邻居，或者仅在 (B{central}) 内估计是否足够。然而，挑战在于 (\tau) 在查询到达之前是未知的，这意味着我们需要在线动态高效地理解 (\tau) 的大小。为应对这一挑战，我们设计了一种基于选择性的早停策略，使算法能够适应不同量级的距离阈值，早停条件有理论保证。

本文的主要贡献如下：

  • 设计：我们提出了一个基于局部敏感哈希（E2LSH）的框架，用于在欧几里得空间中回答高维基数估计问题，并针对具体问题进行了优化。
  • 自适应探测：我们设计了一种高效的基于邻居的自适应桶探测策略，根据不同量级距离阈值下的选择性早停条件，动态探测哈希桶并调整要探索的桶数量。
  • 优化：我们集成了针对具体问题的两个方面的优化。我们开发了自适应渐进采样策略来减少所需的距离计算次数，并应用乘积量化中的非对称距离计算（PQ）来提高距离计算效率。
  • 数据更新：我们进一步利用框架的优势支持大规模数据更新，提供了更新框架各组件的详细说明和算法以及实验评估。

本文结构如下。第 2 节形式化定义问题并介绍框架的必要预备知识。第 3 节回顾相似性搜索基数估计的最新进展。第 4 节展示框架的核心思想以及所提算法各组件的定制伪代码。第 5 节将框架扩展到处理动态数据更新。第 6 节提供算法的广泛实验评估。最后，第 7 节总结论文并展望三个有前景的未来研究方向。

2 预备知识

2.1 问题定义

向量相似性搜索是机器学习和数据分析应用中的一项基本操作，广泛应用于信息检索、推荐系统和计算机视觉。

定义 1（相似性搜索）。给定向量数据集 (D \in R_{N \times d})、范围查询 ((q, \tau))（其中 (q \in R_d) 且 (\tau \in R)）以及距离函数 (dist)，向量相似性搜索返回所有满足 (dist(q, x) \leq \tau) 的 (x \in D)，即 ({x \mid dist(q, x) \leq \tau, x \in D})。此 formulation 涵盖了各种距离度量（如欧几里得距离、余弦距离、曼哈顿距离）下广泛的相似性搜索问题。它通常被称为几何空间或度量空间索引中的范围查询。

定义 2（相似性搜索的基数估计）。给定向量数据集 (D \in R_{N \times d})、范围查询 ((q, \tau))（其中 (q \in R_d) 且 (\tau \in R)）以及距离函数 (dist(\cdot, \cdot))，相似性搜索的基数估计返回 (D) 中与 (q) 的距离不大于 (\tau) 的数据点数量，即 (|{x \mid dist(q, x) \leq \tau, x \in D}|)。

图 1：工作动机说明。(x) 轴是中心桶 (B{central}) 与其 (k) 步邻居 (N_k) 之间的距离，其中 (k \in [0, 14])，(k) 为汉明距离；(y) 轴是 (N_k) 中的选择性（selectivity）。我们使用 5 个数据集，每个包含 10 个查询进行演示。随着 (N_k) 距 (B{central}) 越来越远，邻居的选择性降低，这意味着在基数估计的相似性查询上下文中，较近的邻居更可能包含满足条件的点。

在相似性搜索基数估计的研究中，之前的工作关注一种[23, 30, 42]或多种[18, 33, 38, 39]距离函数，如汉明距离、角度距离、编辑距离、Jaccard 距离以及欧几里得距离。在本文中，我们关注欧几里得空间中的估计。

定义 3（欧几里得距离）。两个向量 (x, y \in R_d) 之间的欧几里得距离（即 (L_2) 距离）计算如下：

2.2 LSH 和乘积量化

局部敏感哈希

局部敏感哈希（LSH）是一种著名的向量索引，广泛用于近似最近邻搜索。LSH 的核心性质是：距离近的点比距离远的点有更大的碰撞概率。形式化定义为：

定义 4[34]。给定距离 (r \geq 0) 和近似比 (c > 1)，如果对于所有 (o_1, o_2 \in D)： (1) 若 (|o_1, o_2| \leq r)，则 (P_r[h(o_1) = h(o_2)] \geq p_1)， (2) 若 (|o_1, o_2| > c \cdot r)，则 (P_r[h(o_1) = h(o_2)] \leq p_2)，

则 LSH 函数族 (H = {h: R_d \rightarrow R}) 是 ((r, cr, p_1, p_2))-敏感的。

不同的距离函数（如 (L_p)、Jaccard 距离）使用不同的 LSH 函数来表示距离邻近关系。在本文中，我们关注欧几里得空间。欧几里得空间中典型的 LSH 族 E2LSH 定义如下：

其中 (o) 是 (D) 中数据点的向量表示，(a \in R_d) 是从 2-稳定分布（标准正态分布）中独立采样的 (d) 维向量，(W) 是预定义的整数，(b \in R) 是从 ([0, W]) 均匀采样的值。

基本 LSH 索引

本节我们将介绍近似最近邻搜索中局部敏感哈希的基本索引构建过程。首先，我们有一个局部敏感哈希函数族 (H = {h_1, h_2, …, h_N})，然后从 (H) 中采样 (k) 个函数，形成复合哈希函数 (g)，向量 (v) 的哈希值计算为：

此过程构建一个哈希表，向量根据距离邻近性被分配唯一的哈希码。通常，在欧几里得空间的 ANNS 上下文中，一个 LSH 索引包含 (L) 个哈希表，每个使用 (K) 个哈希函数，形成 ((K-L)) LSH 方案。

在理解局部敏感哈希索引的基本原理之后，现在让我们定义两个扩展概念，它们对理解框架核心至关重要。

定义 5（中心桶 (B_{central})）。在哈希表中，给定一个 LSH 函数族 ({h1, h_2, …, h_N})，数据点 (x \in R_d) 的中心桶 (B{central}) 定义为查询向量 (x \in Rd) 直接哈希到的桶。(B{central}) 的哈希码为：

定义 6（汉明距离）。两个向量 (x, y \in R_d) 之间的汉明距离计算为对应位置上不同标记的数量，形式化定义为：

定义 7（(B_{central}) 的 (k) 步邻居）。给定中心桶 (B{central})，其 (k) 步邻居是一组哈希桶，记作 (N_k = {N{k1}, N{k2}, …, N{ki}})，其中每个 (N{ki}) 的哈希码满足 (dist{hamming}(B{central}, N{ki}) == k)。

乘积量化

乘积量化[14]是用于高维空间近似最近邻搜索的一种流行索引，其核心思想是将全长度向量压缩为紧凑形式以节省内存。下面我们简要演示乘积量化的过程并解释将在本文中使用的部分。从技术上讲，向量 (x \in R_d) 首先被分割为 (M) 个子向量 (x = (x_1, x_2, …, x_M))，其中每个子向量维度为 (d_M) 且需满足 (M) 整除 (d)；然后数据集中所有向量被分割到 (M) 个子空间，每个子空间由所有对应索引的子向量组成。对于每个 (M) 子空间，PQ 执行聚类算法（如 KMeans）形成 (K) 个子空间质心，其中每个（子）向量被分配到最近的质心。在获得质心和每个子空间的点分配后，每个向量可以表示为长度为 (M) 的码书向量，如 (x = (3, 2, …, 8))，其中每个 (M) 值表示该子空间最近质心的标识符。反之，向量也可以表示为每个 (M) 子空间中一系列质心的拼接。

在 PQ 中，由于每个向量被压缩并用码书表示，不同向量之间的距离计算可以更高效。总的来说，乘积量化中有两种距离计算方案，称为对称距离计算（SDC）和非对称距离计算（ADC）。具体来说，SDC 基于量化后的向量计算两个向量之间的距离，数学上表示为：

其优点是在每个子空间中，任意两个码书向量之间的距离可以预计算，解决了查询未知的难题。尽管计算方便高效，但 SDC 在距离近似方面精度较低，很少用于需要高精度的任务。相比之下，ADC 通过不对查询向量进行量化来改进 SDC 的缺点，这意味着查询向量保持完整精度。数学上，(ADC) 计算为：

代价是我们无法为所有查询预计算通用距离表，因为查询是未知的，这会略微影响效率。然而，我们仍然可以计算查询每个子向量与每个子空间码书向量之间的距离，以便后续距离计算可以参考距离表。考虑到基数估计和近似最近邻搜索的精度要求，(ADC) 将被用于本文并将在优化部分进一步讨论。

3 现有解决方案

基数估计问题是数据库中一个经典问题，已有数十年历史，在关系数据库[6, 8, 10, 11, 16, 32, 44, 45]中提出了大量解决方案。在向量数据库中，基数估计问题是估计相似性搜索中合格点的数量。我们将回顾与本研究密切相关的几项主要工作。

采样方法

解决相似性搜索基数问题最朴素的方法是均匀采样，其常规做法是均匀采样数据集的 1% 或 10% 来推导整个数据集的估计值。该方法在大多数近期工作中被用作对比基准[18, 33, 42]。虽然基于采样的方法提供了一种直接的基数估计手段，但存在两个主要局限。首先，得到的估计值通常粗糙且缺乏准确性。其次，其效率较差：要达到与其他方法相当的准确性，基于采样的技术需要评估更多数量的点，导致显著效率下降。

超平面 LSH 方法[42]

该方法提出了一种使用局部敏感哈希和重要性采样的密度估计器，侧重于角度空间的估计。它首先用超平面 LSH 对数据集进行划分，然后根据不同桶的汉明距离从有潜力的桶中均匀采样。上述过程形式化为一个随机变量：

其中 (C_k q(I)) 是距离为 (I) 的桶中的点数，(K) 表示哈希表的数量。最重要的是，归一化因子 (p(x)) 表示某个点 (x) 在随机选择的哈希函数下落在距离 (q) 汉明距离为 (I) 的桶中的碰撞概率。最后，该随机变量被采样 (S) 次得到 (Z_1, Z_2, …, Z_S)，估计值取平均值。

SimCard[33]

SimCard 是一种用于高维空间的基于深度神经网络的估计器，采用全局-局部结构进行基数估计。具体而言，它应用 K-Means 对数据集进行划分，并使用 PCA 进行降维。对于每个簇，训练一个局部估计模型来预测该划分内的查询基数。然而，跨大量局部模型（如 100 个）评估查询在计算上非常昂贵。为此，引入了全局模型来识别用于基数估计最有前景的局部区域。模型以一组特征作为输入，包括查询向量、距离阈值和数据集的一些属性。该框架的全局-局部架构是新颖的；但它也继承了学习方法的一些常见缺陷。特别是，估计器的性能高度依赖于训练数据的数量和质量，不充分或低质量的训练数据会显著降低准确性。此外，实际上该框架包含数百个充当局部估计器的神经网络，这使得支持大规模数据集更新变得不切实际且效率低下。

SRCE / MRCE[18]

SRCE 和 MRCE 是高维空间基数估计的最新进展。SRCE 是一个利用相似性查询基本属性的简单估计器，而 MRCE 则结合机器学习技术来提高预测精度。两种方法都利用现有数据集的知识（称为参考对象），其假设是给定查询点的距离函数可能与数据集中某些已有点的距离函数相似。SRCE 使用单个参考对象估计基数，在平衡池大小和多样性方面生成参考对象池。在线估计期间，SRCE 识别距离函数与查询最匹配的参考点。在线计算距离函数耗时较长；为解决此问题，SRCE 使用向量索引在离线阶段预计算距离函数。尽管有效改善了效率，但预计算的需求使 SRCE 本质上依赖于查询，这是该算法的一个显著局限。MRCE 使用多个参考对象来估计基数，旨在减少 SRCE 对向量索引预计算距离函数的依赖。有了多个参考，MRCE 训练一个深度神经网络来评估每个参考的贡献，这些贡献的加权和产生最终基数估计。在网络架构方面，模型的输入包括数据点 (p_i)、参考对象 (r_i)、(p_i) 与 (r_i) 之间的距离以及距离阈值。在第一训练阶段，训练一个编码器-解码器模型来将 (p_i) 和 (r_i) 特征化，然后将生成的嵌入与剩余距离特征拼接，以计算每个参考对象的最终权重，最后组合这些权重产生基数估计。MRCE 减少了对向量索引的依赖；然而，获取足够多样的训练数据以获得令人满意的估计性能是耗时的。此外，虽然 SRCE 和 MRCE 在利用现有数据集知识方面是新颖的，但在实践中必须预计算大量值以确保效率和准确性。

4 我们的框架

4.1 概述

核心思想是使用局部敏感哈希（LSH）对数据集进行划分，这使得能够高效剪枝无前景的点，同时快速识别与给定查询接近的候选点（第 4.2 节）。除了 LSH 索引外，我们引入了基于邻居的探测策略（第 4.3 节）来根据距离阈值的量级自适应调整探索的点数（第 4.4 节），从而提高估计效率。此外，我们引入两个额外优化。首先，我们使用渐进采样来减少所需距离计算的次数，同时提供强概率准确性保证（第 4.5 节）。其次，我们利用乘积量化[14]中的非对称距离来进一步加速高维空间中的距离计算（第 4.6 节）。邻居探测策略与渐进采样的伪代码如算法 1 所示，其中 (f{neighbor})（第 12 行）：算法 2 和 (f{central})（第 7 行）：算法 3。此外，除了静态数据集外，我们的框架还支持数据更新，框架的每个组件都可以轻松更新，即使是大规模新数据。我们将在第 5 节提供更新框架的算法。

4.2 数据集划分

数据集划分或分割是高维向量基数估计中常见的预处理策略。其必要性可总结如下： (1) 现代向量数据集通常包含数百万个点，直接对整个空间进行基数估计既困难又容易产生重大误差[33]。因此，将数据集划分为较小的子集有利于提高估计准确性和效率。 (2) 在基数估计中，与查询距离足够远的点不能作为可行的候选，探索它们是不必要的。因此，对数据集进行划分有利于聚焦最有前景的候选点，从而通过剪枝无前景的点来提高效率。

我们的工作利用局部敏感哈希（LSH）对数据集进行划分。由于工作关注欧几里得空间，LSH 函数自然选为 E2LSH[1]。此外，为支持角度空间，框架可以轻松采用超平面 LSH，这也是角度空间类似工作[42]的选择。

4.3 基于邻居的探测策略

设计目标

为解决高维空间相似性查询的基数估计问题，我们旨在开发一种距离阈值感知的桶探测策略，该策略利用探索过的哈希桶的信息（如选择性）来自适应调整要探索的桶数量。在效率方面，我们的目标是使探测策略能够提供准确估计，同时仅探测数据集的很小比例以最小化所需距离计算的次数——距离计算被视为在线估计中的昂贵部分。为实现这一目标，我们受到近似最近邻搜索（ANNS）中多探针 LSH[21]的启发——它声称：给定哈希表中的一个中心桶 (B_{central})，距离仅几跳的相邻桶（在汉明空间中按哈希码距离测量）也很可能包含查询的邻居。在本文中，我们进一步探索并利用这一特性来解决估计问题，并将为框架各组件的设计提供详细推理和论证。

挑战：大量哈希桶

在局部敏感哈希（LSH）中，为在空间划分中获得良好性能同时捕获数百万点之间的距离邻近性，使用多个 LSH 函数来更好地捕获距离分布是常见做法[34, 35]。然而，多个 LSH 函数的使用导致了哈希表中大量的哈希桶。

例 4.1。给定一个哈希表，我们使用 10 个哈希函数，每个函数产生约 4 个不同值，理论上在哈希表中创建了约 (4^{10} = 1,048,576) 个不同的哈希桶。此外，如果使用 14 个哈希函数，将有约 (4^{14} = 268, 435, 456) 个桶。因此，以桶为单位探测邻居效率极低，原因如下：首先，以单个桶探测效率不高，邻居查找/索引时间会在在线估计期间产生较大延迟，并且不可能估计有意义数量的待探索桶；其次，根据我们的初步研究，每个桶中的点数可能高度不平衡，这意味着许多桶可能包含非常少的点（如 3 个或 10 个），从而降低了数据集的局部性信息。

我们的方法

考虑到直接探测大量哈希桶的缺点，我们提出了一个 (k) 步基于邻居的探测策略，其基本概念来自多探针局部敏感哈希。首先，让我们重新澄清哈希桶 (B{central}) 的 (k) 步邻居 (N_k) 的概念——它是一组哈希码在汉明空间中距 (B{central}) 距离为 (k) 的哈希桶。现在，我们的一般探测框架是：给定查询向量 (q)，我们首先估计其中心哈希桶 (B{central})（第 7 行），然后探索那些相邻桶 (N_1, N_2, .., N{K’})（第 9–16 行），满足以下任一条件时终止：

  • 已探索的点数达到最大值（第 10–11 行）
  • 全局探测终止标志被触发（第 14–15 行），其中 (K’ \leq K)，(K) 的最大值是哈希函数的个数

算法 1：基于邻居的探测

输入：   查询：(x ∈ R_d, τ ∈ R), LSH 索引：I ; 快速邻居查找表 P, 估计函数：f;
输出：   估计基数 |A|
|A| ← 0;
nVisited ← 0; (区别于实际计算)
PTF ← none (全局探测终止标志);
hashCode ← I.computeHashCode(x);
|A| += f_central(x, τ, I, hashCode);
nHashFuncs ← I.n_lsh_funcs;
for nDegree ∈ range(1, nHashFuncs) do
    if nVisited ≥ maxVis then
        break;
    nDeg_card, PTF = f_neighbor(nDegree, hashCode, x, τ, P);
    |A| += nDeg_card;
    if PTF then
        break;
    update nVisited;
return |A|;

例 4.2。给定查询向量 (q \in R_d)，容易计算中心桶 (B = [0, 2, 1, 3]) 的哈希码，我们使用一个包含四个哈希函数的哈希表。在我们的哈希表中，有一组不同的哈希桶：

  • N1: [1, 2, 1, 3], [0, 2, 1, 4]
  • N2: [2, 3, 1, 3], [0, 1, 2, 3], [1, 2, 1, 4]
  • N3: [0, 3, 2, 4], [1, 2, 2, 2], [1, 1, 0, 3]
  • N4: [1, 1, 2, 2]

每个哈希桶包含共享哈希码的点，我们按这些哈希码距中心桶哈希码的距离排序。在我们的探测策略中，同一 (N_k) 中的点被作为一个整体分组。然后，我们的策略是从 (N_k) 开始推导估计值，逐增 (k) 直到满足某个停止条件。

4.4 自适应桶探测

挑战：阈值的自适应性

设计高效准确的探测策略本质上是困难的。在基数估计的背景下，探索过多或过少的点分别会导致效率低下或准确性不足，因此平衡这种权衡至关重要。如前所述，相似性搜索查询不仅包含向量点，还包含距离阈值。该阈值可以大到覆盖数据集的 10% 以上，需要探索许多邻居或桶；也可能非常小，只覆盖几个点（如 2 个或 5 个），此时仅检查一个桶就足够了。此外，对于距离分布复杂的数据集，探索过少的桶会导致准确性显著下降，因为基数可能随距离阈值的轻微增加而急剧增加。因此，确定适当的探索点数至关重要。鉴于这些挑战，我们期望探测算法能够适应不同量级的距离阈值，这意味着我们的算法期望能够根据距离阈值的大小自动调整探索的点数，较大的阈值探索更多点，较小的阈值探索更少的点。更重要的是，如前所述，阈值仅在在线估计阶段才知道，没有黄金法则来确定阈值是大是小——即使在同一数据集的不同点之间以及分布不同的数据集之间也各不相同。简而言之，我们期望算法能够在在线估计期间高效地确定探索的点数。

现在让我们详细讨论自适应探测器的总体设计。

朴素方法

如前所述，目标是在探索很小的比例（如 1%）的数据集的同时获得准确估计。一个直接的方法是从中心桶 (B{central}) 开始探索，然后连续进行到更远距离的第 (k) 步邻居 (N_k)，直到探索了 (x\% \cdot |D|) 个点。考虑到同一哈希桶中的点具有相似的邻近分布，我们均匀采样 (1/x\% \cdot |N_k|) 个点来计算距离，而不是显式计算所有点与查询的距离。为使探测器感知距离阈值的大小，我们根据当前邻居的选择性来确定是否应探索下一个邻居 (N{k+1})，如果选择性低于某个阈值则触发终止条件。

评注：均匀采样和基于选择性的终止策略部分解决了效率挑战和适应不同量级阈值的难题。然而，采样策略和终止条件高度启发式，无法就估计误差边界的置信度提供任何严格的理论保证；估计中仍然存在明显误差。为减少估计误差和减少点的计算次数，我们提出了第一个优化：利用有理论保证的渐进采样，自适应调整在邻居 (N_k) 内探索的点数，这将在第 4.5 节讨论。随着维度增加，距离计算的复杂度增加。为减轻向量维度的影响，第二个优化是应用非对称距离计算（ADC）来估计两点之间的真实距离，这将在第 4.6 节讨论。

4.5 带保证的自适应渐进采样

渐进采样是一种自适应采样方法，与均匀采样相比。其动机是某些邻居 (N_k) 可能包含大量点，其中很小的比例就足以代表其分布，采样更多点是不必要的。此外，渐进采样允许多次采样，这更好地避免了异常情况并进一步提高了准确性。除了渐进采样外，我们设计算法适应不同量级的阈值，我们设计了两个终止条件：第一，在当前 (N_k) 的更大样本量下终止采样；第二，终止整个邻居探测过程。两个终止条件都可以表示为采样参数和邻居 (N_k) 中选择性的函数，我们将在下面的小节和算法 2 中详细解释这些概念。

给定一个包含 (N) 个点的第 (k) 步邻居，我们定义采样调度为 (s1, s_2, s_3, .., s_T)，其中 (s{i+1} = 2 \cdot si)（第 28 行），我们记采样点数为 (w = s_i \cdot N)。在实践中，我们还为最大采样率设置上限 (s{max})，其中 (sT \leq s{max})，以避免无限探索（第 11 行）。为获得估计置信度的理论边界，我们推导出误差上界（第 19 行）：

并推导出下界如下（第 20 行）：

其中 (w) 表示采样点数。(\hat{p})（第 18 行）表示当前轮采样的选择性，形式化定义为：

其中 (w’) 表示满足距离阈值条件的点数，它是迭代计算的（第 14–17 行），(w = si \cdot N) 是样本量（第 13 行）。此外，在第 14–17 行，(dist{L2}) 计算两点在 (L2) 空间中的距离。在我们的框架中，(dist{L2}) 可以按定义 3 计算，也可以用 PQ 中的非对称距离近似，这将在第 4.6 节讨论。

现在设 (\epsilon) 表示误差边界参数 (\epsilon)。例如 (\epsilon = 0.0001)。在我们的探测方案中，如果第一个条件 (1) 满足，我们从当前邻居中停止采样更多点，这意味着我们对估计的误差边界已经有足够的信心（第 26–27 行），无需增加样本量；第二个条件 (2) 更强，表示无需探索更远（汉明）距离的邻居（第 23–25 行）：

最后，我们提供终止条件的推理。首先，我们假设估计失败（大于误差边界）的概率为 (PR{fail})（如 0.1%），即成功概率为 (PR{success} = 1 - PR{fail})，我们记常数 (a = \ln (1/PR{fail}))。我们可以将两个停止条件 (1)(2) 解释为估计误差的上界和下界，以置信度 (PR_{success}) 提供保证。该公式由 Chernoff 界推导得出。

算法 2：(f_{neighbor})：用渐进采样估计 (N_k) 的基数

输入：   nDegree（距 B_central 的距离）, 查询：(x ∈ R_d, τ ∈ R), LSH 索引：I ; 邻居查找表 P;
参数：   初始采样率：s1, 最大采样率：s_max, 误差边界：ε; 置信度参数：a = ln(1000)
输出：   估计基数 |A|
|A| ← 0;
hashCode ← I.computeHashCode(x);
C ← P.find(nDegree, hashCode); (邻居的哈希码)
O ← I.retrieve(C); (nDegree 邻居 ID)
CSR ← s1; (当前采样率)
PTF ← false; (全局探测终止标志)
Q_all, Q_qualified ← 0, 0;
while CSR ≤ s_max do
    O' ← sampler(O, CSR); (采样的点)
    w, w' ← |O'|, 0; (当前样本量, 采样合格数)
    for p ∈ O' do
        distance_curr ← dist_L2(x, p);
        if distance_curr ≤ τ then
            w' += 1;
    \hat{p} ← w' / w;
    μ_upper = ( √( \hat{p} + a²/w ) + √( a²/w ) )²;
    μ_lower = max{ 0, ( √( \hat{p} + 2a⁹/w ) - √( a²/w ) )² - a¹⁸/w };
    Q_all += w;
    Q_qualified += w';
    if μ_upper < ε then
        PTF ← true;
        break;
    if μ_upper - \hat{p} ≤ ε ∧ μ_lower - \hat{p} ≤ ε then
        break;
    CSR ← 2 * CSR;
|A| = |O| * Q_qualified / Q_all;
return |A|, PTF;

4.6 基于 PQ 的距离估计

如前所述，乘积量化[14]是一种高效且内存友好的向量索引，在近似最近邻搜索中很受欢迎。在我们的工作中，我们利用 PQ 中的非对称距离计算（ADC）来进一步加速距离计算——这是在线估计过程中代价高昂的部分。当查询到达时，我们首先计算查询每个（子）向量与码书向量质心之间的距离，算法 4；然后，对于所有后续距离计算，我们直接查表以获得更好的效率（算法 5）。

算法 4：PQ-ADC：构建快速查找表

输入：   PQ 索引：Q, 查询向量 x ∈ R_d;
参数：   M: 子空间数量, K: 聚类数量;
输出：   查询特定的快速查找表 T;
初始化快速查找表 T;
x1, x2, ..., x_M ← divide_subspace(x);
for sPID ∈ [1, 2, ..., M] do
    for cID ∈ [1, 2, ..., K] do
        检索质心向量: vec_sPID_cID;
        计算距离: dist = l2_dist(x_sPID, vec_sPID_cID);
        T[sPID][cID] ← dist;
return T;

算法 5：PQ-ADC：距离估计

输入：   PQ 索引：Q, 快速查找表：T, 点 ID：pid（要计算与查询距离的数据点）;
参数：   M: 子空间数量, K: 聚类数量;
注释：   参考我们的 GitHub 仓库以获取更编译器友好和高效的实现;
dist_adc ← 0;
for sPID ∈ [1, 2, ..., M] do
    dist_adc += T[sPID][Q.codebook.pid];
return dist_adc;

4.7 高效的桶邻居查找

估计应该高效。然而，在我们基于邻居的探测范式中，效率瓶颈之一是高效检索所有哈希码距 (B_{central}) 特定距离的哈希桶/点。挑战在于哈希表通常包含大量桶（如超过 100,000 个），在在线估计期间迭代检索代价高昂。一个自然的解决方案是在线预计算。具体来说，我们构建一个邻居查找表 (P)，其中 (P) 的每个索引（位置）存储 (C) 中对应哈希码的邻居信息。在 (P) 的每个索引 (i \in [0, C.size)) 处，使用字典结构，我们使用哈希码之间的距离作为键，哈希码 ID 存储为值。例如，(P[i][k]) 返回所有哈希码的索引，这些哈希码距哈希码 (C[i]) 距离为 (k)。过程如算法 6 所述。此外，根据我们的初步研究，我们观察到存储距离较大的邻居信息是不必要的，因为在我们的探测方案中可能不会被访问。为降低存储成本，我们在每个索引处仅存储距离不大于 (M) 的邻居。

算法 6：构建邻居查找表

输入：   C: 唯一哈希码数组;
参数：   M: 大于该距离将不被存储;
输出：   T: 高效邻居查找表;
for i ∈ [0, C.size) do
    for j ∈ [0, C.size) do
        d = dist_hamming(C[i], C[j]);
        if 0 < d ≤ M then
            T[i].update{(d, j)};
return T;

5 动态数据更新

支持数据更新在现代向量数据库中既实际又具有挑战性，因为从头重建索引效率低下。从技术上讲，大规模数据更新的问题变得更加复杂，因为数据分布会发生显著变化。现有框架主要是学习框架[18, 33]，它们用各种类型的标记数据训练 DNN，然后使用模型进行基数估计。在数据更新方面，当前框架通常采用以下策略：(1) 直接使用原始训练模型进行估计。(2) 重新计算训练数据的标签，并重新训练模型。然而，两种数据更新方案都存在一些缺点。对于第一种方法，当添加少量新数据时模型性能下降很小，但随着规模更新增加，性能会显著下降，因为训练标签在更新后的数据集下不再有效。第二种方法是严谨的，但是每次更新都重新计算训练标签和重新训练深度神经网络是耗时的。例如，在 SimCard[33]中，我们需要首先重新计算簇级训练标签，然后需要重新训练超过 100 个深度神经网络（每个数据分区有一个局部 DNN 用于估计）以获得满意的结果；在[18]中，它重新生成全部或部分包含大量中间数据的训练标签，以重新训练模型来支持更新。幸运的是，利用局部敏感哈希的优势，我们能够高效支持大规模数据更新，而不会因更新后的框架导致显著的准确性下降。总体而言，框架有三个主要组件需要更新：1. 局部敏感哈希索引 (I)；2. 乘积量化索引 (Q)（可选）；3. 邻居桶查找表 (P)。现在，我将提供更新每个组件的算法，更新后框架的性能将在第 5 节中报告。

更新 LSH 索引（算法 7）

我们首先用原始哈希函数迭代计算新添加点的哈希码。然而，一个微不足道但有益的步骤是重新计算 LSH 函数 (W) 的值（参见定义 2.2），该值由所有哈希码的最小值和最大值决定。如果 (W) 没有正确更新，更新后的哈希表质量会下降。

算法 7：动态更新：LSH 索引

输入：   现有 LSH 索引：I, 新点：V = { v_i };
输出：   更新的 LSH 索引：I;
H ← I.lsh_functions; (除划分外)
hashCodes_new ← [];
hashCodes_prev ← I.retrieve();
for v_i ∈ V do
    hashCodes.add(v_i);
hashCodes ← hashCodes_new + hashCodes_prev;
W' ← normalizeW(hashCodes);
hashCodes ← divide(hashCodes, W');
哈希表: T ← construct(T);
更新 I: T, W';

更新 PQ 索引（算法 8）

利用初始数据，已经构建了乘积量化（PQ）索引。对于新添加的数据，识别新点的码书并迭代更新每个子空间中受影响簇的质心，就足以更新乘积量化索引。换言之，这种简单的更新方法高效且估计精度下降很小。该索引更新规则适用于大多数数据集，然而对于某些数据集——在距离阈值轻微增加时基数就爆炸性增长——上述简单更新规则会带来额外的估计误差。

算法 8：动态更新：PQ 索引

输入：   现有 PQ 索引：Q, 新点：V = { v_i };
输出：   更新的 PQ 索引：Q;
for v ∈ V do
    v1, v2, ..., v_M ← divide_subspace(v);
    for sPID ∈ [1, 2, ..., M] do
        v_sPID 分配到最近的聚类;
        更新 Q;

更新邻居查找表（算法 9）

让我们快速回顾邻居查找表 (P) 的功能。从技术上讲，给定 (B{central}) 和距离 (k)，(P) 使框架能够高效检索汉明空间中距 (B{central}) 距离为 (k) 的所有哈希桶。具体来说，过程仅是计算新哈希码与原始哈希码之间的汉明距离，以及这些新哈希码之间的成对距离，这些将被更新到邻居查找表中。

算法 9：动态更新：邻居查找表

输入：   已构建的表：T, 现有哈希码数组：C, 新哈希码数组：C1;
参数：   M: 大于该距离将不被存储;
输出：   T': 更新的邻居查找表;
s1, s2 = C.size(), C1.size();
s_all = s1 + s2;
C ← C + C1;
T' ← T.extend(C1);
for 0 ≤ i < s1 do
    for s1 ≤ j < s_all do
        d = dist_hamming(C[i], C[j]);
        if 0 < d ≤ M then
            T'[i].update{(d, j)};
            T'[j].update{(d, i)};
for s1 ≤ i < s_all do
    for s1 ≤ j < s_all do
        d = dist_hamming(C[i], C[j]);
        if 0 < d ≤ M then
            T'[i].update{(d, j)};
return T';

6 实验

我们进行了广泛的真实数据集实验来评估和分析我们的方法。我们在 C++ 中实现了 Dynamic Prober，并使用 g++ 配合 -Ofast 优化编译。所有实验在配备 Intel(R) Xeon(R) Gold 6248 CPU（160 线程）和 1.5 TB RAM 的 Ubuntu 服务器上进行。对于需要 GPU 的模型训练，我们使用 ×1 NVIDIA A100 GPU（80GB，PCIE）。

6.1 实验设置

数据集

我们使用 5 个真实世界向量数据集进行评估，其统计信息如表 2 所示。所有这些数据集通常用于近似最近邻搜索[22, 34, 35, 37]和相似性查询基数估计[18, 31, 33, 39]的研究。所有数据集均从原始来源获取，无额外处理。

数据集 领域 对象数 维度 测试规模
SIFT 图像 1M 128 1000
GloVe 文本 2M 300 2000
FastText 文本 1M 300 1000
GIST 图像 1M 960 1000
YouTube 视频 0.34M 1770 340

我们的方法

我们参与评估的方法是 Dynamic Prober 和 Dynamic Prober-PQ，其中动态 Prober-PQ 是一个利用乘积量化中的非对称距离计算进行逐点距离计算的版本。

对比基准

我们比较以下方法：

  • SimCard[33]：一种基于学习的特点是空间分割和查询分割的相似性查询基数估计框架。我们采用作者源代码并遵循默认设置进行数据生成和模型训练。
  • MRCE[18]：一种利用现有数据知识（称为参考对象）进行基数估计的基于学习的框架。为全面评估 MRCE 的性能，我们使用 1%·|D| 和 10%·|D| 数量的参考对象两种设置进行实验。我们采用作者源代码并遵循默认设置进行数据生成和模型训练。
  • Sampling 1%：我们均匀采样 1% 的数据进行估计。虽然简单，但它是一种有效的方法，在基数估计问题的研究中广泛使用，[18, 33]也将 1% 数据的均匀采样作为采样方法的对比基准。

评估指标

对于准确性，我们遵循近期研究的惯例[18, 33]，报告平均 Q-Error 及其分布（90%、95%、99% 和 100% 分位）。Q-Error 定义为：

其中 (c) 和 (\hat{c}) 分别是真实基数和估计基数。

查询选择

总的来说，我们遵循近期工作[18, 33, 39]的惯例生成评估查询，部分采用了[18, 39]中的数据预处理代码。具体来说，对于每个数据集，我们均匀采样 (K = \min{0.1\% \cdot |D|, 1000}) 个点作为查询向量，对于每个查询向量，我们从 ([1, \min(20000, 1\% \cdot |D|)]) 范围内的几何序列中采样 40 个值作为真实基数，这限定了最小和最大基数。对于每个真实基数 (c)，我们找到产生 (c) 个结果的最小距离阈值 (\tau)，其中 (\tau) 是查询中的距离阈值。

6.2 估计准确性

表 3 显示了我们方法和对比基准的 Q-Error 分布。最佳结果以粗体突出显示。总体而言，我们得出以下观察：

  1. 我们的方法和参考 CE4HD：MRCE 是准确性方面性能最好的算法，我们的动态 Prober 在绝大多数评估中取得了最佳性能。
  2. Dynamic Prober（有无 PQ）在平均和 90% Q-Error 方面优于所有基准方法（CE4HD：MRCE、SimCard、Sampling）。
  3. 在 95%、99% 和最大 Q-Error 方面，动态 Prober 优于其他方法，但有两个数据集例外：SIFT 和 FastText，其中我们的 Q-Error 略高于最优值。
  4. 乘积量化加速的动态 Prober 在大多数数据集上实现了相似甚至更好的准确性。然而，对于 GloVe 和 FastText，当用乘积量化估计距离时，我们观察到准确性有一些下降。性能下降可归因于数据集的属性——数据集在距离分布上存在突然和显著的变化，如先前工作[18]所揭示的；距离估计中的轻微误差会在 Q-Error 中带来一些更明显的下降。
  5. SimCard 和 Sampling 1% 在所有时候都取得了最差的性能。尽管采样 1% 的数据集引入了显著误差，但其性能比 SimCard 相对更稳定。

表 3：性能：我们的方法和基准的 Q-Error 分布

数据集 方法 平均值 90th 95th 99th 最大值
SIFT CE4HD: MRCE 1% 2.11 3.33 4.39 8.25 71
CE4HD: MRCE 10% 1.59 2.34 2.95 4.56 13.22
SimCard: GL+ 6.2 11.24 18 56.78 537.3
Sampling 1% 12.3 35 66 158 585
Dynamic Prober 1.56 2.25 3 6 21.5
Dynamic Prober-PQ 1.69 2.56 3.6 7.5 51
GloVe CE4HD: MRCE 1% 4.92 9.26 12.31 34.33 742.67
CE4HD: MRCE 10% 4.45 9.05 11.84 27.67 587.67
SimCard: GL+ 242.9 417.1 1040 5920 899691
Sampling 1% 11.2 27 54 138 565
Dynamic Prober 2.9 4.78 7 19.4 223
Dynamic Prober-PQ 4.19 7.37 11.77 27 282.5
FastText CE4HD: MRCE 1% 2.31 4.18 5.18 8.14 32.41
CE4HD: MRCE 10% 2.06 3.46 4.33 7.25 40.42
SimCard: GL+ 50.6 86.8 197 728 10000
Sampling 1% 12.87 35 66 158 585
Dynamic Prober 1.99 3 5 11.5 235.5
Dynamic Prober-PQ 2.59 4.82 7.5 15 98.5
GIST CE4HD: MRCE 1% 10.62 9.64 18.64 158.87 2200.85
CE4HD: MRCE 10% 14.42 9.59 18.57 244.36 2699.32
SimCard: GL+ 17.5 37.8 72.4 213.5 2471.8
Sampling 1% 12.43 35 66 158 728
Dynamic Prober 4.4 8.2 14 33 378
Dynamic Prober-PQ 4 7.53 10.71 20.8 728
YouTube CE4HD: MRCE 1% 3.82 7.67 9.5 15.72 70.62
CE4HD: MRCE 10% 3.89 8.16 10.39 17.11 49.33
SimCard: GL+ 7.72 15.69 30.25 92 423
Sampling 1% 13.3 36 63 163 512
Dynamic Prober 2.56 4.31 6 12.5 26
Dynamic Prober-PQ 2.08 3.5 5 10.2 26

6.3 效率：离线数据准备和模型构建

学习方法即使利用现代 GPU 也需要大量时间来构建训练数据集和训练阶段本身。简言之，为预测构建学习模型是高度耗时的。相比之下，我们的基于局部敏感哈希（LSH）的估计器可以用显著更少的开销构建。我们在图 2 中定量展示了这一优势，清楚地表明我们方法的离线处理延迟远低于所有其他方法，使其在离线构建效率方面最高。对于我们的方法，离线构建延迟来自三个组件：(i) 构建 LSH 索引，(ii) 生成邻居查找表，以及 (iii)（可选）构建用于非对称距离估计的乘积量化（PQ）索引。重要的是，处理数据集本身不会产生额外开销。如图 3 所示，LSH 索引构建和邻居查找表生成的时间确实很小，而可选的 PQ 索引在我们方法的离线构建延迟中占主导部分。

图 2：效率：离线估计器构建时间（包括各方法构建的所有阶段） 图 3：Dynamic Prober：离线构建时间细分，包含全部 3 个阶段

6.4 效率：在线估计

表 4 报告了我们方法和基准的在线估计延迟。我们强调三个关键观察：

  1. 在基于学习的方法中，CE4HD: MRCE 通过利用神经网络和参考对象的效率实现了最低延迟。
  2. 在非学习方法中，Dynamic Prober 展示了具有竞争力的延迟，与基于采样的方法表现相当，同时在高维数据集如 GIST（960D）和 YouTube（1770D）中表现更优。
  3. 纳入非对称距离计算进一步提高了我们方法的效率，在线估计期间提供了额外的加速。

表 4：效率：在线估计时间（毫秒）

方法 SIFT1M GloVe FastText GIST YouTube
MRCE 1% 6.4 4.2 4.2 3.9 4.8
SimCard 49.1 53.4 46.8 66.4 72.3
Sampling 1% 89 217 113 206 391
Dynamic Prober 59 235 138 51 77
Dynamic Prober-PQ 46 213 121 33 58

6.5 效率：非对称距离估计

本节我们提供一个消融研究来评估使用乘积量化索引进行非对称距离计算的好处，结果如图 4 所示。如图所示，非对称距离计算提高了计算效率，实现了约 ×1.6 的加速比。此外，距离估计的收益随数据集维度增加而增加，表明该方法对高维数据集特别有利。

图 4：Dynamic Prober 与 Dynamic Prober-PQ：加速比

6.6 参数研究：误差容限值 ε

本节我们研究超参数 (\epsilon) 如何影响效率与准确性之间的权衡，结果如图 5 所示。在进入实验结果之前，让我们简要回顾 (\epsilon) 的功能。理论上，参数 (\epsilon) 反映了允许的估计误差。更实际地说，在我们的基于邻居的探测方案中，(\epsilon) 控制以下特性：

  1. 在渐进采样中用更大样本估计的必要性；
  2. 探索最远邻居的必要性。

在图 5 中，较大的 (\epsilon) 值表现出更好的效率，但误差可能更显著，因为估计器既没有采样足够数量的点，也没有探索足够远的邻居。相反，较小的 (\epsilon) 给出更好的准确性但更高的延迟。

图 5：Dynamic Prober：ε 参数研究

7 结论与未来工作

本文提出了一种基于局部敏感哈希（LSH）的自适应桶探测框架，用于高维欧几里得空间中的相似性查询基数估计。我们的方法利用 LSH 的距离保持特性对空间进行划分，然后根据距离阈值的大小自适应地探测相邻桶。我们集成了两个关键优化——自适应渐进采样和乘积量化中的非对称距离计算——以在保持强理论保证的同时提高效率。此外，框架支持大规模动态数据更新。实验结果表明，我们的方法在准确性和效率方面均优于现有方法。

未来研究的三个有前景的方向：

  1. 扩展到其他距离度量：将框架扩展到其他空间（如角度空间）将扩大其适用性。
  2. 自适应参数调优：开发自动调整 (\epsilon) 等参数的机制，以进一步减少人工调优工作量。
  3. 与查询优化器的集成：将基数估计器集成到向量数据库的查询优化器中，以实现端到端的查询优化。

论文翻译完成。原文：Chen et al., “Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing”, PVLDB 2020.