由于 AI 与机器学习的加速发展，现如今矢量资料库已无所不在。虽然矢量搜索能支持繁杂的 AI 或机器学习插件，但这个基本概念本身并无从。在文档中，他们来一起看看矢量资料库的工作基本原理，并采用不到 200 行 Rust 标识符构筑两个简单的矢量搜寻库。
GitHub 完备的标识符：https://github.com/fennel-ai/fann/?ref=fennel.ai
责任编辑采用的方法如前所述盛行库 annoy 中采用的一类名为“Locality Sensitive Hashing”（局部性脆弱基元，LSH）的系列产品演算法。责任编辑的目的不是如是说一类绝妙的演算法或库，而是撷取什么样撰写两个矢量搜寻。
在写标识符之前，首先他们来如是说一下什么是矢量搜寻。
矢量（又称内嵌）如是说他们极难采用传统的数据库则表示和查阅文件格式、影像、音频等繁杂的非形式化统计数据，尤其是无法搜寻“相近”统计数据。那么，YouTube 又是什么样优先选择下两个播映音频的呢？Spotify 又是什么样根据当前曲目自订快照的呢？
2010 年代 AI 的不断进步（从 Word2Vec 和 GloVe 开始）使他们能构筑那些第一类的语法则表示，即采用笛卡儿内部空间中的点则表示那些第一类。假定两个音频被态射到点 [0.1, -5.1, 7.55]，另两个被态射到点 [5.3, -0.1, 2.7]。那些机器学习演算法的奇妙之处是，那些点的优先选择留存了语法信息：两个音频的相近度越高，它的矢量间的距越短。
请注意，那些矢量（或更专精的用法是“内嵌”）不一定是二维的，它能、所以通常确实位于更高维的内部空间中（比如说 128 维或 750 维）。所以距也不一定是射影距，其他方式的距也能，比如说共变。不论采用何种方式，重要的是它间的距相关联于相近性。
下面，假定他们能访问所有 YouTube 音频的此类矢量。那么他们什么样找到与某个音频相近度最高的其他音频呢？很简单。遍历所有音频，计算它间的距，并优先选择距最小的音频，这个过程又称之为查找音频的“最近邻居”。这种方法确实有效，除了两个问题，线性O(N)搜寻的成本过高。所以，他们需要一类更快的次线性方法来搜寻音频的最近邻居。这通常是不可能的，必须付出一些代价。
然而，在实际情况下，他们并不需要找到“最近”的音频，只要足够接近就能了。这就是“近似最近邻”（Approximate Nearest Neighbor，ANN）演算法，又称为矢量搜寻。他们的目标是通过次线性方法找到内部空间中任何足够近的最近邻。那么，实际什么样实现呢？
什么样找到近似最近邻？矢量搜寻演算法背后的基本思想都是相同的：通过一些预处理来识别彼此足够接近的点（有点类似于建立索引）。查阅时，采用这个“索引”来排除大部分点。只留下少量点，然后再进行线性扫描。
然而，这个简单的想法有很多能实现的方法。目前有几种最先进的矢量搜寻演算法，例如 HNSW（Hierarchical Navigable Small World，分层的可导航小世界）是一类图，它连接了互相接近的顶点，所以还保存了距固定入口点的长距边。此外还有一些开放源码项目，例如 Facebook 的 FAISS，以及一些高可用矢量资料库的 PaaS 产品，例如 Pinecone 和 Weaviate。
在责任编辑中，假定有“N”个指定的点，他们要在那些点上构筑两个简化的矢量搜寻索引，步骤如下：
随机抽取 2 个矢量 A 和 B。
计算这两个矢量间的中点 C。
构筑两个通过 C 并垂直于连接 A 和 B 的线段的超平面（即更高维度的“线”）。
根据相对于超平面的位置：“上方”或“下方”，将所有矢量分为两组。
分别对两组矢量做以下处理：如果组的大小大于可配置参数“最大节点数”，则在该组之上递归调用此过程，构筑子树。否则，采用所有矢量（或它的唯一 ID）构筑两个叶节点。
他们将采用这个随机过程来构筑一棵树，其中的每个节点都是两个超平面定义，左边的子树是超平面“下方”的所有矢量，右边的子树是超平面“上方”的所有矢量。矢量集不断递归拆分，直到叶节点包含的矢量不超过“最大节点数”。下图是包含5个点的示例：
图1：利用随机超平面分割内部空间
他们随机优先选择矢量 A1=(4,2)和 B1=(5,7)，二者的中点是 (4.5,4.5)，他们构筑一条线，要求通过中点且垂直于线 (A1, B1)。这条线 x + 5y=27（图中蓝色的线）给了他们两组矢量：一组包含 2 个矢量，另一组包含 4 个。假定“最大节点数”设置为 2。那么，第一组矢量不需要进一步拆分，而第二组矢量需要进一步递归——如图所示，他们又构筑了两个红色超平面。对于大型统计数据集，如此重复拆分能将超内部空间拆分为几个不同的区域，如下所示。
图2：被许多超平面分割的内部空间（来自 https://t.co/K0Xlht8GwQ，译者：Erik Bernhardsson）
此处的每个区域代表两个叶节点，所以感觉足够接近的点很可能最终会出现在同两个叶节点中。接下来，给定两个查阅点，他们能在对数时间内自上而下遍历树，找到它所属的叶子，然后对叶节点中的所有（数量不多）点进行线性扫描。很明显，这个演算法并不是万无一失的，即便是距非常近的两个点也完全有可能被两个超平面分开，最终导致二者彼此相距很远。但是，这个问题能通过构筑多棵独立的树来解决，这样，如果两个点间的距足够近，它出现在某些树同两个叶节点中的概率就很高。在查阅时，他们自上而下遍历所有树，定位相关的叶节点，然后求所有叶节点的所有候选节点的并集，并对所有节点进行线性扫描。
好了，理论的如是说到此为止。下面，我们来撰写标识符。
首先，他们为 Rust 的 Vector 类型定义一些工具函数，包括求共变、均值、基元值以及平方 L2 距。感谢 Rust 的优雅的类型系统，他们能传递泛型类型参数 N，以在编译时强制索引中的所有矢量具有相同的维度。
#[derive(Eq, PartialEq, Hash)]pub struct HashKey<const N: usize>([u32; N]);#[derive(Copy, Clone)]pub struct Vector<const N: usize>(pub [f32; N]);impl<constN: usize> Vector { pub fn subtract_from(&self, vector: &Vector) -> Vector { let mapped = self.0.iter().zip(vector.0).map(|(a, b)| b – a); let coords: [f32; N] = mapped.collect::>().try_into().unwrap();returnVector(coords); } pub fn avg(&self, vector: &Vector) -> Vector { let mapped = self.0.iter().zip(vector.0).map(|(a, b)| (a + b) /2.0); let coords: [f32; N] = mapped.collect::>().try_into().unwrap(); returnVector(coords); } pub fn dot_product(&self, vector: &Vector) -> f32 { let zipped_iter = self.0.iter().zip(vector.0); returnzipped_iter.map(|(a, b)| a * b).sum::(); } pub fn to_hashkey(&self) -> HashKey { // f32 in Rust doesnt implement hash. We use bytes to dedup. While it // cant differentiate ~16M ways NaN is written, its safe for us let bit_iter = self.0.iter().map(|a| a.to_bits()); let data: [u32; N] = bit_iter.collect::>().try_into().unwrap();return HashKey::(data); } pub fn sq_euc_dis(&self, vector: &Vector) -> f32 { let zipped_iter =self.0.iter().zip(vector.0); return zipped_iter.map(|(a, b)| (a – b).powi(2)).sum(); }}构筑好那些核心工具函数之后，下面他们来定义超平面：
struct HyperPlane<constN: usize> { coefficients: Vector, constant: f32,}impl<const N: usize> HyperPlane { pub fn point_is_above(&self, point: &Vector) -> bool { self.coefficients.dot_product(point) +self.constant >= 0.0 }}接下来，他们来生成随机超平面，构筑最近邻树的森林。他们应该什么样则表示树中的点呢？
他们能直接将 D 维矢量存储在叶节点中。但是，如果这个维度（D）非常大，那么会导致内存碎片化（严重影响到性能），所以当多棵树引用同两个矢量时，还会造成森林重复保存。因此，他们将矢量存储在全局可访问的连续位置中，并在叶节点中保存类型为 usize 的索引（在 64 位系统上仅占用 8 字节，相反如果直接保存四维矢量，每个维度的 f32 类型就会占用 4 字节）。以下是用于则表示树内部节点和叶节点的统计数据类型。
enum Node<const N: usize> { Inner(Box<InnerNode<N>>), Leaf(Box<LeafNode<N>>),}struct LeafNode<const N: usize>(Vec<usize>);struct InnerNode<const N: usize> { hyperplane: HyperPlane<N>, left_node: Node<N>, right_node: Node<N>,}pub struct ANNIndex<const N: usize> { trees: Vec<Node<N>>, ids: Vec<i32>, values: Vec<Vector<N>>,}那么，他们应该什么样找到正确的超平面呢？
他们从索引中随机采样两个，分别相关联于矢量 A 和 B，计算 n = A – B，并找到 A 和 B 的中点（point_on_plane）。存储超平面采用的结构包含系数（矢量 n）和常量（n 和 point_on_plane 的共变），方式为：n(x-x0) = nx – nx0。他们能求矢量和 n 间的共变，然后减去常数，就能将矢量放在超平面的“上方”或“下方”。由于树中的内部节点包含超平面定义，叶节点包含矢量 ID，因此他们能采用 ADT 对树进行类型检查：
impl ANNIndex { fn build_hyperplane( indexes: &Vec, all_vecs: &Vec>, ) -> (HyperPlane, Vec, Vec) {letsample: Vec = indexes .choose_multiple(&mut rand::thread_rng(), 2) .collect(); // cartesian eqforhyperplane n * (x – x_0) = 0 // n (normal vector) is the coefs x_1 to x_nlet (a, b) = (*sample[0], *sample[1]); letcoefficients = all_vecs[a].subtract_from(&all_vecs[b]);let point_on_plane = all_vecs[a].avg(&all_vecs[b]); letconstant = -coefficients.dot_product(&point_on_plane);let hyperplane = HyperPlane:: { coefficients, constant, }; let(mut above, mut below) = (vec![], vec![]);for &id in indexes.iter() { ifhyperplane.point_is_above(&all_vecs[id]) { above.push(id) }else { below.push(id) }; } return (hyperplane, above, below); }}接下来，他们定义递归过程，根据索引时的“最大节点数”构筑树：
impl<constN: usize> ANNIndex { fn build_a_tree( max_size: i32, indexes: &Vec, all_vecs: &Vec>, ) -> Node {if indexes.len() as usize) { return Node::Leaf(Box::new(LeafNode::(indexes.clone()))); } let (plane, above, below) =Self::build_hyperplane(indexes, all_vecs); let node_above = Self::build_a_tree(max_size, &above, all_vecs); let node_below =Self::build_a_tree(max_size, &below, all_vecs); returnNode::Inner(Box::new(InnerNode:: { hyperplane: plane, left_node: node_below, right_node: node_above, })); }}请注意，由于该演算法不允许重复，构筑两点间的超平面要求这两个点是唯一的，因此在建立索引之前，他们必须去除矢量集中的重复项。
因此整个索引（树的森林）能这样构筑：
impl<constN: usize> ANNIndex { fn deduplicate( vectors: &Vec>,ids: &Vec, dedup_vectors: &mut Vec>, ids_of_dedup_vectors: &mut Vec, ) { let mut hashes_seen = HashSet::new(); for i in 1..vectors.len() { lethash_key = vectors[i].to_hashkey();if!hashes_seen.contains(&hash_key) { hashes_seen.insert(hash_key); dedup_vectors.push(vectors[i]); ids_of_dedup_vectors.push(ids[i]); } } } pub fn build_index( num_trees: i32,max_size: i32,vecs: &Vec>, vec_ids: &Vec, ) -> ANNIndex { let(mut unique_vecs, mut ids) = (vec![], vec![]); Self::deduplicate(vecs, vec_ids, &mut unique_vecs, &mut ids);// Trees hold an index into the [unique_vecs] list which is not // necessarily its id, if duplicates existed let all_indexes: Vec = (0..unique_vecs.len()).collect();let trees: Vec = (0..num_trees) .map(|_| Self::build_a_tree(max_size, &all_indexes, &unique_vecs)) .collect();return ANNIndex::<N> { trees, ids, values: unique_vecs, }; }} 查阅时间索引建立之后，下一步他们什么样采用它搜寻某棵树中输入矢量的 K 个近似最近邻？他们的超平面存储在非叶节点处，因此他们能从树的根开始搜寻：“这个矢量是在这个超平面的上方还是下方？”他们能用共变计算，繁杂度为 O(D)。接下来，他们能根据响应，递归搜寻左子树或右子树，直到找到叶节点。请记住，叶节点中存储的矢量数最大为“最大节点数”，那些矢量位于输入矢量的近似邻域中（它将落入所有超平面下超内部空间的同一分区中）。如果这个叶节点的矢量索引数超过 K，他们就需要根据到输入矢量的 L2 距，对所有那些矢量进行排序，并返回最接近的 K 个矢量。
假定他们的索引最后得到了一棵平衡树，对于维度 D、矢量数量 N 和最大节点数 M << N，搜寻耗费的时间为 O(Dlog(N) + DM + Mlog(M))，最坏的情况下他们需要比较 log(N) 个超平面（即树的高度）才能找到叶节点，每次比较耗费的时间为 O(D) 个共变，计算两个叶节点的所有候选矢量的 L2 距需要 O(DM)，最后在 O(Mlog(M)) 时间内对它进行排序，并返回 前 K 个。
但是，如果他们找到的叶节点少于 K 个矢量，会发生什么情况？如果最大节点数太小，或超平面分割不均匀，则会导致某个子树中的矢量非常少。为了解决这个问题，他们能在树搜寻中添加一些简单的回溯功能。例如，如果返回的候选矢量数量不足，他们能在内部节点再递归调用一次，访问另两个分枝。标识符如下：
1impl<const N: usize> ANNIndex { 2 fn tree_result( 3 query: Vector, 4 n: i32, 5 tree: &Node, 6candidates: &mut HashSet, 7 ) -> i32 { 8 // take everything in node, if still needed, take from alternate subtree 9 match tree {10 Node::Leaf(box_leaf) => {11 let leaf_values = &(box_leaf.0);12let num_candidates_found = min(nas usize, leaf_values.len());13 for i in 0..num_candidates_found {14candidates.insert(leaf_values[i]);15 }16 return num_candidates_found as i32;17 }18 Node::Inner(inner) => {19let above = (*inner).hyperplane.point_is_above(&query);20 let (main, backup) = match above {21 true=> (&(inner.right_node), &(inner.left_node)),22 false => (&(inner.left_node), &(inner.right_node)),23 };24 match Self::tree_result(query, n, main, candidates) {25 k if k < n => {26 k + Self::tree_result(query, n – k, backup, candidates)27 }28 k => k,29 }30 }31 }32 }33}请注意，为了进一步优化递归调用，他们还能保存子树中的矢量总数，并在每个内部节点中保存指向所有叶节点的指针列表，但为了简单起见，此处略过。
将此搜寻扩展到一片森林非常简单，只需从所有树木中单独收集前 K 个候选者，按距对它进行排序，然后返回总体的前 K 个匹配项。请注意，随着树的数量增加，内存的采用和搜寻时间都会呈线性增长，但他们能获得更好的“更近”邻居，因为他们收集了来自不同树的候选者。
1impl<const N: usize> ANNIndex { 2 pub fn search_approximate( 3 &self, 4query: Vector, 5 top_k: i32, 6 ) -> Vec { 7 let mut candidates = HashSet::new(); 8 for tree in self.trees.iter() { 9 Self::tree_result(query, top_k, tree, &mut candidates);10 }11 candidates12 .into_iter()13 .map(|idx| (idx, self.values[idx].sq_euc_dis(&query)))14 .sorted_by(|a, b| a.1.partial_cmp(&b.1).unwrap())15 .take(top_k as usize)16 .map(|(idx, dis)| (self.ids[idx], dis))17 .collect()18 }19}以上就是两个简单的矢量搜寻索引的 200 行 Rust 标识符！
基准测试
其实，这个实现非常简单，以至于他们一度怀疑相较于最先进的演算法，这个演算法非常拙略。因此，他们做了一些基准测试来证实他们的怀疑。
演算法能通过延迟和质量来评估。质量通常通过召回率来衡量：求近似最近邻搜寻返回结果与线性搜寻返回结果的百分比。严格来说，有时返回的结果并不在前 K，但非常接近 K，因此也没关系，为了量化这一点，他们能计算邻居的平均欧几里德距，并将其与平均距进行比较。
测量延迟很简单，他们可以检查执行查阅所需的时间。
所有的基准测试都是在搭载了 2.3 GHz 四核英特尔酷睿 i5 处理器的机器上运行的，采用了 999,994 条维基百科统计数据 FastText 内嵌，300 个维度。他们设置返回“前 K 个”查阅结果。
作为参考，他们拿 FAISS HNSW 索引（ef_search=16、ef_construction=40、max_node_size=15）与 Rust 索引的小型版本（num_trees=3、max_node_size=15）进行了比较。他们采用 Rust 实现了穷举搜寻，而 FAISS 库有 HNSW 的 C++ 源标识符。原始延迟数突出了近似搜寻的优势：
演算法
延迟
QPS
穷举搜寻
675.25 毫秒
1.48
FAISS HNSW 索引
355.36 微秒
2814.05
自订 Rust 索引
112.02 微秒
8926.98
两种近似最近邻方法快了三个数量级。看起来在这个微型基准测试中，他们的 Rust 实现比 HNSW 快 3 倍。
在分析质量时，他们的测试统计数据为：返回“river”的 10 个最近的邻居。
穷举搜寻
FAISS HNSW 索引
自订 Rust 索引
单词
欧几里得距
单词
射影距
单词
射影距
river
0
river
0
river
0
River
1.39122
River
1.39122
creek
1.63744
rivers
1.47646
river-
1.58342
river.
1.73224
river-
1.58342
swift-flowing
1.62413
lake
1.75655
swift-flowing
1.62413
flood-swollen
1.63798
sea
1.87368
creek
1.63744
river.The
1.68156
up-river
1.92088
flood-swollen
1.63798
river-bed
1.68510
shore
1.92266
river.The
1.68156
unfordable
1.69245
brook
2.01973
river-bed
1.68510
River-
1.69512
hill
2.03419
unfordable
1.69245
River.The
1.69539
pond
2.04376
再来两个例子，这次他们搜寻“war”。
穷举搜寻
FAISS HNSW 索引
自订 Rust 索引
单词
射影距
单词
射影距
单词
射影距
war
0
war
0
war
0
war–
1.38416
war–
1.38416
war–
1.38416
war–a
1.44906
war–a
1.44906
wars
1.45859
wars
1.45859
wars
1.45859
quasi-war
1.59712
war–and
1.45907
war–and
1.45907
war-footing
1.69175
war.It
1.46991
war.It
1.46991
check-mate
1.74982
war.In
1.49632
war.In
1.49632
ill-begotten
1.75498
unwinable
1.51296
unwinable
1.51296
subequent
1.76617
war.And
1.51830
war.And
1.51830
humanitary
1.77464
hostilities
1.54783
Iraw
1.54906
execution
1.77992
他们采用的这个语料库包含 999,994 个单词，他们可视化了在 HNSW 和他们的自订 Rust 索引下，每个单词与其前 K=20 个近似邻居的平均射影距的分布：
最先进的 HNSW 索引提供的邻居确实比他们的示例索引更近，其平均距和中值距分别为 1.31576 和 1.20230（而与他们的示例索引分别为 1.47138 和 1.35620）。在大小为 1 万的子集上，HNSW 的前 K=20 的召回率为 58.2%，而他们的示例索引在不同配置下的测试结果如下：
树的数量
最大节点数
平均运行时间
QPS
召回率
3
5
129.48微秒
7723
0.11465
3
15
112.02微秒
8297
0.11175
3
30
114.48微秒
8735
0.09265
9
5
16.77毫秒
60
0.22095
9
15
1.54毫秒
649
0.20985
9
30
370.80微秒
2697
0.16835
15
5
35.45毫秒
28
0.29825
15
15
7.34毫秒
136
0.28520
15
30
2.19毫秒
457
0.23115
通过上面的数字能看出，虽然他们的演算法在质量上无法与尖端技术相媲美，但它的速度非常快。为什么会这样？
老实说，在构筑这个演算法时，他们兴奋得昏了头脑，性能优化也只是为了好玩。下面是一些重要的优化：
将去除文件格式的重复统计数据的过程转移到索引冷路径上。通过索引（而不是浮点数组）引用矢量能大幅提高搜寻速度，因为跨树搜寻唯一候选者只需要对 8 字节索引进行散列（而不是 300 维 f32 统计数据）。
在将点添加到全局候选列表之前，散列并搜寻唯一矢量，通过递归搜寻调用中的可变引用传递统计数据，以避免栈帧间和栈帧内的复制。
将 N 作为通用类型参数传递进去，这样类型检查就会将 300 维的统计数据当作长度为 300 的 f32 数组，这不仅能改善缓存局部性性，还可以减少内存占用。
他们怀疑内部操作（例如共变）被 Rust 编译器矢量化了，但他们没有检查。
一些真实世界应用的考虑
有一些问题这个示例没有考虑到，但在生产环境的矢量搜寻中非常关键：
当搜寻涉及多个树时应当使用并行。不要顺序收集候选者，而是应该并行进行，因为每个树都会访问完全不同的内存，因此每个树都能在各自的线程上单独运行，候选者通过通道发送到主线程。线程能在创建索引时建立，并采用模拟搜寻进行预热（将树加载到缓存），从而减小搜寻的额外开销。这样搜寻就不会根据树的数量线性增长了。
大型树可能无法完备地加载到内存中，可能需要从磁盘中读取，所以能将特定的子图放到磁盘上，并精心设计演算法，保证搜寻正常工作的同时，尽可能减小文件I/O。
继续深入，如果树无法保存在两个实例的磁盘上，能将子树分布到多个实例中，并让递归搜寻在本地统计数据不存在时发出RPC请求。
树包含许多内存重定向（如前所述指针的树对L1缓存不友好）。平衡树能写成数组，但他们的树只是接近平衡，其超平面是随机的。是否可能采用新的统计数据结构？
上述问题的解决方案，对于新统计数据即时编制索引也是成立的（可能需要对大型树进行分片）。如果特定索引序列会导致非常不平衡的树，那么是否应该重建树？
那些都是他们未来该深刻思考的问题。
原文链接：https://fennel.ai/blog/vector-search-in-200-lines-of-rust/
声明：责任编辑为 CSDN 翻译，未经允许，禁止转载。
