ElasticSearch学习篇11_ANNS之基于图的NSW、HNSW算法

前言

往期博客ElasticSearch学习篇9_文本相似度计算方法现状以及基于改进的 Jaccard 算法代码实现与效果测评_elasticsearch 文字相似度实现方法-CSDN博客 根据论文对文本相似搜索现状做了一个简要总结，然后对论文提到的改进杰卡德算法做了实现，并结合业务场景测评，另外对其他两种改进杰卡德算法做了测评总结适用的业务场景。

面对多维数据，空间紧邻搜索被应用在多种场景的检索需求，如人脸识别、图片搜索、商品的推荐搜索等。如何高效的从海量数据中紧邻搜索热点数据是某些搜索业务场景所要求的，下面是学术界常用的用在空间紧邻搜索的四种算法思想，在此基础上也衍生的很多工业界针对不同业务场景的开源检索算法入ANNOY、faiss、QSG-NGT等

而Lucene和ES使用的多维数据紧邻搜索是改进的BKD以及HNSW，Lucene从6.0版本引入了BKD，关于BKD原理参考往期博客，该BKD结构就是基于空间分割算法。Elasticsearch从8.0版本开始引入了向量近邻检索k-nearest neighbor（kNN）search功能，该功能支持使用HNSW（Hierarchical Navigable Small World）算法来优化向量检索的性能。下面主要了解相关算法以及学习基于图的NSW、HNSW算法。

目录

一、ANNS

1、ANNS概述

ANNS（Approximate Nearest Neighbor Search）翻译为近似最近搜索。是指在大型数据集中找到给定查询点的最近邻点。ANNS 旨在最小化计算成本并同时高效找到近似最近邻。
ANNS和ANN（Artificial Neural Network）和KNN（K-Nearest Neighbors）是三种不同的概念，它们在目的、原理和应用场景上有所区别：

1. ANNS（Approximate Nearest Neighbor Search）:
   • 目的：ANNS旨在高维空间中快速找到与查询点近似最近的邻居，牺牲一定的精确度以换取搜索速度的提升。
   • 原理：通过构建特定的数据结构（如基于空间划分的KD-Tree、局部敏感哈希LSH等）或使用特定的算法逻辑来减少在高维空间中搜索最近邻所需的计算量。
   • 应用场景：广泛应用于推荐系统、图像检索、模式识别等领域，特别是在处理大规模高维数据时。
2. ANN（Artificial Neural Network）:
   • 目的：ANN是一种模仿生物神经网络行为的计算模型，用于识别数据中的复杂模式和关系，进行分类、回归等任务。
   • 原理：由多层神经元组成，通过前向传播和反向传播算法，调整神经元之间的连接权重，以学习输入与输出之间的映射关系。
   • 应用场景：广泛应用于图像识别、语音识别、自然语言处理等领域。
3. KNN（K-Nearest Neighbors）:
   • 目的：KNN是一种基于实例的学习方法，用于分类或回归任务，通过查找最近的K个邻居来预测新样本的类别或值。
   • 原理：不需要显式的训练过程，而是直接根据距离度量（如欧氏距离）在训练数据集中找到与新样本最近的K个样本，然后根据这些邻居的信息进行预测。
   • 应用场景：适用于小到中等规模的数据集，常用于分类问题、推荐系统等。

总结：

• ANNS关注于高维空间中的近似最近邻搜索，主要解决搜索效率问题。
• ANN是一种模拟人脑神经网络的计算模型，用于学习数据的复杂