https://blog.csdn.net/Datawhale/article/details/134453533

1. Intro

非结构化数据压成 \(D\) 维向量

五个问题：

• 模糊搜索标准：向量不太适应模糊语义查询
• 更多代价：\(O(D)\)
• 内存消耗大：全要访问
• 缺乏结构：(有结构的可以排序啥的 index 她不行)
• 和属性不兼容（不太明白，可能是别的可以直接球是不是答案，比如这个 top k 是一个堆还得一个一个比？

评估

精确度 Precision： 相关结果 / 所有解（答案里面有多少对的）
召回率 Recall：（所有相关的里面有多少被发现出来了）
延迟 (Latency)
吞吐量 (Throughput)

Cases

读入难 (read-heavy, 例如：LLM-based？): 需要高吞吐，低延迟(?)
写入难 (write-heavy, e-commerce)：高写作吞吐量, 交易分割和数据一致(?) (transaction isolation requirements and data consistency)

基于云 (cloud-based)：Zilliz, Weaviate [1], Pinecone 提高高扩展性、弹性、可用性、容错性
(Zilliz: 语义缓存，送到 chatbox 前用 VDBMs 提前 check 减少高花费)

2. 查询处理

相似性得分

• 多向量搜索 组合（？
• S/M（有多个向量？） Q [查询] （实体是否多个向量）S/M F [特征]

Sol

• 收集索引向量困难：随机 / 划分 / 导航 (navigable)
• 存储大小大：量化 (quantization)

操作符 (Operator)

抽象定义，没理解

• 向量操作符：数据修改插入删除向量 ..
• 搜索操作符：投影（复杂度有点高了）

搜索算法

用优化器 (optimizer) 自动选算法 / 手动选

分数选择

单位长度 -> cos = dot，欧几里得距离也相对应
EuclidesDB：多个嵌入模型，最语义相关
SeeSaw：交互增强

分数设计

可以用 Mahalanobis （马氏距离，没理解公式，未知样本球状分布的近似？）度量学习
\(D>10\)，IID (维度独立切同分布) 最近最远 cos 和欧几里得也近似相等（？不太明白）
现实生活数据本质低维，也有用曼哈顿和切比雪夫距离去恢复可辨性（不太知道为啥能恢复）

3. 索引

数据分区技术

• 随机：概率放大，增加区分？
• 学习分区
• 可导航（图，方便穿梭

存储和索引

• 量化 压缩信息（最小化信息损失） 最小化存储成本
• 磁盘驻留（最小化 I/O 检索次数

表 (Table)

方便更新

• 随机：LSH，受欢迎，稳定的错误边界
  都是搞个桶，也可以看成分块 （分类）。。

局部敏感哈希 LSH (Locality sensitive hasing)

可能需要高冗余性提高准确度

1. 有四个参数 \(r_1, r_2, p_1, p_2\)
2. 满足距离 \(\le r_1\) 在一个桶 (哈希函数相同)里概率 \(\ge p_1\)
3. 距离 \(\ge r_2\) 时在一概率 \(\le p_2\)
   有这个保证的函数构成哈希函数族
   多个函数并起来都一样的才在一个桶里

• 有 \(K = \lceil{\log_{1/p_2}N}\rceil\) 个大值域（\(U^K\)）
• \(L = O(1/p_1^K)\) 个哈希函数扩充成
  ![[Pasted image 20240912234608.png]]
  不明白，但好像构建的复杂度也不是瓶颈，而且这里也是看表现调参吧。。反正是一个类似密度的东西，可以保证每个桶大概是 \(N^{\rho}\) 个东西，所以查询复杂度是 \(O(DN^{\rho})\)
  最好是 \(r_1=距离查询点的最小值, cr_1 = r_2\)，这样相对最小值
• 每个查询的候选者集合都不一样，精确度和召回率很低（逻辑？？）尝试扩展搜索用 Multi-probe LSH

1. \(E^2LSH\) 投影随机超平面 \(\rho < 1/c\)
2. \(IndexLSH\) 二进制投影
3. \(FALCONN\) 球体LSH （投影到球上然后分裂到更小的球 \(\rho = 1/(2c^2-1)\)

学习哈希 L2H (Learning to hash)

• spectral hashing 光谱哈希 近似矩阵 神经网络？
• SPANN：用 k-means，磁盘驻留，最小化 I/O，key 在内存，分层桶调整大小，邻域规则减少 I/O （玄幻）

Quantization 量化

Product quantization 乘积量化

比如你要分成 \(K\) 类，直接做每次迭代是 \(O(DNK)\) 的
可以把 \(D\) 平均分成 \(m\)，那每一个维度找 \(K^{1/m}\) 哥重心就可以了

![[Pasted image 20240913014003.png]]
真的不能要了，i和j都搞不清楚

然后再撑起来。每轮复杂度是 \(O(DNK^{1/m})\)？（他写错了？
![[Pasted image 20240913013902.png]]

