向量数据库原理解析

基础的向量数据库原理想必都很熟了，其核心就是对于所有要查询的query embedding，找一个或多个与其最相似的data embedding。
向量数据库做成对embedding得相似度盘算很简单，难就难在：你面对的是一个可能存储几十万几百万embedding的数据库，对于恣意一个来访的embedding，你真的要遍历这几百万数据库吗？
为了搜索服从，各种框架就要开始发力了。
最简单的方法

假如你能提前把embedding分到几个独立的数据库里，例如这个库存储百科信息，那个库存储金融专业信息，则单个数据库就会比力小了，再让rag通过意图辨认的方式路由到子数据库。
这个方法只能常数级别缓解，但是也是须要的。
k-means

你使用聚类算法，或几十个embedding为一组，或几百个embedding为一组，求组内的mean embedding来代表这一个组，那么你能以更大的常数级别削减你所要检索的embedding数量。你找到了top-k最相似的组，就再从这些组里面细化地检索最相似向量。
位置敏感hash(LSH)

这是一种聚类方法的变体。之所以用它，我觉得是因为聚类方法要提前设定聚类数量， 而且要迭代很多次，盘算起来很耗时。
LSH是一种期望将位置相近的向量映射到相近编码空间上的方法。举一个简单的例子，我假如在平面上随机地画128个超平面，并让每个超平面的上侧embedding计为1，下侧为0，就这样为每个embedding编码出128位0-1编码，那么来了一个查询embedding，它同样有个编码，我自然以为与其编码类似的那一批embedding是与其近来的。那么我会提前把每个01编码看作一个bucket，里面存的都是编码类似的embedding，用的时间直接查找拿bucket就行，然后再细查。
LSH改良

由于随机画超平面来做01编码的方法存在随机性，会出现“明明相近，但被超平面分开”的偶合。这无法避免，但可以缓解。一般来说，会通太过割embedding的方式做到。例如embedding dim为1024，我会把它切成8段，每一段都单独土地算LSH，就有了8个桶集合。我查询的时间，把自己也分成8段，去找对应的集合里面编码类似的桶，找出8个子集。显然，这种方法能够大大缓解由一次LSH导致的偶合。
k-measn改良（积量化PQ）

k-means也会有题目，你的embedding空间太大了，k设几十万都不够。如何解决？也是分割embedding。1024的embedding维度，我分成64段，每段16维，那么可能每段只需要k=256就够聚类了。然后我就有了一个64个值、每个值值域为1～256的序列，用于表示一个1024的embedding在每个子空间里聚类的环境。这不光是从1024->64维的降维，每个单元也从float32的32位降到了256的8位。
导航小世界NSW

这是基于图布局的导航搜索算法。
假设我们已经为离散的点基于某种方法（例如k-means，德劳内三角剖分法）构建了一个拓扑图，那么我们可以通过一个未经理论证明的猜想“6人猜想：恣意两个人，只需要6个中间人，就可以形成关系”实现快速搜索。
该算法这样搞：对于一个查询向量S，随机一个图数据库中的embedding A为起始点，然后探求A的邻人，找到其中与S相似度最高的B，B再找其邻人，再与S算相似度…这样能快速找到最相近的节点。
分层导航小世界HNSW

实在NSW还不够快，一步步挪太慢了。之所以一步步挪，是因为我们构建拓扑图时，就是这么构建的。而且我们可以直观地想到，在从A开始时，你完全不必纠结于步子太大，只要最后够小就行。
那如何构建一个有长隔断拓扑关系的图呢？指数衰减概率分布可以用来指导一个新加入的embedding是否应该一次次地出现在更高、更粗糙拓扑图上的概率。
假如我要搞6层分层，0为最底层，1～6为导航层，新加入的点A一定会出现在0层，然后在0层使用德劳内三角法构建拓扑。A以指数衰减概率抛硬币，判定其是否出现在1层，出现，则在1层加入A，然后用德劳内三角。就这样一直往上。
？题目：每一层构建拓扑时，要求每个新增节点要与至少M个近邻节点连接，这本质上也是一次搜索，这要怎么做？

我觉得HNSW前期应使用德劳内三角，后期由于每一层节点已经不少了，直接用其自己的方法导航找到近来的K个就行。
最小天生树算法

构建拓扑确实很难，所以想了很多方法。最小天生树算法是一种图论算法，从某个节点出发，每次添加的节点都要求与已有节点的隔断最小。这种方法不像k-nn只围着自己一圈形成菊花状局部拓扑。
实际应用时，仍旧是靠HNSW自己找k个相近节点，然后构建一个全连接子图，在这上面找出一个最小天生树。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。