推荐算法:HNSW【推荐出与用户搜索的类似的/用户感兴趣的商品】
HNSW算法概述
HNSW(Hierarchical Navigable Small Word)算法算是目前推荐领域里面常用的ANN(Approximate Nearest Neighbor)算法了。其目的就是在极大量的候选集当中如何快速地找到一个query最近邻的k个元素。
要找到一个query的k个最近邻元素,一个朴素的思想就是我去计算这个query和所有的总量N 个候选元素的距离,然后选择其中的前k 个最小元素,这个经典算法的算法复杂度是O(Nlog(k)),显然这个算法复杂度实在是太高了,无法适用于实际的使用场景。
而要解决这个问题,可以有多种实现方法,这里所要说的HNSW算法就是目前比较常用的一种搜索算法,它算是其前作NSW算法的一个升级版本,但是两者的本质都是基于一个朴素的思路,就是通过图连接的方式给所有的N 个候选元素事先地定义好一个图连接关系,从而可以将前述的算法复杂度当中的N 的部分给减小掉,从而优化整体的检索效率。
其整体的一个图结果可以用下图进行表达:

解决的问题:做高效率相似性查找。推荐系统中,如何找到与用户query最相近的几个item,然后推荐出去【也就是推荐出与用户搜索的类似的/用户感兴趣的商品】。
解决方法有:Annoy,KD-Tree, LSH, PQ,NSW, HNSW等。
近似最近邻搜索算法(Approximate Nearest Neighbor Search,ANNS)发展:近邻图(Proximity Graph)–> NSW --> Skip List --> HNSW
近似最近邻搜索算法(Approximate Nearest Neighbor Search,ANNS)
1. 近邻图(Proximity Graph)
近邻图(Proximity Graph): 最朴素的图算法
思路: 构建一张图, 每一个顶点连接着最近的 N 个顶点。 Target (红点)是待查询的向量。在搜索时, 选择任意一个顶点出发。 首先遍历它的友节点, 找到距离与 Target 最近的某一节点, 将其设置为起始节点, 再从它的友节点出发进行遍历, 反复迭代, 不断逼近, 最后找到与 Target 距离最近的节点时搜索结束。

存在的问题:
- 图中的K点无法被查询到。
- 如果要查找距离Target (红点)最近的topK个点, 而如果点之间无连线, 将影响查找效率。
- D点有这么多友节点吗? 增加了构造复杂度。谁是谁的友节点如何确定?
- 如果初始点选择地不好(比如很远),将进行多步查找。
2. NSW算法原理
NSW,即没有分层的可导航小世界的结构(Navigable-Small-World-Graph )。
针对上面的问题,解决办法:
- 某些点无法被查询到 -> 规定构图时所有节点必须有友节点。
- 相似点不相邻的问题 -> 规定构图时所有距离相近到一定程度的节点必须互为友节点。
- 关于某些点有过多友节点 -> 规定限制每个节点的友节点数量。
- 初始点选择地很远 -> 增加高速公路机制。
2.1 NSW构图算法
图中插入新节点时,通过随机存在的一个节点出发查找到距离新节点最近的m个节点(规定最多m个友节点,m由用户设置),连接新节点到这最近的m个节点。节点的友节点在新的节点插入的过程中会不断地被更新。

m=3(每个点在插入时找3个紧邻友点)。
第1次构造:图为空,随机插入A,初始点为A。图中只有A,故无法挑选友节点。插入B,B点只有A点可选,所以连接BA。
第2次构造:插入F,F只有A和B可以选,所以连接FA,FB。
第3次构造:插入C,C点只有A,B,F可选,连接CA,CB,CF。
第4次构造:插入E,从A,B,C,F任意一点出发,计算出发点与E的距离和出发点的所有“友节点”和E的距离,选出最近的一点作为新的出发点,如果选出的点就是出发点本身,那么看我们的m等于几,如果不够数,就继续找第二近的点或者第三近的点,本着不找重复点的原则,直到找到3个近点为止。找到了E的三个近点,连接EA,EC,EF。
第5次构造:插入D,与E点的插入一模一样,都是在“现成”的图中查找到3个最近的节点作为“友节点”,并做连接。
第6次构造:插入G,与E点的插入一模一样,都是在“现成”的图中查找到3个最近的节点作为“友节点”,并做连接。
在图构建的早期,很有可能构建出“高速公路”。
第n次构造:在这个图的基础上再插入6个点,这6个点有3个和E很近,有3个和A很近,那么距离E最近的3个点中没有A,距离A最近的3个点中也没有E,但因为A和E是构图早期添加的点,A和E有了连线,我们管这种连线叫“高速公路”,在查找时可以提高查找效率(当进入点为E,待查找距离A很近时,我们可以通过AE连线从E直接到达A,而不是一小步一小步分多次跳转到A)。
结论:一个点,越早插入就越容易形成与之相关的“高速公路”连接,越晚插入就越难形成与之相关的“高速公路”连接。
这个算法设计的妙处就在于扔掉德劳内三角构图法,改用“无脑添加”(NSW朴素插入算法),降低了构图算法时间复杂度的同时还带来了数量有限的“高速公路”,加速了查找。
2.2 NSW查找算法

