先容一点metric self-join和复合索引条记

metric self-join

The self-similarity join in metric spaces
对于给定的一组数据                               D                      ⊆                      U                          D\subseteq U               D⊆U，self-simility join                               D                               ⋈                         s                              D                          D\bowtie_s D               D⋈s​D 界说为找到全部数据对                               (                      x                      ,                      y                      )                      ,                      x                      ,                      y                      ∈                      D                      ,                      x                      ≠                      y                          (x,y) ,x,y\in D,x\neq y               (x,y),x,y∈D,x=y，而且在相似性判断条件下                               x                      ,                      y                          x,y               x,y 是相似的。
它是一种数据发掘和数据库范畴的技能，用于在数据会合找到全部满足特定相似性度量的对象对。它的提出是为了优化数据分析中的相似性查询，尤其是在低维度数据中。这种技能在很多算法中作为子步伐利用，比方 DBSCAN 聚类算法和时间序列数据分析。
metric self-join 的效果为 KNN 图的构建提供了根本。两者的重要区别在于 metric self-join 关心的是满足相似性条件的全部点对，而 KNN 图进一步限定了只生存近来的 k 个邻人，以是说这两者在某种水平上等同，以是SISAP 2025寻衅中提到KNN图构建（大概说metric self-join）
提一点有关ANN的说法

参考自向量索引算法HNSW和NSG的比力，即为什么要研究图上算法
如今常用的索引范例以及它们的范围性。
起首是基于树的算法，这里举例较为经典的 KD-tree 。这种索引范例在向量维度稍大一些的情况下 (d>10) ，索引性能会急剧降落乃至不如暴力搜索。再说说基于 LSH (locality-sensitive hashing) 的索引，如果想要取得高召回率， LSH 算法必须要创建大量的 Hash 表，这会使得索引巨细膨胀数倍。
不光云云，树和 LSH 都属于空间切分类算法，此类算法有一个无法制止的缺陷，即为了进步搜索精度，只能增大搜索空间。图 1-A 形貌了基于树的切分搜索，每个虚线分割出的地区是一个子树，如果搜索向量在子树的边沿时，算法须要搜索多个子树来获取效果。图 1-B 形貌了基于 Hash 的切分搜索，虚线形貌了每个独立的hash表，搜索面对的题目与基于树的搜索算法类似。以是空间切分类算法在最坏的情况下须要扫描险些整个数据集，这在很多场景下显然是无法继承的。

由于图数据布局有天生近邻关系的特性，在图上做近来邻搜索看来是一种不错的思绪，以是比年来基于图的向量搜索算法也是一个研究热门。
文中还具体阐明确HNSW和NSG的差别，这里放上他的总结：
HNSW 从布局入手，利用分层图进步图的导航性镌汰无效盘算从而低沉搜索时间，到达优化的目标。而 NSG 选择将图的团体度数控制在尽大概小的情况下，进步导航性，收缩搜索路径来进步搜索服从。
HNSW 由于多层图的布局以及连边计谋，导致搜索时内存占用量会大于 NSG，在内存受限场景下选择 NSG 会更好。
但是 NSG 在建图过程中无论内存占用照旧耗时都大于 HNSW。
别的 HNSW 还拥有如今 NSG 不支持的特性，即增量索引，固然耗时巨大。
对比其他的索引范例，无论 NSG 照旧 HNSW 在搜索时间和精度两个方面，都有巨大上风。
复合索引布局

重要参考Faiss: The Missing Manual中的内容
A composite index is built from any combination of:

• Vector transform — a pre-processing step applied to vectors before indexing (PCA, OPQ).
  
• Coarse quantizer — rough organization of vectors to sub-domains (for restricting search scope, includes IVF, IMI, and HNSW).
  
• Fine quantizer — a finer compression of vectors into smaller domains (for compressing index size, such as PQ).
  
• Refinement — a final step at search-time which re-orders results using distance calculations on the original flat vectors. Alternatively, another index (non-flat) index can be used.
  

Note that coarse quantization refers to the ‘clustering’ of vectors (such as inverted indexing with IVF). By using coarse quantization, we enable non-exhaustive search by limiting the search scope.
Fine quantization describes the compression of vectors into codes (as with PQ) . The purpose of this is to reduce the memory usage of the index.

盛行的复合布局

IVFADC

IVFADC的焦点是IVF256和PQ32这两个索引的组合。
该索引方法于2010年与乘积量化一起提出[H. Jégou, et al.,Product quantization for nearest neighbor search(2010),TPAMI]。从其时起，它不绝是最受接待的索引之一——它有着公道的召回率、很快的速率和超低的内存利用量。但是，它的缺点是召回性能比力一样平常，只能说还说得已往。
利用IVFADC举行索引有两个步调：

• 向量被分配到IVF布局中的差别列表（或沃罗诺伊Voronoi分区。沃罗诺伊图基于一组特定点将平面分割成差别地区，而每一地区又仅包罗唯一的特定点，而且该地区内恣意位置到该特定点的间隔比到别的的特定点都要更近）。
  
• 向量利用 PQ 举行压缩。
  

