Skip to content

Latest commit

 

History

History
135 lines (72 loc) · 23 KB

challenge.md

File metadata and controls

135 lines (72 loc) · 23 KB
Raw

4.2 向量数据库面临的挑战

截止目前，向量数据库在国内外仍处于发展的早期阶段，其稳定性、效率和应用场景正在实践中不断探索。

本节列举了目前向量数据库面临的主要挑战和未来发展趋势。

4.2.1 向量标量混合查询

向量标量混合查询在向量检索的基础上添加了标量过滤约束，即返回的相似向量还要满足给定的过滤条件。根据标量过滤与向量检索的执行顺序，当前的混合查询方法可分为三类：前期过滤、后期过滤、融合过滤。前期过滤是指先根据标量约束过滤出符合标量要求的候选，然后在此候选上执行向量检索获取向量距离较近的结果。后期过滤是指先执行向量检索召回向量距离较近的候选，然后对候选进行标量过滤获取满足标量约束的结果。融合过滤是指向量检索和属性过滤同时执行，直接获取既满足向量相似性又满足标量约束的结果。根据具体处理场景的差异，三种不同的过滤策略各有优势。当前，根据这三种过滤策略设计的方法虽能满足一些特定应用的需求，但都不同程度地存在局限性。向量标量混合查询仍面临以下几个挑战：

  1. 如何确定最优候选数量？无论是前期过滤还是后期过滤，最终结果都是两步生成的，即先生成候选，而后在候选上获取结果。因此，确定最佳候选数至关重要，这直接决定着搜索的效率和结果的精度。比如，如果候选数过少，则可能导致获取的最终结果不足甚至得不到符合要求的结果，破坏了结果的精度；如果候选数过多，则可能导致大量的冗余计算，降低了搜索的效率。有效且高效地评估最佳候选数仍然是一个具有挑战性的问题。

  2. 如何联合向量距离和标量距离？融合过滤方案通常需要综合评估向量相似性和标量的匹配度，而后为两者打一个总分，以此排序中间访问结果。然而，向量距离与标量距离之间往往不具有可比性，因此需要将两者映射到相同的度量空间中，并分配不同的权重。然而，不同的场景下的向量距离和标量距离可能具有显著不同的度量方式和权重分配方式，比如有时候向量距离更重要，而有时候权重距离更重要。因此，设计自适应的权重分配策略仍然具有挑战性。

  3. 如何选择最优的执行策略？由于不同的混合查询策略在不同的查询负载下各有优势，一些向量数据库（比如Milvus、ADBV）实施多种混合查询策略，并基于代价模型对不同查询选择执行代价更低的策略。然而，这些方法假设可选择性等一些关键指标是已知的，这并不符合很多真实场景的特征。此外，为了估算搜索时间开销，它们的索引方法局限在暴力扫描、量化压缩等技术，难以扩展到当前最优的导航图索引上。因此，设计泛化性更强的最优执行策略选择方法仍具有挑战。

  4. 如何处理复杂的标量过滤逻辑？当前的方法主要适用于处理标量过滤逻辑较简单的场景，比如“=”。然而，真实场景存在更多复杂的过滤逻辑，比如“>”、"<"、“>=”、"<="等，这给某些混合查询方法带来显著的挑战。例如，融合过滤策略难以处理不等式过滤逻辑。因此，设计一种鲁棒性更强的索引和检索策略以同时支持各种过滤逻辑的混合查询仍然需要进一步研究。

4.2.2 海量数据索引支持

@向隆？

4.2.3 动态数据集

经典的关系型数据库管理系统有四项基本操作：增、删、改、查。目前，向量数据库可以完成高效的查询（最近邻搜索），部分向量索引可以支持动态插入，对于数据的删除、修改，则大部分向量索引难以支持。然而，在实际应用场景中，对动态数据集的支持是一个基本需求。例如，在一个服务于电商平台的推荐系统中，一个商品的上架和下架就会涉及这个商品对应向量在数据库中的插入和删除；商品描述和详情的修改又会涉及向量的修改。

