【AI知识点】分层可导航小世界网络算法 HNSW(Hierarchical Navigable Small World)
HNSW(Hierarchical Navigable Small World)分层可导航小世界网络算法 是一种高效的近似最近邻搜索(Approximate Nearest Neighbor Search, ANN) 算法,特别适用于大规模、高维数据集的相似性检索。HNSW 基于小世界网络(small-world networks)原理,通过构建一个多层次的图结构,能够快速找到与查询点相似的数据点。它在实践中非常流行,广泛用于需要快速搜索高维数据的任务,例如图像检索、推荐系统、文本嵌入向量检索等。
1. HNSW的背景
在处理高维数据时,经典的最近邻搜索方法(如暴力搜索)由于计算复杂度高,在实际应用中效率低下。HNSW 通过引入一种基于图的结构,显著提高了近似最近邻搜索的效率,同时保持了较高的精度。HNSW 是一种改进的基于图的搜索方法,它借鉴了“小世界”网络的概念,即在图中任何两个节点之间都有相对较短的路径。
2. HNSW的核心思想
HNSW 的基本思路是将数据点组织成一个分层图结构,每一层的图结构代表数据的不同分辨率。在高层次,数据点的数量较少,连接关系较少,搜索效率较高。在底层,数据点的数量较多,连接关系更密集,能够更精确地找到最近邻。通过逐层导航和搜索,HNSW 能够快速找到与查询点最相似的点。
比喻解释:
可以将HNSW比作一个由多层城市地图组成的导航系统。最上层的地图展示了整个城市的概貌,虽然不详细,但能让你大致找到查询点所在的区域;随着你进入下一层,更详细的街道信息出现,你可以更精确地靠近目标;在最后的层次上,你甚至可以看到具体的建筑物,帮助你找到目标位置。这种从粗略到精细的导航过程帮助你快速找到目标,而不必从头到尾细致地搜索整个城市。
3. HNSW的工作原理
HNSW的结构和搜索过程可以分为两个阶段:构建图结构 和 搜索过程。
图结构和搜索过程可参考下图:
图片来源:https://www.pinecone.io/learn/series/faiss/hnsw/
a. 构建图结构
HNSW使用分层的图(network)来表示数据点。在最上层的图中,每个节点代表一个数据点,图中的连接稀疏;随着层数降低,图中的节点和连接变得更加密集。构建过程如下:
-
层次结构:
HNSW 将数据点分配到不同的层次。在较高层,数据点较少且连接较少,而在较低层,数据点较多且连接较密集。最上层的数据点数最少,搜索可以从这里开始逐层导航到更低层,直到找到最近邻。 -
基于随机化的层次分配:
每个数据点被分配到不同的层次是随机的。数据点的层数是根据某种随机分布(如泊松分布)确定的,较少的数据点会被分配到上层,而大多数数据点只会出现在较低的层次中。 -
小世界图结构:
每一层的图都符合“小世界”网络的特性:节点之间的连接既有局部的,也有较远距离的(跨越较长距离的跳跃连接)。这种结构保证了即使在高维空间中,也能通过少数几步找到相近的节点。 -
邻居选择:
在每一层,节点只会连接到与它距离较近的其他节点。这种邻居选择策略保证了图的连通性,同时限制了连接的数量,使得计算和存储效率更高。
b. 搜索过程
HNSW的搜索是一个从上到下的过程,即从最上层的稀疏图开始搜索,逐步进入下层的密集图。整个搜索过程如下:
-
从顶层开始:搜索从顶层的稀疏图开始。由于顶层节点较少,搜索过程可以快速找到一个与查询点相对接近的节点。
-
逐层导航:一旦在上层找到一个接近的节点,搜索会进入下一层更密集的图。在每一层,算法会在该层的邻居节点之间进行本地搜索,以找到更接近查询点的节点。
-
近邻搜索:在底层的密集图中,搜索的精度较高,可以更精确地找到查询点的近似最近邻。在这个过程中,使用启发式方法来选择要探索的节点,并限制需要访问的节点数量。
-
返回结果:搜索最终会在最底层找到一个或多个与查询点最相似的点,这些点就是近似最近邻。
4. HNSW的优势
HNSW在实践中非常有效,原因包括以下几个方面:
-
快速搜索:通过分层的小世界图结构,HNSW 能够以较低的时间复杂度完成近似最近邻搜索。它可以通过逐层导航,快速减少搜索空间,从而在大规模数据集中进行快速检索。
-
高精度:尽管 HNSW 是一种近似搜索方法,它的精度通常非常接近精确的最近邻搜索。这是因为在底层的密集图中,局部搜索非常精确。
-
可扩展性:HNSW非常适合处理大规模、高维数据集。随着数据集的增大,HNSW的搜索时间增长较慢,且它能够在线增量构建,即随着数据的加入,图结构可以动态更新。
-
灵活性:HNSW可以应用于不同的距离度量方法,包括欧几里得距离、余弦相似度等。
5. HNSW的缺点
尽管HNSW在大规模高维数据检索中表现非常好,但它也有一些局限性:
-
构建图的复杂度较高:与其他ANN算法相比,HNSW的图构建过程较为复杂,尤其是在处理非常大规模的数据集时,初始构建可能会消耗较多时间和资源。
-
内存占用较大:HNSW 通过存储分层的图结构,内存使用量会较大,特别是在处理高维、海量数据时,需要足够的内存来存储节点和连接信息。
6. HNSW的实际应用
HNSW由于其高效的搜索能力,已经被广泛应用于各种实际场景中:
-
推荐系统:在推荐系统中,HNSW可以快速找到与用户行为或兴趣相似的其他用户或物品,提供个性化的推荐。
-
图像搜索:HNSW能够快速处理高维图像特征向量,帮助图像搜索系统找到与查询图像相似的其他图片。
-
文本检索:HNSW可用于处理文本嵌入向量的相似性搜索,帮助自然语言处理系统快速找到语义相似的文本。
-
生物信息学:在生物信息学中,HNSW可以用于处理基因序列或蛋白质结构的相似性搜索。
7. HNSW与其他ANN算法的比较
-
与LSH(Locality Sensitive Hashing)相比:LSH通过哈希将相似的数据点映射到相同的桶中,而HNSW使用基于图的结构。相比之下,HNSW通常在精度和效率上优于LSH,特别是在处理高维数据时。
-
与KD树、Ball树相比:KD树和Ball树适合处理低维数据,但在高维数据上效率迅速下降。相比之下,HNSW在高维数据上表现得更好,具有更好的扩展性。
8. 总结
HNSW(Hierarchical Navigable Small World) 是一种基于分层图结构的高效近似最近邻搜索算法,它通过构建小世界图结构,在处理大规模、高维数据时实现了快速和高精度的搜索。它已在多个领域得到了广泛应用,如推荐系统、图像检索、文本相似性搜索等。尽管构建和内存开销较大,HNSW仍然是许多高维搜索任务中的首选算法之一。
相关文章:

