向量数据检索方向调研

本文由ykindred首发, 转载请标明出处.

向量数据管理方向调研报告向量数据管理的概念和问题个人思考问题：如何建立向量数据库？或者说，对于大规模高维向量数据，如何进行有效的管理从而能够实现增删改查等操作？第一想法是建立类似Trie树的数据结构，对每一个维度进行分类查找，时间复杂度在O(n)。但这样会产生两个问题：一是对于连续的数据来说不能成立，二是空间复杂度是指数级别的。可以考虑以某种标准对每个维度的数值进行分类，比如按大于等于0和小于0分类再建立Trie树（这时候其实就成为了某种二叉树），在维度比较高，并且向量数量不那么多的情况下有着比较理想的时空复杂度。但是又出现了两个问题：最主要的问题在于如果数据的分布非常不均匀，会导致时间复杂度的退化；其次是这种方法的空间复杂度虽然降低了常数，但依然是指数级别增长，开销非常大。换一种思路来说，可以根据向量的某种“特征”建立哈希表，特征相似的向量，哈希值应该相同。查询时先进入具有相似特征的向量集合中，再进行精确查询。这种“特征”是什么呢？应该是向量数据的辐角。但是问题又产生了：n维的向量将会具有n-1个辐角，处理这n-1个辐角向量的难度相比处理n维向量的难度来说并没有下降。以我目前的知识水平来说实在难以给出答案，于是我开始了本次学习。学习内容一、读综述Vector Database Management Systems: Fundamental Concepts, Use-cases, and Current Challenges, by Taipalus，学习向量数据和向量数据库的基本概念、用例、挑战

向量数据和向量数据库的基本概念：

为什么需要向量数据？非结构化的数据，比如长文本、图片、视频等，可以将其多方面的特征量化，从而用多维向量储存，每个维度储存一个特征，这个过程称为向量化。向量化的好处可以通过计算两个向量之间的夹角或欧式距离来判断它们的相似程度，从而找出相似的数据。
为什么向量数据需要特殊处理而不能用传统数据库（SQL）处理？需要储存的向量通常具有高维度、稀疏、并且很复杂，在查询时往往需要查询相近的内容，而非精确查询（类似搜索引擎），这与传统数据库的特征不同。
概念：向量数据管理系统（VDBMS）专门管理高维向量数据的系统，提供对相似高维向量的快速精确搜索。与数据管理系统（DBMS）类似，VDBMS包括但不限于数据查询、操作、收集元数据（数据属性）、编制索引、控制数据访问权限、备份，具有可扩展性并且提供与其他工具的接口。部分DBMS比如PostgreSQL和Redis也提供了管理向量数据的功能，但未针对向量数据进行专门优化。
数据库系统的架构数据库系统包含一个或多个DBMS。首先DBMS中的传统数据（比如文本）被向量化（向量化后的向量被称为vectors embedding或者特征向量feature vectors（不同于线性代数中的特征向量eigen vectors）），然后传给VDBMS。VDBMS不止储存向量本身，还会储存一个向量标识符和数个向量元数据（向量的属性），往往还有这个向量代表的原始数据本身。

（图来自原文）数据库系统的架构，底层数据库提供数据，应用层面查询数据，均向量化后在VDBMS中操作核心是这几个环节：向量索引化，数据向量化，向量相似性评估 5. 向量编制索引的一些算法（核心思想是牺牲部分精确度，换取更高的速度）： PQ（Product Quantization乘积量化）：将高维向量分成多个子向量，再分别进行聚类量化 LSH（Locality-Sensitive Hashing位置敏感哈希）：将位置相近的向量对应到同一个桶里 HNSW（Hierarchical Navigable Small World，分层-可导航-小世界）：建立小的世界网络，用于快速近邻搜索还有R-Tree，KD-Tree，随机投影算法等 6. 数据向量化：有多种方式，文中没有详细展开 7. 向量相似性评估的方法： Jaccard相似度：通过比较两个集合共同元素与总元素数量的比例来评估相似度 Euclidean距离：使用欧式空间的直线距离来判断相似度点积/余弦相似度：计算向量夹角来判断相似度产品和特征：

