文献分享: DiskANN查询算法的复杂度下界

文章目录

• 0. 写在前面
• • 0.1. 预备知识
  • 0.2. 一些记号
  • 0.3. 本文的研究概述
• 1. DiskANN \text{DiskANN} DiskANN回顾
• • 1.0. Intro
  • 1.1. DiskANN \text{DiskANN} DiskANN的基本操作
  • 1.2. DiskANN \text{DiskANN} DiskANN的构建操作
• 2. 对于慢处理 DiskANN \text{DiskANN} DiskANN的理论分析
• • 2.1. 预处理分析
  • 2.2. 查询分析
  • 2.3. 对复杂度的紧致性分析
• 3. 对于快处理 DiskANN \text{DiskANN} DiskANN(及其他算法)的实验
• • 3.1. 快处理 DiskANN \text{DiskANN} DiskANN的实验
  • 3.2. NSG/HNSW \text{NSG/HNSW} NSG/HNSW算法的实验
  • 3.3. 交叉对比
  • 3.4. 其它算法上的实验

0. 写在前面

0.1. 预备知识

1️⃣最邻近搜索：给定数据库 U U U中的 n n n个对象(子集)，以及输入的查询点 q q q

1. 精确定义( NN \text{NN} NN)：返回 e ∗ ∈ S e^*\in{S} e∗∈S满足 dist ( q , e ∗ ) = min ⁡ e ∈ S dist ( q , e ) \text{dist}(q, e^*) = \min\limits_{e \in S} \text{dist}(q, e) dist(q,e∗)=e∈Smin​dist(q,e)
2. 近似定义( c-ANN \text{c-ANN} c-ANN)：返回 e ∈ S e\in{S} e∈S满足 dist ( q , e ) ≤ c ∗ dist ( q , e ∗ ) \text{dist}(q, e)\leq{}c*\text{dist}(q, e^*) dist(q,e)≤c∗dist(q,e∗)

2️⃣倍增维度

1. 直径：点集中距离最远的两点的距离，即 diam ( X ) = sup ⁡ e 1 , e 2 ∈ X dist ( e 1 , e 2 ) \text{diam}(X)=\displaystyle\sup_{e_1, e_2 \in X} \text{dist}\left(e_1, e_2\right) diam(X)=e1​,e2​∈Xsup​dist(e1​,e2​)
2. 2 λ - 2^{\lambda}\text{-} 2λ-分割： X X X可被分为 m m m个子集 X 1 X 2 . . . X m X_1X_2...X_m X1​X2​...Xm​，且满足 { m ≤ 2 λ diam ( X i ) ≤ 1 2 diam ( X ) \begin{cases}m\leq{}2^{\lambda}\\\\\text{diam}(X_i)\leq{}\cfrac{1}{2}\text{diam}(X)\end{cases} ⎩ ⎨ ⎧​m≤2λdiam(Xi​)≤21​diam(X)​
3. 倍增维度：就是 λ m i n \lambda_{min} λmin​，即用最少 2 λ m i n 2^{\lambda_{min}} 2λmin​个半径不超过 1 2 r X \cfrac{1}{2}r_{_X} 21​rX​​的球体填满 X X X

3️⃣球体的一个性质：任何球体 B ( e , r ) B(e, r) B(e,r) 都可被至多 O ( k d ) O\left(k^d\right) O(kd) 个半径为 r c \cfrac{r}{c} cr​ 的球体覆盖

0.2. 一些记号

符号	含义
( X , D ) (X, D) (X,D)	基础度量空间， X X X为点集 D D D为距离类型
D ( u , v ) D(u, v) D(u,v)	P = { x 1 , … , x n } P = \{x_1, \ldots, x_n\} P={x1​,…,xn​}中的俩点 x u x_u xu​和 x v x_v xv​的距离
B ( p , r ) B(p, r) B(p,r)	以 p ∈ X p \in X p∈X为球心 r r r为半径的球
Δ \Delta Δ	点集中最远俩点 / 最近俩点的比值
d d d	倍增维度

0.3. 本文的研究概述

1️⃣背景：很多 c-ANN \text{c-ANN} c-ANN算法比如 HNSW/NSG/DiskANN \text{HNSW/NSG/DiskANN} HNSW/NSG/DiskANN在基准数据集上性能不错，但其下界不可知

2️⃣研究成果

1. 最坏情况上界：对于 DiskANN \text{DiskANN} DiskANN慢处理版，可在 O ( log ⁡ α Δ ( α − 1 ) ϵ ) O\left(\log _\alpha \cfrac{\Delta}{(\alpha-1) \epsilon}\right) O(logα​(α−1)ϵΔ​)步返回 ( α + 1 α − 1 + ϵ ) -ANN \left(\cfrac{\alpha+1}{\alpha-1}+\epsilon\right)\text{-ANN} (α−1α+1​+ϵ)-ANN
   • 但值得注意， DiskANN \text{DiskANN} DiskANN慢处理的图构建复杂度高达 O ( n 3 ) O(n^3) O(n3)
2. 最坏情况下界：对于 DiskANN \text{DiskANN} DiskANN块预处理版/ HNSW \text{HNSW} HNSW/ NSG \text{NSG} NSG，算法找到 5 5 5个最邻近前至少要走 0.1 n 0.1n 0.1n步

3️⃣未来的研究方向：有没有一种算法，预处理和查询都低于线性复杂度 ? ? ?

1. DiskANN \text{DiskANN} DiskANN回顾

1.0. Intro

标签：log,DiskANN,0.1,text,复杂度,下界,alpha,ANN
From： https://blog.csdn.net/qq_64091900/article/details/141144031