【AI知识点】分层可导航小世界网络算法 HNSW(Hierarchical Navigable Small World)
HNSW(Hierarchical Navigable Small World)分层可导航小世界网络算法 是一种高效的近似最近邻搜索(Approximate Nearest Neighbor Search, ANN) 算法,特别适用于大规模、高维数据集的相似性检索。HNSW 基于小世界网络&…...

ubuntu图形界面右上角网络图标找回解决办法
问题现象: ubuntu图形界面右上角网络图标消失了,不方便联网: 正常应该是下图: 网络寻找解决方案,问题未解决,对于某些场景可能有用,引用过来: 参考方案 Ubuntu虚拟机没有网络图标或…...
maven安装本地jar包到本地仓库
有时候我们需要把本地的 jar 包 install 到本地的 maven 仓库,这时就需要手动install依赖项。例如,把下面的 zhdx-license-1.0.jar 安装到本地 maven 仓库的操作如下: <dependency><groupId>com.zhdx</groupId><artifa…...

1panel申请https/ssl证书自动续期
参考教程 https://hin.cool/posts/sslfor1panel.html #Acme 账户 #1panel.腾讯云dns账号 这里有一步不需要参考,腾讯云dns账号,就是子帐号授权 直接控制台搜索 访问管理 创建用户 授权搜索dns,选择第一个 点击用户名,去掉AdministratorAccess权限 5.点击api密钥生成即可…...

【C语言】指针篇 | 万字笔记
写在前面 在学习C语言过程,总有一个要点难点离不开,那就是大名鼎鼎的C语言指针,也是应为有指针的存在,使得C语言一直长盛不衰。因此不才把指针所学的所有功力都转换成这个笔记。希望对您有帮助🥰🥰 学习指…...
使用transformers调用owlv2实现开放目标检测
目录 安装Demo 安装 pip install transformersDemo from PIL import Image, ImageDraw, ImageFont import numpy as np import torch from transformers import AutoProcessor, Owlv2ForObjectDetection from transformers.utils.constants import OPENAI_CLIP_MEAN, OPENAI_…...

大数据技术:Hadoop、Spark与Flink的框架演进
大数据技术,特别是Hadoop、Spark与Flink的框架演进,是过去二十年中信息技术领域最引人注目的发展之一。这些技术不仅改变了数据处理的方式,而且还推动了对数据驱动决策和智能化的需求。在大数据处理领域,选择合适的大数据平台是确…...
Spring Boot框架下的新闻推荐技术
1系统概述 1.1 研究背景 如今互联网高速发展,网络遍布全球,通过互联网发布的消息能快而方便的传播到世界每个角落,并且互联网上能传播的信息也很广,比如文字、图片、声音、视频等。从而,这种种好处使得互联网成了信息传…...

