向量数据库|第2期|pgvectorscale.docx
5墨值下载
向量数据库
第
期
大家都听说过
，一个
存储和查询向量的扩展，是
生态当之无愧的
最受推崇的工具之一。
向
中添加了
类型，以及各种搜索操作符和索引，
使其拥有
和
的完整数据库能力。但他的
索引有两个问题：
）需要将整个索引都放到内存，否则会变慢。索引成为整个应用的唯一瓶颈
）基于
索引的
不能以一种合理的方式充分利用预过滤。利用
查询
向量首先需要进行索引查询、获取结果，然后才能进行过滤。更为糟糕的是 ，
仅能从
中返回最大结果集（大多数情况下小于
，否则会变得很
慢）。假设你有一个多租户应用，维护数千支
，每一个有数千个文本（或向
量）。针对你的查询请求，
会查询所有
，返回一个有限数量的结果集，
然后在此结果集上执行过滤。如果最佳结果位于不相干
中时，无法保证为你
的
找到任何向量。
pgvectorscale
（
Rust
语言开发的）添加了基于磁盘的流索引，可以解决这两个问题。准确
的说，它添加了微软
!
论文中提到的
StreamingDiskANN
，一种图结构的专门用于过
滤的近邻查询的索引。
的三大特性：支持
!
索引（算法）、支持
"#$ "
、支持
%
（
&&' "()*"&+&"
）。
1
、
DiskANN
算法
!
算法和
类似也是一种基于图的查询算法。基于图的算法有一个问题：查找
一个距离
&"
非常远的点非常耗时，因为它需要大量
。
通过引入一个分层系统（顶层仅有“
"#",
边，即高速公路边，帮助快速进入正
确的区域，并且有指向低层节点的指针允许以更细粒度的遍历图）。该方法虽然解决了
"#"
问题，但通过分层系统引入了更多的
" &"
，需要更多随机访问，从而需要
将该图放到
-.
中以获得更好的性能。
与此相反，
!
使用单层图，在图构建时通过引用远距离的邻居边来解决
"#"
问
题。单层构建简化了算法，并且在查询时减少了不必要的随机访问，使得
更加高效。
相对于
来说，它从一个随机图开始，他的核心是一个名为
/"
的图
算法，
即构建图的算法为：
）随机初始化一个出度为
-
的图
：每个节点随机选择
-
数量的邻居节点并建立连接
）计算图
的导航点，也就是近似质心
0
）以距离全局质心最近的点作为搜索算法起始节点，为每个点重新选择近邻
1
）基于步骤
初始化的随机近邻图和步骤
0
确定的起始点，对每个点做
(
即贪婪搜索，将搜索路径上的所有点都放到近邻集。这里需要跳到
2
和
2
部分
了解如何选择候选邻居集。
3
）执行步骤
0
）和
1
）两遍，第一遍
α=1
，第二遍
α>=1
。
其实是，在随机图基础上，从质心开始遍历两遍重新生成新图。
如何体现
Disk4
对于索引构建的问题，
!
在构建索引时通过
!#"
聚类的方式将整个数据集划分
成
!
个簇，然后将每个节点分配到最近的
个簇中，每个簇分别构建
/"
图，这样就可
以在内存中进行索引的构建，最后通过简单的边并集将所有不同的图合并为一个图。
1.1
如何选择近邻？
现有的一些近邻图算法选边策略：如上图给绿色点选择邻居，假设要给它选择两个邻居，
从构建一个精确的近邻图角度来看，一定是选择离绿色点最近的两个点（点
和点
）。
这样得到的图精确了，但是可能造成邻居集中在一块的现象，不能在各个方向均匀分布。
!
论文中提出，一个精确的近邻不并不一定是最合适的
。
因此可以通过连接远距离的点来构建近邻图：先将距离绿色点最近的点
选中（加入绿色
点的近邻集），然后对点
进行判断：
56786
绿点
7
则不将点
加入绿色点的近邻集。
其中
表示两点的距离。依次对
0
及左下角的其他点进行判断（顺序是离旅店由近到远），
最后判断点
1
，
617961
绿点
7
，所以将
1
加入绿点的近邻集。
这种方法比较激进，会删除很多长边。
1.2
如何调整，再增加一些长边？
一种极端情况下，数据集中的点都在一条线上，如上图。如此按照
2
进行选边时，每个
点只能和离它最近的两个点相连。这样执行
时，会导致平均跳数很高，如果配合外
村执行搜索，可能会导致多次磁盘
:
。
距离
'
最近，将
加入
'
的近邻；接着判断
，
6796'7
，
加入
'
的近邻；直线上的其他点就如同被
和
屏蔽掉一样，不和
'
相
连了，因为
6
其他
786'
其他
7
或者
6
其他
786
其他
7
。
/"
对此进行了调整，增加一个参数
α
：
α*d(a
或者
c
，其他
)>d(b,
其他
)
，通过调整
α
值，从而增加一些长边。
of 5
5墨值下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论