这里 i 应该删掉，写错了。
不同的压缩方法：OPQ (Optimized PQ)、hierarchical quantizers、anisotropic quantizers

举例

• Faiss：很多 "flat" 索引，向量对应压缩版本，没桶？
• SQ (standard quantizer)：位级别压缩
• IVFSQ 用 SQ 然后帮到最近重心的桶里
• IVFADC：先用桶 kmeans 然后 PQ 压缩，减掉桶重心用余数向量再迅雷量化器 (quantizer?)，查询 q 没有被量化，比较用的是 ADC ("asymmetric distance computation") （可以预处理一些东西）
• ADBV：桶分成更小的桶（就是树结构啊，或者块分块）VGPQ（Voronoi Graph Product Quantization"）

树 (Tree)

\(\log\) 结构
就是和之前看的是一样的划分下去
自然的想法基于距离划分：

• 基于枢纽 (?) pivot-based trees：VP-tree, M-tree, k-means tree, 基于深度学习
• \(D\) 太大一般基于随机，（例如 1. FLANN，用 PCA 结合随机和学习划分 2. ANNOY 类似于 RPTree 随机投影树 ）
• 许多树可以做到确切的结果（exact），不高效，有一个策略叫 defeatist search (击败主义搜索)（树被遍历到叶级别，覆盖 q 的叶内（为啥叶子里还有向量）的所有向量立即返回为最近邻。虽然击败者搜索不能保证准确的结果，但没有回溯，复杂度是 \(O(D \log n)\) 完全没明白）
• 都是依赖数据的，对着卡肯定平衡不了（？(far there are no methods for rebalancing nodes after a number of out-of-distribution updates.? 为什么不能 fhq-treap一样每次随一下肯定是平衡的呀（？)

非随机树

K-D Tree 分中位数

随机树

PCA 主成分分析 (Principal Component Trees)：旋转角度 (提前找到让坐标轴和主维度对齐？)

• PKD-tree 每次旋转找平面 FLANN 沿着主切
• RPT 随机投影可以适应找主要/本质维度(不用代价高昂的PCA)，下一个随机扰动切平面（这个我之前想到过，很自然，肯定被做了。。

图 (Graph)

表现好，不好解释
随机生成基于

• HNSW：方便构造更新 许多商业支持（问题：存储成本）

• MSNs (monotonic search networks) / HNSW：高导航型。。
  前者倾向于依赖搜索试验，后者用启发式过程 one - shot refine

• KNNG：k 个最近（类似 k means 的迭代增强） 批量查询）

  • \(Exact\): \(O(N^{2-\epsilon})\)
  • 迭代增强：
    1. KGraph (NN-Descent)：找邻居的邻居
    2. EFANNA: k-d tree 随机森林生成初始 KNNG，在线查询

单调搜索网络 (MSNs)

增加一些边联通，搜索单调路径指的是访问的点距离查询越来越小。
"best-first" 搜索探索到这种路径，每次选最近的，肯定单调。图的性质保证有边。复杂度是路径上所有出度的和。Delaunay三角剖分，需要 \(\omega(N^{\lceil D/2 \rceil})\) 时间。早期用 RNG 构建

搜索试验探测图的质量，加入新边。每次找一条路找path更新。

random (随机 pair) and fixed trials
Fixed Trial: 固定试验构造，找一个导航节点，查询也这样。
（感觉基本都是 \(O(N^{\epsilon})\) 跟没说一样）
NSG (Navigating Speading-Out Graph) 从近似 KNNG 开始，生成树连接。
Vamana 随机图而不是 KNNG，不 check lune membership 了

• DiskANN 磁盘驻留：kmeans划分，Vamana idex，PQ 二合一（压缩 beam search ....

小世界图 (Small world graphs)

小世界图：特征路径以 \(O(\log n)\) 增长
可导航图：best 搜索路径是 \(\log n\) 级别
构造： one-shot refine
恢复 \(\log\) 搜索，限制出度借机（没有太理解

Discussion

• Batched: KNNGs
• LSH Based / RPTree：错误保证
• SPANN / MANN：基于磁盘索引
• Table：write heavy
• 树 / 图：read heavy
  混合结构：NGT

索引设计

事物隔离 (transaction isolation)
system level / storage level.
Open problem:

• Faiss实现许多向量索引，不支持并发更新
• 很多动态 collection 不行

4. 查询优化

查询计划表示为操作符的 DAG，选择最优的计划，最小化延迟（花费时间）。
主要限制于谓词 (predicated) 查询（因为非谓词太简单？）

计划枚举 - 计划选择

混合操作符

谓词查询 过滤？

预过滤：

blockfirst scan works by "blocking" out vectors in the index before the scan is conducted
Blocking 阻塞（就是剪枝去掉一些？），谓词提前知道可以离线（？

ADBV & Milvus: 状压 bitmask check
Milvus：预先分区，去那找