论文写作时（2024）几个主要的VDBMS：Pinecone, Chroma, Milvus, Weaviate, Vald, Qdrant, Deep Lake
提供向量管理功能的DBMS: PostgreSQL, MongoDB, Cassandra, Redis, SingleStore 用例
相似性搜索：多媒体搜索：例如在电商平台中查找相似商品；推荐系统：推荐相似内容；轨迹分析：优化物流、交通等领域的调度方案；人脸识别等。
图、视频的相似性搜索：以图搜图：图片通过卷积神经网络进行特征提取，这些特征向量化后可以用于相似性搜索；视频进行关键帧提取后类似。
声音识别：可用于用户认证和交互型智能体，交互型智能体可根据不同的声音做出不同回应
聊天机器人的长时记忆：自然语言经过处理后可以作为向量储存起来。虽然其他用其他方式也可以实现聊天机器人的记忆，但生成式模型能够记忆的文本往往有限，可以使用VDBMS实现长时记忆。进一步说，VDBMS可以储存文档作为生成式AI的输入，模型回答问题时从文档集合中检索出相关的信息，从而提高回答质量。（这种方法称为RAG，Retrieval-augmented Generation，检索增强生成）目前面临的挑战
速度与精确度的平衡 VDBMS中的查询往往通过ANN（近似最近邻）实现，一些算法如PQ算法能够降低查询的时空复杂度，但需要牺牲精确度。而无损算法如R-trees则时空复杂度较高，随着数据量的增大，速度与精确度的权衡变得更加重要，一个同时确保速度和精确度的方法是为同一个向量使用多个索引，但这种方法需要更多的储存容量。
增长的维度和稀疏性部分领域要求对数据有更全面更精确的认识，这导致数据分析的特征数量的提高，导致维度增加和计算复杂度增加。随着维度的增加，可用空间变得更加稀疏，这种稀疏性使得索引和检索变得复杂，因为为稠密数据设计的算法难以有效地表示和查询稀疏数据。
相比DBMS来说实现技术尚不成熟 VDBMS作为较新的系统，其实现方式还在剧烈更新变化中，因此不易于维护。而DBMS有着庞大活跃的用户社群，能够获得在线教程、第三方扩展和集成等支持。信息安全也是一个重要方面，DBMS较为稳定，具有更好的安全性，而VDBMS可能还存在一些安全隐患。

二、读技术博客Vector Embeddings Explained-Weaviate Blog

问题：我了解到高维向量的“聚类”概念，有一个问题我感到很疑惑，技术博客里面说“水果”和“苹果”“葡萄”这些词对应的向量接近，但我发现“水果”所指代的范畴明显与具体的水果不同，有没有可能“水果”这个词应该用更大的对象来表示？比如说一个高维平面？如果用一个高维平面来表示“水果”的话，具体水果的向量是不是会分布在这个平面上或者接近这个平面？有没有人做过相关的研究呢？既然词向量能够进行线性运算，那词向量会不会形成线性结构呢？比如说平面？在检索时能不能先检索该向量接近的平面，再在平面附近进行检索呢？

经过思考和查阅资料后得出了以下几个（初步的）答案： 1.词向量的线性运算确实能够揭示出词向量空间中的某些结构，在某些情形下，这种结构可以近似为一个低维线性子空间（比如平面） 2.这种低维结构可能呈现在语法上，也可能呈现在语义上 3.可以通过统计学方法来分析出子空间的维度，比如主成分分析 4.这种做法与聚类的思想类似，本质都是对词向量进行分类检索如果要把“水果”映射到高维结构（比如超平面）的话，有以下两个问题： 1. 模型复杂度的升高 2. 表示类别的词汇可能是多义的，不同语境下的词向量会有所不同