在向量数据库中高效处理动态数据集至少包含以下几个技术挑战：

  1. 向量索引的更新。大部分向量索引需要根据数据集中的数据分布决定索引结构，而处理动态数据集要求索引能够自适应地根据数据分布的变化调整索引的结构。比如，随着新数据的插入，树索引需要细化分区，增加或重新选择空间分割方式（平面）；而数据的删除意味着需要分区的合并或分割方式的重新选择。对于图索引来说，插入和删除都意味着图中拓扑结构的调整，既要保证新增加的连接（边）不会影响图的稀疏性以保证查询效率，又要保证删除旧有的边不会让图索引的导航性受到影响。此外，由于图数据访问方式的复杂性，图索引的更新比其它索引更加困难。
  2. 向量数据存储的更新。相比于标量数据，向量数据单条数据占据空间更大。因此，频繁的删除会使得存储空间更大的碎片化。此外，为了提高向量数据的访问效率，向量数据往往会分区存储以利用数据局部性（尤其是对于磁盘数据），同一分区的数据共同访问的概率更高。数据的更新可能破坏原有分区的平衡性，导致查询效率的降低。
  3. 读写操作的并发控制。对向量索引的数据更新往往会引起索引结构以及其它数据存放位置的变化，相比于标量索引（如B+树），数据更新时，需要锁的范围会更大。因此，如何高效处理对于向量索引的读写并发控制也是一个亟需克服的挑战。

4.2.4 多模态检索

当前的向量检索主要面向单一模态场景，即底库数据和查询输入数据具有相同的模态，它们生成的向量均在同一向量空间。随着对检索质量越来越高的要求，多模态检索逐渐得到更多的研究关注和应用。比如在电商场景，用户可能输入一张拍摄的照片并添加一些文字描述以检索一些与照片相似且满足文字约束的商品。在另一些场景中，用户可能仅仅输入文字来检索符合文字内容约束的一些图片。在以上两个场景中，检索过程均涉及图片和文字两种不同的模态。更多模态的引入带来更高质量检索结果的同时，也给检索技术带来诸多挑战。

  1. 多模态数据向量化。通常来说，不同的编码器被用于编码不同模态的数据，比如ResNet用于编码图像、BERT用于编码文本。同一个编码器可将不同数据映射到相同的向量空间，从而通过向量检索直接获取相似结果。然而，多模态检索要求编码器能同时理解不同模态数据。一些多模态编码器比如CLIP虽在图文理解上展示了巨大成功，但其仍面临着较大的编码器误差。因此，高质量地编码多模态数据仍然是一个具有挑战性的问题。

  2. 多模态检索策略。当前的多模态检索策略主要依赖于多路召回或模态融合，它们并不能很好地捕获不同模态之间的重要性。例如，多路召回需要先执行多路的单模态检索获取多个候选集，然后通过候选合并获取最终结果。然而，这些候选之间可能没有交集，而且合并过程本身就具有挑战性。此外，模态融合需要首先克服高质量编码的问题。因此，基于现有技术设计一个更有效的多模态检索方案仍然值得研究探索。

  3. 多向量索引和检索。多个模态导致一个对象包含更多的向量。当前的索引技术为每一个模态的向量单独构建索引，这限制了多向量检索的效率和精度。此外，更多的向量也进一步加剧了向量计算开销。因此，为多向量对象设计一个有效且高效的索引和检索策略是一个值得探索的方向。

  4. 查询向量分布与底库向量分布不一致。跨模态检索提出了一种新的查询类型：分布外查询（Out-Of-Distribution, OOD）。在这种场景下，查询向量与底库向量具有显著不同的分布，一般的向量索引和检索策略在处理这类查询时面临着显著的精度和效率瓶颈。因此，针对这类查询如何设计专门的索引和检索策略需要进一步的研究探索。

4.2.5 索引构建自动化

如本书所归纳，向量索引的发展已经有很长的历史，期间诞生了几十上百种向量索引。时至今日，仍有多种索引在不同的评估指标、不同数据集上占据着优势地位。比如，图索引中的HNSW在查询性能上是表现最佳的索引之一，而LSH索引在处理超高维向量时有明显优势，树索引中的Dumpy在时间序列上有着更好的可伸缩性。

对于用户而言，如何针对特定的数据集选择最合适的索引是非常困难的，而且在选择索引后，如何针对不同索引的特性选择构建参数，以及在运维过程中如何监测索引性能以进行调优则更加依赖对特定索引的研究知识。

由于以上问题的存在，用户往往会选择一个“基本可靠”的索引（即性能优良，广泛使用，社区活跃，文档丰富）来使用。比如，目前大部分的向量数据库仅支持两种索引，树索引中的IVF-Flat和图索引中的HNSW。尽管这两种索引在大部分时候可以基本满足用户需求；然而，缺少对特定数据分布和应用场景的分析，可能会让用户承担更高的成本和不可靠的服务。换句话说，索引类型和索引构建参数的不合理选择会使得用户的硬件资源不能发挥出应有的价值。