Graph

避免不联通：

• Filtered-DiskANN ：技巧性的加一些边（属性分类）
• HNSW：范围窗口，找到相交（离线决定好，sort 按顺序放进去）？In [145], each edge of an HNSW index is labeled with a range window so that vectors which obey a one or two-sided range intersecting the window can be found by traversing the edge. These labels are determined offline by sorting the dataset beforehand and then inserting vectors into an HNSW in sorted order. The use of sorted insertion prevents disconnections.

单级过滤（single-stage filtering）

visit-first scan 一遍扫一遍查

• low-selectivity predicates（低选择性谓词）（？直接扫比block快？（就是你block比较难block？
• 高选择性，如果用容易连续回溯？（避免，加入属性机制进行遍历
  best-first search operator，属性增强边遍历？

后过滤（post-filter）

计划枚举

少量运算符 - 预定义有效 - 关系代数 relational algebra （允许自动枚举
Predefined :

• 单（特定，不用选择，非谓词查询 [一个方法]） / 多计划 （多索引，多方法，例如 VGPQ 支持暴力和表）
• 自动枚举（Automatic Extended）：自动优化扩展 pgvector [7] 和 PASE [136]

计划选择

• handcrafted rules：人工规则，自己 if 分类讨论，阈值：Qdrant, Yahoo Vespa
• cost model：[ADBV and Milvus] 操作符（操作次数，去 memory disk 里找的。离线？

讨论

谓词查询

• Cost Estimation：不确定会 block 几个 (tree / graph) 会导致
  1. post-filtering 会导致结果 < k？（最后再清算都扫一遍么.....（通过找 \(\alpha k\) 个来缓解问题。。很笨感觉
• Operator Design：设计高效的算子？。。就是设计算法呗。。。

查询执行 (Query Execution)

云服务：分解架构？？disaggregated architectures -> 高弹性 -> 硬件加速
怎么进行（算法？）
奇怪的加速（硬件，搞不懂）

• HNSW，删除打标记而不是改变结构（tombstoning）

数据操作

• Milvus， LSM 树 替罪羊
• Manu 切片 / 太多就合并、bitmap 防止删除干扰
• Vald: NGT,
• ADBV 分布式

分布式查询处理

• 跨节点划分向量
• 保持数据一致性
• 支持分布式搜索

划分

• 属性，区分键
• ADBV：结构化属性 指定属性
• Vald：增量加向量
• 搜索结构：WAL，LSM，HNSW
• A quorumbased mechanism is used to maintain consistency [48].
• Vearch - HNSW 阈值

一致性

不太明白一致性是啥。。（？？
一致和可用 (availability) 的balance

• Weaviate 复制分片可用性，复制品 WAL + LSM + HNSW 完全并入正确结构才让写入
• Vespa 等副本确认
• quorumbased 仲裁机制
• Manu delta 一致性 时间不到不让跑？？？

分布式搜索

想略过了，不懂分布式太难了（他也略过）就是分开搞完独立的合并答案

硬件加速

（也想略过，没明白）

• Milvus 划分查询足够小 < CPU Cache
• SIMD 一系列 难以加速 并行？shuffle 添加
• GPU ... ADC Faiss. Wrap shuffle

LSM Tree

不行了就暴力重构

搜索引擎 / 库

• Apache Lucene 可插入 （HNSW）
• KGraph，LSH
• Applureform 数据集管理中间部件

现存系统

Native

专业化

* Mostly vector：

• Vald 非谓词 多个代理 近似搜索
• Vearch 近似搜索 基于图像
• Pinecone 扩展分布式

Most Mixed

• optimizer
• Milvus 全面
• Manu 附加特征（base Milvus
• Qdrant ：HNSW 告诉
• NucliaDB & Marqo 文档搜索
• Weaviate 图 文档搜索 基于仲裁

扩展

• NoSQL 很像 native？？
  • Vespa 可扩展分布式 / 灵活 SQL 查询
  • Cassandra
  • Spark-based Databricks
  • 除了 document 还有别的 如 Neo4j Graph 仅 ANN

Rational

extended relational systems 系统固有能力？
PASE / pgvector

Libraries and other systems

Apache Lucene
Libraries:

• KGraph
• SPTAG)

Benchmark

ANN Benchmark
Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement

挑战 Open Problem

• 分数选择 设计
• 索引设计
• 谓词查询
• 运算符设计（算法？
• 增量搜索（k实际大
• 多向量
• 安全和隐私

总结

1. 读了两遍论文，花的时间很长，但还是抓不清楚主次，很多东西很模糊*
2. 笔记比较混乱，看完很多细节都忘了，但看笔记也想不起来是啥
3. 感觉这篇文章也比较乱，举例子一遍一遍的举，结果也没明白每个的特点是啥，而且很多细节都是浅尝辄止，也不知道具体是啥，比如 HNSW ....