向量数据管理的常用算法主要用来解决ANN近似最近邻问题学习内容：视频BV11a4y1c7SW，BV1BM4y177Dk，查阅网络资料，咨询AI大模型

LSH，局部敏感哈希：目的：设计哈希函数，使得相近的向量能够尽量映射到相同桶中。检索时在相同桶（以及相似的桶）中检索即可，常用的（使用欧式距离作为度量的）哈希方法是随机投影后进行空间划分，在相同单元格内的数据点映射到相同桶中。主要问题：哈希函数的选择，处理复杂度受数据分布影响大，内存开销较大
PQ，乘积量化：目的：对数据进行压缩，降低空间和时间开销（牺牲精度），具体操作是将原向量按维度划分为多个子向量，对每个子向量量化（映射到聚类后的最近中心点），形成若干个码字索引，储存和查询时对码字索引进行操作即可。主要问题：精度损失较大优化方向：
近似过程中，某些维度可能比其他维度更重要，为每个维度分配权重后的PQ算法称为加权PQ（W-PQ）
可以同时进行多个量化方法，并将结果结合起来，增大开销但减小误差，称为多重量化（MQ）
结合投影和量化，可以进一步优化精度和速度（QP）
可以使用统计学方法来补偿检索时的误差
HNSW算法，（分层可导航小世界）目的：为数据点引入图结构（小世界网络）来判断它们之间的相似性关系。引入“分层”的概念，将图结构分成多个层优势：高效，高速，高准确度，能够适应不同大小的数据集主要问题：内存开销较大，建图所需时间较长
R-树是一种高维平衡树结构，每个节点对应一个矩形（MBR，最小外接矩形）目的：建立平衡树，以支持快速查询（查询时只需遍历可能相交的 MBR）
KD-树目的：建立一个二叉树，把空间用平面划分，每个节点对应一部分空间优点：构建简单，储存效率高，低维空间中查询效率高缺点：在高维空间中性能下降明显插入删除效率低

向量数据管理的前沿方向学习内容：主要是网络搜索和询问AI 一、分布式向量检索把向量检索做成分布式系统，用于大规模向量数据管理。核心问题：

如何将数据分布到各个节点？查询的时候该访问哪些节点？
节点之间的访问量不均衡，某些节点可能查询量过大，某些节点查询量非常小，如何保证查询分布均衡？
延迟与召回率如何均衡？（即时间与精确度的平衡）
如何降低节点间通信的开销？具体研究方向：
SPANN算法（分布式ANN算法）的优化：通过向量分区和图结构来在每个分区内高效检索
HNSW分布式化：把HNSW图分布到不同节点可以解决内存占用大的问题
负载均衡与分布策略研究：通过动态分片（比如说，先进行聚类，再把一个聚类作为一片来分区）来保证向量分布均匀，查询时可以只查询相关分片，减少节点通信的开销未来研究热点：
RAG的规模化部署：如何部署大规模的向量用于实现RAG？
存算一体化：在储存节点处直接进行ANN计算以减少通信开销
结合分布式计算（异构硬件加速）：合理调度GPU、FPGA等计算资源二、多模态向量检索对不同类型的输入数据进行相似性检索，用于处理多模态数据（比如图文一体，音视频一体的数据）研究热点：
跨模态表示学习：将不同模态的向量映射到同一个空间（保证相似性关系）
多模态RAG：检索不同类型相似数据三、稀疏向量检索稀疏向量是维度高，但大部分为0的向量。可以通过倒排索引（inverted index）进行高效检索。核心问题：
高维向量如何稀疏化？
大规模稀疏向量如何储存？如何高效检索？
如何同时搜索稀疏向量和稠密向量？研究热点：
深度学习驱动的稀疏向量检索
稀疏 + 稠密的融合检索