索引向量后，在查询向量 xq 和我们的索引量化向量之间实行非对称间隔盘算 （Asymmetric Distance Computation：ADC）
之以是被称为非对称搜索，是由于它将未压缩的 xq 与索引中被压缩的 PQ 向量举行比力。与之相反，SDC是将查询向量xq先辈行压缩量化，再去已经压缩的索引中比对。
（实在就是我在PQ条记中提到的在的查询到来时的两种间隔盘算方式，SDC就是方式一，ADC就是方式二）
Multi-D-ADC

Multi-D-ADC是指多维（multi-dimention）索引+PQ算法，PQ在搜索时举行不对称的间隔盘算（ADC，见前面）。[A. Babenko, V. Lempitsky,The Inverted Multi-Index(2012),CVPR]
多维ADC索引基于倒排多索引（IMI），它是IVF的一种变体。IMI在召回和搜索速率方面都优于IVF，但增长了内存利用量。以是当IVF+ADC方法在召回和速率上差能人意时，可以利用IMI索引（如多D-ADC），而且（在有些情况下）还可以节省更多的内存利用。IMI索引的工作方式与IVF非常相似，但Voronoi图是在向量的一些子维度上举行分区。这产生的类似于多级Voronoi分区布局。

在引入HNSW之前，效果最优的方法是加了OPQ预处理处罚的Multi-D-ADC方法：“OPQ32,IMI2x8,PQ32”

引入HNSW后

先容一下OPQ

OPQ是在PQ的根本上进一步优化的一种技能，它通过对向量举行旋厘革换，将分布不匀称的数据重新调解，使其在各个子向量维度上更匀称。这种预处理处罚使量化后的数据更加高效。
工作流程：

• 利用旋转矩阵对原始向量举行变更，使其分布更匀称。
  
• 再利用PQ对变更后的向量举行量化。
  

上风：提升召回率，特殊是在向量数据分布不匀称时效果显着。
缺点：额外的旋转盘算大概会增长少量处理处罚时间。
旋厘革换的作用

在产物量化（PQ）中，向量会被分割为多个子向量，并分别举行量化。然而，如果原始向量数据分布不匀称，各个子向量之间大概存在显着的差别，导致量化毛病较大。旋厘革换（通过旋转矩阵）可以对向量的团体分布举行调解，将分布不均的特性“平滑”化，使每个子向量的分布更加匀称。
通过这种优化，可以有效低沉量化毛病，从而进步召回率和检索精度。
旋厘革换的具体实现

OPQ的旋厘革换采取一个优化的旋转矩阵举行盘算，该过程包罗以下步调：

• 练习旋转矩阵：通过利用样本数据来学习最佳旋转矩阵。该矩阵的操持目标是最小化量化毛病。
  
• 应用旋转矩阵：对全部输入向量举行线性变更，通过矩阵乘法将输入向量映射到新的空间。
  
• 子向量分割：在变更后的空间中，将向量分割为多个子向量，以准备后续的产物量化步调。
  

公式表达：                                    y                         =                         R                         ⋅                         x                               \mathbf{y} = \mathbf{R} \cdot \mathbf{x}                   y=R⋅x 此中：𝑥是原始向量，𝑅是旋转矩阵，𝑦是旋转后的向量。
为什么旋厘革换能平滑分布？

旋厘革换的理论根原泉源于线性代数。简朴来说：

• 重新分配特性相干性：旋转矩阵通过对原始向量举行正交变更，可以将原来高度相干的维度解耦，使它们在差别子向量中分布得更匀称。
  
• 优化全局特性分布：这种重新分列可以将某些维度的过分厘革“扩散”到整个向量中，从而制止单一子向量负担过多的信息。
  

旋厘革换是否有效，依赖于数据分布。如果数据的原始分布已经非常匀称（比方尺度正态分布），旋转的收益大概有限。但对于那些在某些维度上分布不均的数据集（如高维奇怪数据），旋转可以显着改善量化性能，进而提升检索精度。
与PCA末了操纵（类旋转）的比力

PCA的末了一步数据投影与旋转：将原始数据投影到由特性向量界说的新坐标系中。这一步可以看作是对数据的旋转，由于数据从原始空间转移到了主身分空间。
公式表现为：                                    Y                         =                         X                         ⋅                         P                               \mathbf{Y} = \mathbf{X} \cdot \mathbf{P}                   Y=X⋅P 此中：𝑋 是原始数据矩阵，𝑃 是包罗特性向量的矩阵（旋转矩阵），𝑌 是转换后的数据矩阵。
注意这里是右乘
PCA末了的旋转：

• 目标是低沉数据维度，同时生存最大方差方向上的信息。
  
• 数据的旋转是为了找到新的坐标系，使数据尽大概会合在少数几个维度上。
  
• 
  

OPQ事先的旋转：

• 目标是优化子向量分布，使得产物量化（PQ）效果更好。
  
• 数据的旋转是为了将数据的分布“平滑化”，使得子向量的分布更加匀称。
  

矩阵左乘和右乘的差别

• 操纵对象差别：
  

• 左乘作用于列向量，通常用于坐标系变更。
  
• 右乘作用于行向量，通常用于操纵向量数据。
  

• 意义差别：
  

• 左乘的效果是向量在新坐标系中的表现。
  
• 右乘的效果是向量数据自己的重新分布或操纵。
  

• 实用场景：
  

• 左乘用于图形变更、物体旋转等场景。
  
• 右乘用于矩阵叠加、数据处理处罚等场景。