4.2.6 数据隐私与安全

隐私保护

得益于云计算的发展，它以较低的成本提供了可扩展的计算和存储能力，为各类企业、政府以及个人用户提供了便利。他们已经开始将他们的计算任务和存储需求转移至第三方公共云服务提供商，例如微软的Azure、亚马逊的AWS、阿里云等。虽然云计算为企业提供了前所未有的机遇，例如提升服务、扩大收入、与其他合作伙伴进行协作，但它也不可避免地带来了一些严重的副作用，尤其是关于隐私的问题。在向量检索领域，隐私保护的问题同样也很重要。向量检索作为一种常见的数据检索方式，其数据通常包含大量的用户信息和敏感数据。当这些数据被上传到云端进行处理和存储时，如果没有适当的隐私保护措施，就可能会导致这些敏感信息的泄露。尤其在云计算环境中，数据的所有者和处理者往往不是同一方。这就意味着，数据所有者需要将他们的数据委托给云服务提供商进行处理和存储。如果隐私保护方案不够完善，那么存储在云端的用户数据就有可能被泄露。此外，向量检索的特性使得数据在处理过程中可能会被复制和传输，这进一步增加了数据泄露的风险。因此，如何在享受云计算带来的便利和可扩展性的同时，有效地保护向量检索中的数据隐私，已经成为了一些学者的工作重点。

现有方案的限制

在近似最近邻检索算法中的隐私保护问题可以表示为如何在不泄漏原始向量、查询或返回结构的情况下执行。近年来，已经有很多工作在隐私保护查询取得了进展，这些加密策略在很难在高维度向量的加密中直接应用主要是因为有以下限制:

  1. 只适用于关系数据库或低维数据集的限制：现有的隐私保护查询方法主要是针对关系数据库或低维数据集设计的。关系数据库是以表格的形式存储数据的数据库，而低维数据集的数据维度通常小于5。然而，对于高维度的数据，这些方法可能不适用。这主要是因为高维数据的复杂性和多样性，使得直接应用这些方法可能会导致效率低下或者无法达到预期的隐私保护效果。
  2. 采用完全同态加密可能耗时过长的限制：完全同态加密（FHE）是一种允许在密文上直接进行计算的加密方法，而无需先解密。这样可以保护数据的隐私，但是，FHE的计算效率通常较低，特别是对于复杂的查询例如近似最近邻检索，如果使用FHE，可能会导致查询时间过长，从而影响系统的性能。
  3. 使用顺序保持编码（OPE）可能产生过多的通信和时间成本的限制：OPE是一种可以在密文上保持原始数据顺序的加密方法。这使得它可以提高处理查询的效率，因为可以在密文上直接进行比较操作。然而，使用OPE时，为了访问加密的索引和解密密文，可能需要进行多轮的通信，这会增加通信的时间和成本。此外，多轮通信也可能增加数据泄露的风险。

基础概念

在介绍加密近似最近邻检索前，让我们先了解一些加密算法的概念。

加法同态操作

在密码学中，"同态"这个词描述了一种能够在加密数据上进行计算，并且这些计算的结果与在未加密数据上进行相同计算的结果是一致的，即使数据在计算过程中一直保持加密状态。举个例子，假设我们有一个加法同态加密系统，我们有两个数字2和3，我们先加密这两个数字。在加法同态系统中，我们可以直接对这两个加密的结果进行加法操作，得到一个新的加密结果。然后，当我们解密这个新的加密结果时，我们会得到5，这就是2和3的和。这就是加法同态的主要特性，即使在加密状态下，我们仍然可以进行加法操作，而不需要解密数据。这种特性对于许多应用非常有用，尤其是在需要在加密数据上进行计算的情况下，如云计算和数据隐私保护等。

Paillier加密

