局部敏感哈希(LSH)简介

0.   Intro \textbf{0. Intro} 0. Intro

1️⃣ LSH \text{LSH} LSH的优势:在 λ \lambda{} λ较大的度量空间,也可以高效回答 c-ANN \text{c-ANN} c-ANN查询问题

2️⃣一些预备知识

  1. 多重集并集 (multi-set union):  \text{(multi-set union): } (multi-set union): 和普通并集相比区别在于保留重复项
    • 比如 Z 1 = { a , b } 和 Z 2 = { b , c } Z 1 ⇒ Z 1 ∪ Z 2 = { a , b , b , c } Z_1 = \{a, b\}和Z_2 = \{b, c\}Z_1 \Rightarrow{}Z_1\cup Z_2 = \{a, b, b,c\} Z1={a,b}Z2={b,c}Z1Z1Z2={a,b,b,c}
  2. Markov \text{Markov} Markov不等式: Pr [ X ≥ t ⋅ E [ X ] ] ≤ 1 t \text{Pr}[X \geq t \cdot \mathbf{E}[X]] \leq \frac{1}{t} Pr[XtE[X]]t1

1.   ( r , c ) -Near   Neighbor   Search \textbf{1. }(r,c)\textbf{-Near Neighbor Search} 1. (r,c)-Near Neighbor Search

1️⃣ ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN概念

image-20240731222415006
  1. r ≥ 1 r \geq 1 r1 c > 1 c > 1 c>1 S ⊆ U S\subseteq{}U SU ∣ S ∣ = n |S|=n S=n q ∈ U q \in U qU

  2. ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN查询返回: D =dist ( q , e i ) D\text{=dist}(q,e_i) D=dist(q,ei)

    image-20240803185122335
    Case \textbf{Case} Case ∃ e i 使 D ∈ [ 0 , r ] \exist{}e_i使D\in[0,r] ei使D[0,r] ∃ e i 使 D ∈ [ r , c r ] \exist{}e_i使D\in{}[r,cr] ei使D[r,cr] ∃ e i 使 D ∈ [ c r , ∞ ] \exist{}e_i使D\in[cr,\infin{}] ei使D[cr,]返回对象
    Case 1 \text{Case 1} Case 1一定可能可能满足 D ≤ c r D\leq{cr} Dcr e i e_i ei
    Case 2 \text{Case 2} Case 2不可能不可能不可能返回寂寞
    Case 3 \text{Case 3} Case 3不可能一定可能满足 D ≤ c r D\leq{cr} Dcr e i e_i ei

2️⃣引理:按以下步骤,可回答 S S S上所有 c 2 -ANN c^{2}\text{-ANN} c2-ANN查询

  1. 条件:对任意 r ≥ 1 r \geq 1 r1 c > 1 c > 1 c>1,我们已经知道了如何在 S S S上构建结构来回答 ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN查询
  2. 步骤:
    • 构建 O ( log ⁡ diam ( S ) ) O(\log \text{diam}(S)) O(logdiam(S))个这样的结构
    • 发起 O ( log ⁡ diam ( S ) ) O(\log \text{diam}(S)) O(logdiam(S)) ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN查询 ( c c c相同但 r r r不同)

2.   Locality   Sensitive   Hashing \textbf{2. Locality Sensitive Hashing} 2. Locality Sensitive Hashing

