【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分类汇总、定位和创建组。附多个操…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...

VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...

高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...