Paillier加密是一种公钥加密系统，由法国密码学家Pascal Paillier在1999年提出。这种加密系统的主要特性是它的同态性质，特别是它支持加法同态操作Paillier加密系统的工作原理是这样的：

  1. 密钥生成：首先，选择两个大的质数$p$和$q$，并计算$n = p \times q$和$\lambda = \text{lcm}(p-1, q-1)$，其中$\text{lcm}$是最小公倍数函数。公钥是$n$，私钥是$(n, \lambda)$。
  2. 加密：给定一个明文$m$和公钥$n$，选择一个随机数$r$，其中$0 < r < n$和 $\gcd(r, n) = 1$，$\gcd$是最大公约数函数。密文$c$是$c = g^m \times r^n \mod n^2$，其中$g$是一个随机选择的数，满足$\gcd(g, n^2) = 1$。
  3. 解密：给定一个密文$c$和私钥$(n, \lambda)$，明文$m$是$m = \frac{L(c^\lambda \mod n^2)}{L(g^\lambda \mod n^2)} \mod n$，其中函数$L(x) = \frac{x-1}{n}$。

Paillier加密的同态性质表现在以下两个方面：

  1. 加法同态性：给定两个明文$m_1$和$m_2$，他们的加密结果的乘积将等于$m_1 + m_2$的加密结果，即$E(m_1) \cdot E(m_2) = E(m_1 + m_2)$。
  2. 乘法同态性：给定一个明文$m$和一个整数$k$，$m$的加密结果的$k$次方将等于$k \cdot m$的加密结果，即$E(m)^k = E(k \cdot m)$。

AES加密

AES (Advanced Encryption Standard) 是一种对称加密算法，也就是说，它使用相同的密钥进行加密和解密。AES由美国国家标准和技术研究院（NIST）于2001年发布为FIPS PUB 197，并在全球范围内广泛使用。AES是一种基于块的加密算法，通常使用128位的块，但密钥长度可以是128位、192位或256位。

AES的加密过程包括多个轮次，每个轮次都包含几个步骤：字节替换（SubBytes）、行移位（ShiftRows）、列混淆（MixColumns，最后一轮除外）和轮密钥加（AddRoundKey）。每一轮都使用了从原始密钥派生出的不同轮密钥。轮数取决于密钥的长度：10轮用于128位密钥，12轮用于192位密钥，14轮用于256位密钥。解密过程与加密过程相反，使用逆操作以相反的顺序进行。

SCPQ

安全粗糙乘积量化（SCPQ）是一个为了解决在云上进行近似最近邻检索的方案。SCPQ是一种基于高维隐私保护查询框架的方法，主要结合了加密和乘积量化（PQ）技术。这种方法不仅考虑了数据重构的隐私，还包括数据所有者、数据用户、私有云和pCSP的角色。 作者在论文中举例了一个场景，例如在基于云的电子健康记录（EHRs）系统中，一个医院的医生可能是其框架中的用户。当用户提交查询时，私有云首先将查询转换为相应的代码和索引。然后，pCSP与用户交互，在加密形式下搜索查询，并使用简单的加法同态操作以获取查询和原始向量之间的加密距离。最后，pCSP从代码中维护一个IVF列表，并解密候选距离以返回结果。

框架

框架的目标是在云环境中安全地进行高维数据存储和近似最近邻检索。这个框架涉及四个主要参与者：

  1. 数据拥有者（DO）：DO拥有一个在d维空间中的数据库D。由于计算和存储资源有限，DO将数据库和搜索工作负载外包给pCSP。为了数据安全，DO在外包之前会对数据进行加密。为了在搜索过程中保护数据，DO应该为数据构建一个倒排文件（IVF）列表，并将其加密后发送给pCSP。

  2. 隐私保护的云服务提供商（pCSP）：pCSP通常由第三方服务提供商支持。他拥有可扩展的计算和存储设施，可以为高维数据存储和近似kNN查询提供云平台。然而，他对数据和查询感兴趣，可能会非法地解密和搜索DO存储的数据，或者受到外部攻击者的攻击。假设他可以正确地处理近似kNN查询，但不能从加密数据中推断出任何有价值的信息。

  3. 用户（US）：US拥有小型的存储和计算能力，例如移动终端。当发出查询请求时，授权的US可以访问存储在pCSP上的数据，并获取查询结果。假设US可能不完全可信，因为他可能会获取到查询结果之外的一些数据，或者与pCSP合谋泄露交互信息。

  4. 中间服务器（PrC）：每个US都拥有一个PrC，这是一个在DO和US之间的可信服务器，可以由一组US共享。他有限的存储和计算能力，但通信带宽较小，他可以执行一些低成本的操作，例如，他通过可信渠道接收US的查询请求，并向US返回量化代码和查询索引。