相亲交友系统的社会影响:家庭结构的变化
随着互联网技术的发展,相亲交友系统已成为许多单身人士寻找伴侣的重要途径。这些平台不仅改变了人们的社交方式,还对家庭结构产生了深远的影响。本文将探讨相亲交友系统如何促使家庭结构发生变化,开发h17711347205并通过简单的Python代码示例…...
C++ 内存池(Memory Pool)详解
1. 基本概念 内存池是一种内存管理技术,旨在提高内存分配的效率。它通过预先分配一块大的内存区域(池),然后从中分配小块内存来满足应用程序的需求。这样可以减少频繁的内存分配和释放带来的性能开销。 2. 设计思路 内存池的设…...
css三角形:css画箭头向下的三角形
.arrow { position: absolute; bottom: 0; left: 50%; transform: translateX(-50%); width: 0; height: 0; border-style: solid; border-width: 8px 5px 0 5px; /* 上、左、下、右 */ bord…...
CSS属性 - animation
一、基本概念 animation是 CSS 中的一个属性,用于将通过keyframes规则定义的动画应用到元素上。它是一种简写属性,能够在一个声明中设置多个动画相关的子属性。 二、语法结构 基本语法为: animation: name duration timing - function de…...
昇思MindSpore进阶教程--在ResNet-50网络上应用二阶优化实践(下)
大家好,我是刘明,明志科技创始人,华为昇思MindSpore布道师。 技术上主攻前端开发、鸿蒙开发和AI算法研究。 努力为大家带来持续的技术分享,如果你也喜欢我的文章,就点个关注吧 文章上半部分请查看 在ResNet-50网络上应…...

基于大数据的Python+Django电影票房数据可视化分析系统设计与实现
目录 1 引言 2 系统需求分析 3 技术选型 4 系统架构设计 5 关键技术实现 6 系统实现 7 总结与展望 1 引言 随着数字媒体技术的发展,电影产业已经成为全球经济文化不可或缺的一部分。电影不仅是艺术表达的形式,更是大众娱乐的重要来源。在这个背景…...
实景三维技术对光伏产业的发展具有哪些优势?
实景三维技术对光伏产业的发展具有显著的优势,主要体现在提高选址准确性、优化用地规划、促进数据融合应用以及赋能文旅服务领域。 提高选址准确性:通过构建高精度的三维地形模型,结合卫星遥感、无人机测绘等技术手段,实景三维…...

四非人的保研之路,2024(2025届)四非计算机的保研经验分享(西南交通、苏大nlp、西电、北邮、山软、山计、电科、厦大等)
文章目录 一、个人背景二、夏令营北京邮电大学CS西南交通大学CS深圳大学CS苏州大学NLP南开大学CS 三、预推免北京邮电大学CS华东师范大学 CS和大数据电子科技大学 CS东北大学 CS厦门大学 信息学院山东大学 CS和SE西安电子科技大学 CS 四、个人经验五、上岸 一、个人背景 学校专…...

UE5.4.3 录屏回放系统ReplaySystem蓝图版
这是ReplaySystem的蓝图使用方法版,以第三人称模版为例,需要几个必须步骤 项目config内DefaultEngine.ini的最后添加: [/Script/Engine.GameEngine] NetDriverDefinitions(DefName"DemoNetDriver",DriverClassName"/Script/…...

ECCV 2024 | 融合跨模态先验与扩散模型,快手处理大模型让视频画面更清晰!
计算机视觉领域顶级会议 European Conference on Computer Vision(ECCV 2024)将于9月29日至10月4日在意大利米兰召开,快手音视频技术部联合清华大学所发表的题为《XPSR: Cross-modal Priors for Diffusion-based Image Super-Resolution》——…...

9--苍穹外卖-SpringBoot项目中Redis的介绍及其使用实例 详解
目录 Redis入门 Redis简介 Redis服务启动与停止 服务启动命令 Redis数据类型 5种常用数据类型介绍 各种数据类型的特点 Redis常用命令 字符串操作命令 哈希操作命令 列表操作命令 集合操作命令 有序集合操作命令 通用命令 在java中操作Redis Redis的Java客户端 …...

【EXCEL数据处理】000014 案例 EXCEL分类汇总、定位和创建组。附多个操作案例。
前言:哈喽,大家好,今天给大家分享一篇文章!创作不易,如果能帮助到大家或者给大家一些灵感和启发,欢迎收藏关注哦 💕 目录 【EXCEL数据处理】000014 案例 EXCEL分类汇总、定位和创建组。附多个操…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...

Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...

ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...