1️⃣局部敏感哈希函数定义:核心思想就是将相似的点映射进同一桶,不相似的点映射到不同桶

  1. 前提
    • r / c / p 1 / p 2 r/c/p_1/p_2 r/c/p1/p2满足 r ≥ 1 / c > 1 / 0 < p 2 < p 1 ≤ 1 r\geq{}1/c>1/0 < p_2 < p_1 \leq 1 r1/c>1/0<p2<p11
    • h h h是根据某种分布从函数族 H H H中抽取的函数
  2. 随机函数 h :  U → N h\text{: }U \rightarrow \mathbb{N} hUN ( r , c r , p 1 , p 2 ) -LSH \left(r, cr, p_1, p_2\right)\text{-LSH} (r,cr,p1,p2)-LSH函数,需满足
    • ∀ x , y ∈ U → { dist ( x , y ) ≤ r ⇒ Pr [ h ( x ) = h ( y ) ] ≥ p 1 dist ( x , y ) > c r ⇒ Pr [ h ( x ) = h ( y ) ] ≤ p 2 \forall{}x,y\in{}U\to{}\begin{cases}\text{dist}(x, y) \leq r\Rightarrow{}\text{Pr}[h(x) = h(y)] \geq p_1\\\\\text{dist}(x, y) > cr\Rightarrow{}\text{Pr}[h(x) = h(y)] \leq p_2\end{cases} x,yU dist(x,y)rPr[h(x)=h(y)]p1dist(x,y)>crPr[h(x)=h(y)]p2
    • 即两个数据靠得近( ≤ r \leq{}r r),哈希冲突到一个桶的概率就大;靠的远( > c r >cr >cr)则概率就小
  3. 此外定义 ( r , c r , p 1 , p 2 ) -LSH \left(r, cr, p_1, p_2\right)\text{-LSH} (r,cr,p1,p2)-LSH函数的对数比值为 ρ = ln ⁡ ( 1 p 1 ) ln ⁡ ( 1 p 2 ) = ln ⁡ p 1 ln ⁡ p 2 < 1 \rho = \cfrac{\ln \left(\cfrac{1}{p_1}\right)}{\ln \left(\cfrac{1}{p_2}\right)}=\cfrac{\ln{}p_1}{\ln{}p_2}<1 ρ=ln(p21)ln(p11)=lnp2lnp1<1

2️⃣放大引理:若已知如何获得 ( r , c r , p 1 , p 2 ) -LSH \left(r, cr, p_1, p_2\right)\text{-LSH} (r,cr,p1,p2)-LSH函数 h h h ∀ int  ℓ ≥ 1 \forall{\text{int }}\ell \geq 1 int 1 ( r , c r , p 1 ℓ , p 2 ℓ ) -LSH \left(r, cr, p_1^{\ell}, p_2^{\ell}\right)\text{-LSH} (r,cr,p1,p2)-LSH函数 g g g使

  1. ∀ x , g ( x ) \forall{}x,g(x) x,g(x)计算复杂度是 h ( x ) h(x) h(x) O ( ℓ ) O(\ell) O()
  2. g ( x ) g(x) g(x)空间复杂度为 O ( ℓ ) O(\ell) O()

3️⃣ LHS \text{LHS} LHS实例: ( N d , dist=Euclidean ) \left(\mathbb{N}^d,\text{dist=Euclidean})\right. (Nd,dist=Euclidean) ( r , c r , p 1 , p 2 ) -LSH \left(r, cr, p_1, p_2\right)\text{-LSH} (r,cr,p1,p2)-LSH函数

  1. 构建
    • 生成 d d d个随机变量 α 1 α 2 . . . α d \alpha_1\alpha_2...\alpha_d α1α2...αd α i ∼ N ( 0 , 1 ) \alpha_i\sim{}N(0,1) αiN(0,1)
    • β > 0 \beta > 0 β>0依赖于 c c c γ \gamma γ [ 0 , β ] [0, \beta] [0,β]中均匀随机生成
    • ∀ x ∈ N d \forall{}x\in\mathbb{N}^d xNd定义 h ( x ) = [ γ + ∑ i = 1 d ( α i ⋅ x [ i ] r ) β ] h(x)=\textbf{[}\cfrac{\gamma+\displaystyle\sum\limits_{i=1}^d\left(\cfrac{\alpha_i \cdot x[i]}{r}\right)}{\beta}\textbf{]} h(x)=[βγ+i=1d(rαix[i])]
  2. 性质: p 2 p_2 p2是一个常数,该函数的对数比值 ρ ≤ 1 c \rho\leq\cfrac{1}{c} ρc1

3.   A   Structure   for   ( r , c ) -NN   Search \textbf{3. A Structure for }(r,c)\textbf{-NN Search} 3. A Structure for (r,c)-NN Search

3.0.   Inro \textbf{3.0. Inro} 3.0. Inro

1️⃣一些前置条件

  1. S ⊆ U   ( ∣ S ∣ = n ) S\subseteq{}U\,(|S|=n) SU(S=n)
  2. 若能够构建 ρ \rho ρ ( r , c r , p 1 , p 2 ) -LSH \left(r, cr, p_1, p_2\right)\text{-LSH} (r,cr,p1,p2)-LSH函数,该结构用于在 S S S上回答 ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN查询
  3. t l s h t_{lsh} tlsh为评估 ( r , c r , p 1 , p 2 ) -LSH \left(r, cr, p_1, p_2\right)\text{-LSH} (r,cr,p1,p2)-LSH函数值所需时间

2️⃣需要证明的定理:存在这样一种结构

  1. 复杂度:
    • 空间复杂度:使用 O ( n 1 + ρ ⋅ log ⁡ 1 p 2 n ) O\left(n^{1+\rho} \cdot \log_{\frac{1}{p_2}} n\right) O(n1+ρlogp21n)个内存单元 + + +存储 O ( n 1 + ρ ) O\left(n^{1+\rho}\right) O(n1+ρ)个对象
    • 时间复杂度:查询耗时 O ( n ρ ⋅ log ⁡ 1 p 2 n ⋅ t l s h ) + O\left(n^\rho \cdot \log_{\frac{1}{p_2}} n \cdot t_{lsh}\right)+ O(nρlogp21ntlsh)+计算距离耗时 O ( n ρ ) O\left(n^\rho\right) O(nρ)
  2. 效果:能够至少以 1 10 \cfrac{1}{10} 101的概率,正确回答一次 ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN查询

3.1.   Structure \textbf{3.1. Structure} 3.1. Structure

1️⃣哈希函数 g 1 g 2 . . . g L g_1g_2...g_L g1g2...gL:令 ℓ ≥ 1 \ell \geq 1 1 L ≥ 1 L \geq 1 L1为待定的整数,则

  • 由函数 h : ( r , c r , p 1 , p 2 ) -LSH h\text{:}\left(r, cr, p_1, p_2\right)\text{-LSH} h:(r,cr,p1,p2)-LSH放大到为 L L L个独立函数 → { g 1 : ( r , c r , p 1 , p 2 ) -LSH g 2 : ( r , c r , p 1 2 , p 2 2 ) -LSH          . . . . . . .  g ℓ : ( r , c r , p 1 ℓ , p 2 ℓ ) -LSH          . . . . . . .  g L : ( r , c r , p 1 L , p 2 L ) -LSH \to\begin{cases}g_1\text{:}\left(r, cr, p_1, p_2\right)\text{-LSH}\\\\g_2\text{:}\left(r, cr, p_1^2, p_2^2\right)\text{-LSH}\\\\\,\,\,\,\,\,\,\,\text{. . . . . . . }\\g_{\ell}\text{:}\left(r, cr, p_1^{\ell}, p_2^{\ell}\right)\text{-LSH}\\\\\,\,\,\,\,\,\,\,\text{. . . . . . . }\\\\g_L\text{:}\left(r, cr, p_1^L, p_2^L\right)\text{-LSH}\end{cases} g1:(r,cr,p1,p2)-LSHg2:(r,cr,p12,p22)-LSH. . . . . . . g:(r,cr,p1,p2)-LSH. . . . . . . gL:(r,cr,p1L,p2L)-LSH

2️⃣桶定义:让所有 x ∈ S x\in{}S xS通过所有哈希函数 g i g_i gi算出哈希值,所有哈希值相同的 x x x分到一个桶里

3️⃣哈希表: T i T_i Ti收集了由 g i g_i gi哈希出来的若干非空桶,一共 L L L张哈希表 T 1 , … , T L T_1, \ldots, T_L T1,,TL 构成了我们的结构

  • 空间消耗: { 内存单元:  O ( n ⋅ L ⋅ ℓ ) 对象:  O ( n ⋅ L ) → \small\begin{cases}内存单元\text{: }O(n \cdot L \cdot \ell)\\\\对象\text{: }O(n \cdot L)\end{cases}\to{} 内存单元O(nL)对象O(nL) { ℓ = log ⁡ 1 p 2 n L = n ρ → \begin{cases}\ell{}=\log_{\frac{1}{p_2}}n\\\\L=n^{\rho}\end{cases}\to{} =logp21nL=nρ空间复杂度符合 Intro \text{Intro} Intro中的定理

3.2.   Query   \textbf{3.2. Query } 3.2. Query 

1️⃣查询信息:对 q ∈ U / S q\in{U\text{/}S} qU/S执行 ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN查询

2️⃣查询步骤

  1. q q q分别通过 g 1 g 2 . . . g L g_1g_2...g_L g1g2...gL哈希函数,分别被分进桶 g 1 ( q ) g 2 ( q ) . . . g L ( q ) g_1(q)g_2(q)...g_L(q) g1(q)g2(q)...gL(q)记作 b 1 b 2 . . . b L b_1b_2...b_L b1b2...bL
  2. Z = Z= Z= b 1 b 2 . . . b L b_1b_2...b_L b1b2...bL的多重集并集中任选 2 L + 1 2L+1 2L+1
    • 特殊情况:如果 ∑ i = 1 L ∣ b i ∣ ≤ 4 L + 1 \displaystyle\sum_{i=1}^L |b_i| \leq 4L+1 i=1Lbi4L+1,则 Z Z Z会包括所有桶的所有对象
  3. Z Z Z中找到距 q q q最近的对象 e e e,若 dist ( q , e ) ≤ c r \text{dist}(q, e) \leq cr dist(q,e)cr则返回 e e e

3️⃣查询时间: { 原子操作:  O ( t l s h ⋅ ℓ ⋅ L ) 计算距离:  O ( L ) → \small\begin{cases}原子操作\text{: }O\left(t_{lsh} \cdot \ell \cdot L\right)\\\\计算距离\text{: }O(L)\end{cases}\to{} 原子操作O(tlshL)计算距离O(L) { ℓ = log ⁡ 1 p 2 n L = n ρ → \begin{cases}\ell{}=\log_{\frac{1}{p_2}}n\\\\L=n^{\rho}\end{cases}\to{} =logp21nL=nρ时间复杂度符合 Intro \text{Intro} Intro中的定理

3.3.   Analysis   \textbf{3.3. Analysis } 3.3. Analysis 

0️⃣ Good \text{Good} Good的标准: x ∈ S x\in{S} xS good ⇔ dist ( q , x ) ≤ c r \text{good}\xLeftrightarrow{}\text{dist}(q, x) \leq c r good dist(q,x)cr 否则就为 Bad \text{Bad} Bad,算法至少返回一个 good \text{good} good才成功

1️⃣引理 1 :  1\text{: } 1查询能被正确回答,需要满足以下两个条件

  1. C 1 : \mathbf{C 1:} C1 e ∗ e^* e至少出现在 b 1 , … , b L b_1, \ldots, b_L b1,,bL中的一个
  2. C 2 : \mathbf{C 2:} C2 b 1 b 2 . . . b L b_1b_2...b_L b1b2...bL的多重集并集中,至少含有 2 L 2L 2L bad \text{bad} bad对象

2️⃣引理 2 2 2 C 1 \mathbf{C 1} C1不成立的概率小于 1 e \cfrac{1}{e} e1,即 Pr [ e ∗ ∉ ⋃ i = 1 L b i ] ≤ 1 e \text{Pr}\left[e^* \notin \displaystyle\bigcup\limits_{i=1}^L b_i\right]\leq{}\cfrac{1}{e} Pr[e/i=1Lbi]e1 ,其中这个 e = 2.718... e=2.718... e=2.718...

3️⃣引理 3 3 3 C 2 \mathbf{C 2} C2不成立的概率小于 1 2 \cfrac{1}{2} 21

🤕所以 C 1 \mathbf{C}1 C1 C 2 \mathbf{C}2 C2同时成立的概率至少为 1 − ( 1 e + 1 2 ) > 0.1 1-(\cfrac{1}{e}+\cfrac{1}{2})>0.1 1(e1+21)>0.1

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/908353.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

论文 | Evaluating the Robustness of Discrete Prompts

论文《Evaluating the Robustness of Discrete Prompts》深入探讨了离散提示&#xff08;Discrete Prompts&#xff09;的鲁棒性&#xff0c;即离散提示在自然语言处理任务中面对不同扰动时的表现。研究特别关注离散提示在自然语言推理&#xff08;NLI&#xff09;任务中的表现…

Linux 之 信号概念、进程、进程间通信、线程、线程同步

学习任务&#xff1a; 1、 信号&#xff1a;信号的分类、进程对信号的处理、向进程发送信号、信号掩码 2、 进程&#xff1a;进程与程序的概念、进程的内存布局、进程的虚拟地址空间、fork创建子进程、wait监视子进程 3、 学习进程间通信&#xff08;管道和FIFO、信号、消息队列…

Vue:模板 MVVM

Vue&#xff1a;模板 & MVVM 模板插值语法指令语法 MVVMdefineProperty数据代理 模板 Vue实例绑定一个容器&#xff0c;想要向容器中填入动态的值&#xff0c;就需要使用模板语法。模板语法分为插值语法和指令语法。 插值语法 插值语法很简单&#xff0c;使用{{}}包含一…

C++中的继承——第二篇

一、继承与友元 友元关系不能够继承&#xff08;就像父亲的朋友不一定是自己的朋友&#xff09; 具体实现起来就是父类的友元可以访问父类的成员&#xff0c;但是不可以访问子类的成员 二、继承与静态成员 子类的静态成员变量本质上与父类的是同一份&#xff0c;存储在静态…

uni-app发起请求以及请求封装,上传及下载功能(六)

文章目录 一、发起网络请求1.使用及封装2. https 请求配置自签名证书3.拦截器 二、上传下载1.上传 uni.uploadFile(OBJECT)2. 下载 uni.downloadFile(OBJECT) 一、发起网络请求 uni-app中内置的uni.request()已经很强大了&#xff0c;简单且好用。为了让其更好用&#xff0c;同…

SLAM定位总结

文章目录 一、激光定位1.A-LOAM &#xff08;2018&#xff09;2.F-LOAM &#xff08;2021&#xff09;3.CT-ICP &#xff08;2022&#xff09;3.DLO:Fast Localization with Dense Point Clouds &#xff08;2022&#xff09;4.kiss-ICP :In Defense of Point-to-Point ICP Sim…

大端存储和小端存储

大端存储和小端存储 在计算机系统中&#xff0c;数据在内存中的存储方式并不是唯一的。对于多字节的数据类型&#xff08;如 int、float 等&#xff09;&#xff0c;计算机可以以不同的方式在内存中存储它们。这些存储方式通常分为两种&#xff1a;大端存储&#xff08;Big-En…

【数据结构二叉树】C非递归算法实现二叉树的先序、中序、后序遍历

引言: 遍历二叉树&#xff1a;指按某条搜索路径巡访二叉树中每个结点&#xff0c;使得每个结点均被访问一次&#xff0c;而且仅被访问一次。 除了层次遍历外&#xff0c;二叉树有三个重要的遍历方法&#xff1a;先序遍历、中序遍历、后序遍历。 1、递归算法实现先序、中序、后…

【LeetCode】移除链表中等于设定值的元素、反转链表

主页&#xff1a;HABUO&#x1f341;主页&#xff1a;HABUO &#x1f31c;有时候世界虽然是假的&#xff0c;但并不缺少真心对待我们的人&#x1f31b; 1. 移除链表中设定值的元素 题目&#xff1a;给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所…

程序员日志之DNF手游1023版本活动补充

目录 传送门正文日志1、概要2、正文 传送门 SpringMVC的源码解析&#xff08;精品&#xff09; Spring6的源码解析&#xff08;精品&#xff09; SpringBoot3框架&#xff08;精品&#xff09; MyBatis框架&#xff08;精品&#xff09; MyBatis-Plus SpringDataJPA SpringClo…

macOS开发环境配置与应用开发教程

macOS开发环境配置与应用开发教程 引言 macOS是一个强大的操作系统&#xff0c;广泛应用于软件开发&#xff0c;尤其是iOS和macOS应用开发。本文将详细介绍如何配置macOS开发环境&#xff0c;并通过实例演示如何进行应用开发。希望通过这篇文章&#xff0c;帮助读者快速上手m…

提高交换网络可靠性之认识STP根桥与端口角色

转载请注明出处 该实验旨在学习如何选举根桥与识别端口角色。 1.三台交换机按要求连线&#xff0c;改名&#xff0c;分别为S1&#xff0c;S2&#xff0c;S3&#xff0c;以S1为例&#xff1a; 2.在S1上配置优先级为28672 同理&#xff0c;在交换机S2和S3上配置其优先级为32768&…

基于大数据的热门旅游景点数据分析系统的设计与实现

作者主页&#xff1a;编程千纸鹤 作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验&#xff0c;被多个学校常年聘为校外企业导师&#xff0c;指导学生毕业设计并参…

【大语言模型】ACL2024论文-03 MAGE: 现实环境下机器生成文本检测

【大语言模型】ACL2024论文-03 MAGE: 现实环境下机器生成文本检测 目录 文章目录 【大语言模型】ACL2024论文-03 MAGE: 现实环境下机器生成文本检测目录摘要研究背景问题与挑战如何解决核心创新点算法模型实验效果&#xff08;包含重要数据与结论&#xff09;主要参考工作后续优…

A012-基于Spring Boot的私房菜定制上门服务系统的设计与实现

摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统私房菜定制上门服务系统信息管理难度大&#xff0c;容错率…

ios 快捷指令扩展(Intents Extension)简单使用 swift语言

本文介绍使用Xcode15 建立快捷指令的Extension&#xff0c;并描述如何修改快捷指令的IntentHandler&#xff0c;带参数跳转主应用&#xff1b;以及展示多个选项的快捷指令弹框(配置intentdefinition文件)&#xff0c;点击选项带参数跳到主应用的方法 创建快捷指令 快捷指令是…

【MacOS实操】如何基于SSH连接远程linux服务器

MacOS上远程连接linux服务器&#xff0c;可以使用ssh命令pem秘钥文件连接。 一、准备pem秘钥文件 如果已经有pem文件&#xff0c;则跳过这一步。如果手上有ppk文件&#xff0c;那么需要先转换为pem文件。 macOS 的默认 SSH 客户端不支持 PPK 格式&#xff0c;你需要将 PPK 文…

Puppeteer点击系统:解锁百度流量点击率提升的解决案例

在数字营销领域&#xff0c;流量和搜索引擎优化&#xff08;SEO&#xff09;是提升网站可见性的关键。我开发了一个基于Puppeteer的点击系统&#xff0c;旨在自动化地提升百度流量点击率。本文将介绍这个系统如何通过模拟真实用户行为&#xff0c;优化关键词排名&#xff0c;并…

Golang | Leetcode Golang题解之第524题通过删除字母匹配到字典里最长单词

题目&#xff1a; 题解&#xff1a; func findLongestWord(s string, dictionary []string) (ans string) {m : len(s)f : make([][26]int, m1)for i : range f[m] {f[m][i] m}for i : m - 1; i > 0; i-- {f[i] f[i1]f[i][s[i]-a] i}outer:for _, t : range dictionary …

019集——获取CAD图中多个实体的包围盒(CAD—C#二次开发入门)

如下图所示&#xff0c;获取多个实体的最大包围盒&#xff0c;用红色线表示&#xff1a; 也可单独选圆的包围盒 部分代码如下&#xff1a; using Autodesk.AutoCAD.ApplicationServices; using Autodesk.AutoCAD.DatabaseServices; using Autodesk.AutoCAD.Geometry; using A…