为了保护搜索的安全，引入了Paillier同态算法，它支持加法同态和概率非对称加密。可以利用这个属性来加密查找表，并在不解密的情况下得到加密的近似距离。此外，还引入了AES，用于预处理数据库和代码。总的来说，将数据库和查询量化为短的PQ代码，并使用AES加密原始数据和代码，以在框架中构建IVF列表。为了安全地搜索，pCSP持有DO的加密数据库和加密的IVF列表；US从他的PrC提交加密的查询索引给pCSP；pCSP与US一起响应查询。下一个小节将详细描述完整的解决方案。

方案

全同态加密虽然是一种很好的加密方式，它可以使pCSP在密文形式下安全地进行搜索。然而，这种方法需要大量的密文计算和运行时间，尤其是在US必须处理大量的全同态解密操作时。这种计算负担对于移动终端等设备来说可能过于沉重。
考虑到量化查询的特点。如果量化查询直接使用Paillier加密，那么每个查询需要进行大量的同态加密和同态加法。这对于移动终端用户来说，时间成本可能过高。因此，SCPQ选择不在US中直接执行Paillier加密，而是将码本转移到可信的PrC进行安全和快速的量化。整个方案需要保护搜索过程的安全。DO使用秘密密钥K加密数据库和倒排文件列表，并使用公钥pk加密查找表。US在加密查找表的成对密文上执行多次同态加法。然后，pCSP解密与加密数据对应的相关距离。这样，通过使用AES和Paillier算法，可以保护存储在pCSP和US上的数据。最后，为了减少通信成本，研究者引入了粗量化来构造粗码本和粗量化器，并使用k-means算法。他们设计了IVF列表以避免穷举搜索，这样US只需要访问与查询索引对应的IVF的内容。
在整个查询过程中，US只需要进行简单的同态加法，因为大的同态解密负担被转移到了pCSP。这样，SCPQ解决方案在响应时间上应该更有效、更实用，特别是对于实际应用来说。

在这个过程中，粗码本和粗量化起也是一个重要的环节。这两个元素的设计目的是对数据集进行有效的划分和索引，以便在查询处理中快速并准确地找到候选结果。粗码本是一个包含了数据集中所有可能的粗量化值的列表。它的构建通常基于k-means聚类算法。在这个过程中，数据集被划分为$K_c$个簇，每个簇的中心（即聚类中心）代表了一个粗量化值。这些聚类中心构成了粗码本。

粗量化器$Q_c$的作用是将数据点映射到粗码本中的一个条目。具体来说，对于任意给定的数据点$x$，粗量化器会找到粗码本中最接近$x$的条目，并将其作为$x$的粗量化值。这种映射过程可以通过计算$x$与粗码本中每个条目的距离，并选择距离最小的那个条目来实现。

在这个设计中，粗码本和粗量化器共同作用，将数据集划分成多个簇，每个簇都由一个粗量化值（即聚类中心）代表。这种划分和索引方式可以大大提高搜索效率，因为在处理查询时，只需要在与查询索引对应的簇（即IVF列表的条目）中搜索，而不需要对整个数据集进行穷举搜索。

然而，这种方法也有一个缺点，那就是可能会导致搜索结果的质量下降。因为在处理查询时，真实的结果可能会出现在查询索引以外的簇中。为了解决这个问题作者提出了一个解决方案，即在处理每个查询时，选择$w$个最近的簇，并在这些簇的IVF列表条目中进行搜索。这样，可以获取到更多的候选结果，从而提高搜索质量。

4.2.8 索引的理论保障与可靠性

向量索引的一个额外问题是性能的方差较大。即，对于不同的查询，得到指定精度的需要的查询时间（或给定查询时间的查询精度）差异是很大的，这一点对于图索引来说尤其明显。

在真实场景当中，用户往往需要处理不同难度的查询，这样的结果是会带来不可靠的服务质量。相比较而言，树索引有较为完备的理论保障和精确查询算法；LSH索引可以提供基于概率的精度保障；而基于图的索引和基于量化的索引对应的理论保障则与真实场景仍有较大偏差，这实际上增加了使用上的不可靠性。

因此，从理论意义上讲，如何为图和量化索引建立理论模型，进一步提供理论保障仍然是一个需要解决的问题；从实践意义讲，如何设计一个性能方差较小且高效的向量索引，也是提升向量索引服务质量必须要解决的问题。