图中的边有两个不同的目的:
- Short-range edges,用作贪婪搜索算法所需的近似 Delaunay 图。
- Long-range edges,用于贪婪搜索的对数缩放。负责构造图形的可导航小世界(NSW)属性。
优化查找:
- 建立一个废弃列表visitedSet,在一次查找任务中遍历过的点不再遍历。
- 建立一个动态列表result,把距离查找点最近的n个点存储在表中,并行地对这n个点进行同时计算“友节点”和待查找点的距离,在这些“友节点”中选择n个点与动态列表中的n个点进行并集操作,在并集中选出n个最近的友点,更新动态列表。

推荐算法:HNSW算法简介-CSDN博客
检索模型-粗排HNSW_hnsw模型-CSDN博客
相关文章:
推荐算法:HNSW【推荐出与用户搜索的类似的/用户感兴趣的商品】
HNSW算法概述 HNSW(Hierarchical Navigable Small Word)算法算是目前推荐领域里面常用的ANN(Approximate Nearest Neighbor)算法了。其目的就是在极大量的候选集当中如何快速地找到一个query最近邻的k个元素。 要找到一个query的…...
C++ //例3.14 找出100~200间的全部素数。
C程序设计 (第三版) 谭浩强 例3.14 例3.14 找出100~200间的全部素数。 IDE工具:VS2010 Note: 使用不同的IDE工具可能有部分差异。 代码块 方法:使用函数的模块化设计 #include <iostream> #include <iomanip> #i…...
虚幻学习笔记11—C++结构体、枚举与蓝图的通信
一、前言 结构体的定义和枚举类似,枚举的定义有两种方式。区别是结构体必须以“F”开头命名,而枚举不用。 额外再讲了一下蓝图生成时暴露变量的方法。 二、实现 2.1、结构体 1、定义结构体 代码如下,注意这个定义的代码一定要在“UCLASS()”…...
【android开发-19】android中内容提供者contentProvider用法讲解
1,内容URI 在Android系统中,Content URI是一种用于唯一标识和访问应用程序中的数据的方法。它由Android系统提供,通过Content Provider来实现数据的共享和访问。 Content URI使用特定的格式来标识数据,通常以"content://&qu…...
浅谈排序——快速排序(最常用的排序)
快速排序(Quick Sort)是一种常见的排序算法,由英国计算机科学家东尼霍尔(Tony Hoare)在1960年发明。这是一种分治算法,基本思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所…...
Springboot项目实现简单的文件服务器,实现文件上传+图片及文件回显
文章目录 写在前面一、配置1、application.properties2、webMvc配置3、查看效果 二、文件上传 写在前面 平常工作中的项目,上传的文件一般都会传到对象存储云服务中。当接手一个小项目,如何自己动手搭建一个文件服务器,实现图片、文件的回显…...
5V低压步进电机驱动芯片GC6150,应用于摄像机,机器人 医疗器械等产品中。具有低噪声、低振动的特点
GC6150是双通道5V低压步进电机驱动器,具有低噪声、低振动的特点,特别适用于相机变焦对焦系统、万向架、摇头机等精度、低噪声STM控制系统,该芯片为每个通道集成了一个256微步的驱动器。通过SPI & T2C接口,客户可以方使地调整驱…...
3D Web轻量引擎HOOPS Communicator如何实现对大模型的渲染支持?
除了读取轻松外,HOOPS Communicator对超大模型的支持效果也非常好,它可以支持30GB的包含70万个零件和3.5亿个三角面的Catia装配模型! 那么它是如何来实现对大模型的支持呢? 我们将从以下几个方面与大家分享:最低帧率…...
『 Linux 』进程地址空间概念
文章目录 🫙 前言🫙 进程地址空间是什么🫙 写时拷贝🫙 可执行程序中的虚拟地址🫙 物理地址分布方式 🫙 前言 在c/C中存在一种内存的概念; 一般来说一个内存的空间分布包括栈区,堆区,代码段等等; 且内存是…...
PySpark大数据处理详细教程
欢迎各位数据爱好者!今天,我很高兴与您分享我的最新博客,专注于探索 PySpark DataFrame 的强大功能。无论您是刚入门的数据分析师,还是寻求深入了解大数据技术的专业人士,这里都有丰富的知识和实用的技巧等着您。让我们…...
三(五)ts非基础类型(对象)
在ts里面定义对象的方式也有很多。 普通定义 let obj1:{} {} // obj1.name fufu 报错,只能定义为空对象且不能修改 // 但是可以在赋初始值的时候直接添加属性,这是ts在类型推断时,它会宽容地匹配对象的结构。 let obj2:{} {name: fufu}…...
HeartBeat监控Redis状态
目录 一、概述 二、 安装部署 三、配置 四、启动服务 五、查看数据 一、概述 使用heartbeat可以实现在kibana界面对redis服务存活状态进行观察,如有必要,也可在服务宕机后立即向相关人员发送邮件通知 二、 安装部署 参照文章:HeartBeat监…...
FairGuard无缝兼容小米澎湃OS、ColorOS 14 、鸿蒙4!
随着移动互联网时代的发展,各大手机厂商为打造生态系统、构建自身的技术壁垒,纷纷投身自研操作系统。 而对于一款游戏安全产品,在不同操作系统下,是否能够无缝兼容并且提供稳定的、高强度的加密保护,成了行业的一大痛…...
【Copilot】Edge浏览器的copilot消失了怎么办
这种原因,可能是因为你的ip地址的不在这个服务的允许范围内。你需要重新使用之前出现copilot的ip地址,然后退出edge的账号,重新登录一遍,最后重启edge,就能够使得copilot侧边栏重新出现了。...
C++入门【6-C++ 修饰符类型】
C 修饰符类型 C 允许在 char、int 和 double 数据类型前放置修饰符。 修饰符是用于改变变量类型的行为的关键字,它更能满足各种情境的需求。 下面列出了数据类型修饰符: signed:表示变量可以存储负数。对于整型变量来说,signe…...
STP笔记总结
STP --- 生成树协议 STP(Spanning Tree Protocol,生成树协议)是根据 IEEE802.1D标准建立的,用于在局域网中消除数据链路层环路的协议。运行STP协议的设备通过彼此交互信息发现网络中的环路,并有选择地对某些端口进行阻…...
Qt开发 之 记一次安装 Qt5.12.12 安卓环境的失败案例
文章目录 1、安装Qt2、安卓开发的组合套件2.1、CSDN地址2.2、官网地址2.3、发现老方法不适用了 3、尝试用新方法解决3.1、先安装JDK,搞定JDK环境变量3.1.1、安装jdk3.1.2、确定jdk安装路径3.1.3、打开系统环境变量配置3.1.4、配置系统环境变量3.1.5、验证JDK环境变量…...
基于SpringBoot的就业信息管理系统设计与实现(源码+数据库+文档)
摘 要 在新冠肺炎疫情的影响下,大学生的就业问题已经变成了一个引起人们普遍重视的社会焦点问题。在这次疫情的冲击之下,大学生的就业市场的供求双方都受到了不同程度的影响,大学生的就业情况并不十分乐观。目前,各种招聘平台上…...
Java面试整理(四)Java IO流
我记得自己刚开始学Java的时候,都听过师兄的分享,说IO流是很重要,而且很难。 自己正式接触之后,其实IO流这块知识并不是特别难,而且随着IT的发展,IO流这块反而用得不是很多。特别是在应用开发这个层面,用得更少。 当然,可能会有朋友跳出来说“这怎么可能?你不懂Java吧…...
《安富莱嵌入式周报》第328期:自主微型机器人,火星探测器发射前失误故障分析,微软推出12周24期免费AI课程,炫酷3D LED点阵设计,MDK5.39发布
周报汇总地址:嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 更新一期视频教程: 【实战技能】 单步运行源码分析,一期视频整明白FreeRTOS内核源码框架和运行…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
