지역감응 해싱

컴퓨터 공학에서, 지역감응 해싱(LSH)은 유사한 입력 항목을 높은 확률의 동일한 "버킷"으로 해시하는 알고리즘 기법이다.^[1](버킷의 수는 가능한 입력 항목의 우주보다 훨씬 작다.)^[1]유사한 항목이 동일한 버킷에 포함되기 때문에 이 기법은 데이터 클러스터링과 가장 가까운 인접 검색에 사용될 수 있다.해시 충돌이 최소화되지 않고 극대화된다는 점에서 기존 해싱 기법과는 다르다.또는, 이 기법은 고차원 데이터의 차원성을 줄이는 방법으로 볼 수 있다; 고차원 입력 항목은 항목 간의 상대적 거리를 유지하면서 저차원 버전으로 축소될 수 있다.

해싱 기반 근사치 인접 검색 알고리즘은 일반적으로 해싱 방법의 두 가지 주요 범주 중 하나를 사용한다. 해싱 방법은 로컬리티 보존 해싱(LSH)과 같은 데이터 독립적 방법 또는 데이터 의존적 방법(예: LPH)이다.^[2][3]

정의들

한 LSH family[1][4][5]F{\displaystyle{{F\mathcal}}}M)(M, d){\displaystyle{{M\mathcal}미터 법 우주}=(M,d)}, 문턱 R>0{\displaystyle R>0}, 근사치 인자 c1{\displaystyle c> 1}, 확률 P1{\displaystyle P_{1}}와 P2정의된다. {\displaystyle P_${2}}$. This family ${\displaystyle {\mathcal {F}}}$ is a set of functions ${\displaystyle h\colon M\to S}$ that map elements of the metric space to buckets ${\displaystyle s\in S}$. An LSH family must satisfy the following conditions for any two points ${\displaystyle p,q\in M}$ and any hash 함수 h ${\displaystyle h}$은$($는)F {\$displaystyle$ {\mathcal ${F}$에서 임의로 선택됨:

• d( p ,q) ≤ R ${\displaystyle d(p,q)\leq R$ h( p)= h (q) ${\displaystyle h(p)=h(q)}($즉, p와 q)가 적어도 P 1{\$displaystystyle P_{1$
• 만약 d(p ,q )c c R{\$displaystyle$ d(p$,q)\geq$ cR}, 최대 P 2 ${\$$displaystyle h(p)=h(q)},$ 확률 최대 P 2 {\$displaystystyle P_{2$

> ${\$ 가족이 흥미롭다 그런 가족 F ${\$ {\\displaystyle ${\\\\mathcal${F}}}을$(R, C$ ${1},P_{2})${\$discripty}$라고 한다.

H가 확률 분포 D와 함께 기능을 함수 h∈ H{\displaystyleh\in H}선택에 결합된 해시 함수의 Alternatively[6]는 유사점 기능 ϕ 가진 항목이 U을 지닌 우주에 관해서:U×U→[0,1]{\displaystyle \phi \colon U\times U\to[0,1]}로 정의한 LSH 제도는 가족입니다.교류D에 대한 코딩은 P r h ∈ H[ () h ( ( )= h( b) = ϕ (, b ) = ( (, ) ${\displaystyle Pr_{h\in H}[h(a)=h(b$)]]의 속성을 만족시킨다$.$$=\phi (a,b)}$의 모든 a, b ∈ U ${\displaystyle a,b\in U}$에 대한 .

지역성 보존 해싱

지역성 보존 해시는 미터법 공간 M=( M, d) ${\displaystyle {\mathcal{M}=(M,d)}$의 점을 스칼라 값에 매핑하는 해시함수 f이다.

${\d(p,q)<d(q,r)\Rightarrow f(p)-f(q) < f(q)-f(r) }$

어떤 3점 p ,q , r ∈ M ${\displaystyle p,q,r\in M}$에 대하여.

즉, 이들은 입력값 사이의 상대적 거리가 출력 해시 값 사이의 상대적 거리에 보존되는 해시함수로서, 서로 더 가까운 입력값은 서로 더 가까운 출력 해시 값을 산출하게 된다.

인접 입력 간에 랜덤 출력 차이가 나도록 설계된 암호 해시함수와 체크섬과는 대조적이다.

메모리 경합과 네트워크 혼잡을 줄이기 위해 범용 해싱을 사용하는 병렬 RAM(Random-Access Machine) 알고리즘 구현에서 데이터 파이프라이닝을 용이하게 하는 방법으로 첫 번째 로컬리티 보존 해시함수 제품군이 고안되었다.^[7][8]

해시를 보존하는 지역성은 공간을 채우는 곡선과 관련이 있다.^[how?]

증폭

Given a ${\displaystyle (d_{1},d_{2},p_{1},p_{2})}$-sensitive family ${\displaystyle {\mathcal {F}}}$, we can construct new families ${\displaystyle {\mathcal {G}}}$ by either the AND-construction or OR-construction of ${\displaystyle {\mathcal {F}}}$.^[1]

AND-구성을 생성하기 위해 해시함수 g의 새로운 패밀리 G ${\$ ${\mathcal$${G}$을(를) 정의하고, 여기서 각 함수 g는 F${\$$displaystyle$ $h_{1},\dots, h_{$$k}$에서 생성된다. 그런 다음 해시함수G에 대해 그렇게 말한다.${\displaystyle g\in {\mathcal {G}}}$, ${\displaystyle g(x)=g(y)}$ if and only if all ${\displaystyle h_{i}(x)=h_{i}(y)}$ for ${\displaystyle i=1,2,\ldots ,k}$. Since the members of ${\displaystyle {\mathcal {F}}}$ are independently chosen for any G ∈ G ${\$displaystyle $g\in {\$$mathcal$ ${$$G},$ G ${\$d}, p 1k$,$ p 2k) ${\d$ 스타일$(d_{1$},$d_{2},p_{1}^{k},$p_${2}^{k}}}}}}}$ -민감한 패밀리.

OR 구성을 생성하기 위해 해시함수 g의 새로운 패밀리 G ${\$ ${\mathcal$${G}$을(를) 정의하며, 여기서 각 함수 g는 F ${\displaystyle$ $h_{1},\dots, h_{$$k}$에서 생성된다. 그런 다음 해시함수 G∈에 대해 이렇게 말한다.${\$$displaystyle$ $g\in {\$mathcal{G},<img alt="g \in \mathcal G" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/234ed606a13e83e2572c4ff4339ac7e63d4d7eae" style="vertical-align: -0.671ex; width:5.349ex; height:2.509ex;" papago-attr-id="150">g (x ) = g ( y ) {\$displaystyle$ $g(x$$)=$$g(y$$)}$의 값이 하나 이상일 경우에만 $해당된다.$Since the members of ${\displaystyle {\mathcal {F}}}$ are independently chosen for any ${\displaystyle g\in {\mathcal {G}}}$, ${\displaystyle {\mathcal {G}}}$ is a ${\displaystyle (d_{1},d_{2},1-(1-p_{1})^{k},1-(1-p_{2})^{k})$${}$ -민감한 패밀리.

적용들

LSH는 다음과 같은 몇 가지 문제 영역에 적용되었다.

• 중복에 가까운 검출^[9]
• 계층적 군집화^[10][11]
• 게놈 전체 연관성 연구^[12]
• 이미지 유사성 식별
  • 비주얼랭크
• 유전자 표현 유사성 식별^{[citation needed]}
• 오디오 유사성 식별
• 가장 가까운 이웃 검색
• 오디오 지문^[13]
• 디지털 비디오 지문 채취
• 데이터베이스 관리 시스템의^[14] 물리적 데이터 조직
• 완전히 연결된 신경망^[15][16] 훈련

• 컴퓨터 보안^[17]

방법들

해밍 거리에 대한 비트 샘플링

LSH 패밀리를 구성하는 가장 쉬운 방법 중 하나는 비트 샘플링이다.^[5]This approach works for the Hamming distance over d-dimensional vectors ${\displaystyle \{0,1\}^{d}}$. Here, the family ${\displaystyle {\mathcal {F}}}$ of hash functions is simply the family of all the projections of points on one of the ${\displaystyle d}$ coordinates, i.e., F = { h : { 0 , 1 }${\displaystyle {\mathcal {F}}=\{h\colon \{0,1\}^{d}\to \{0,1\}\mid h(x)=x_{i}{\text{ for some }}i\in \{1,\ldots ,d\}\}}$, where ${\displaystyle x_{i}}$ is the ${\displaystyle i}$th coordinate of ${\displaystyle x}$. A random function ${\dis$F ${\$의 $Playstyle h}$은(는) 입력 지점에서 무작위 비트를 선택하기만 하면 된다.이 패밀리는 P 1= 1- R/ d ${\$d $디스플레이$ 스타일 $P_{1}=1-R/d$ P 2= 1- c R/ d ${\displaystyle P_{2$}=1-cR$/d}$ 매개 변수를 가지고 있다.^{[clarification needed]}

최소 독립 순열

Suppose U is composed of subsets of some ground set of enumerable items S and the similarity function of interest is the Jaccard index J. If π is a permutation on the indices of S, for ${\displaystyle A\subseteq S}$ let ${\displaystyle h(A)=\min _{a\in A}\{\pi (a)\}}$. Each possible choice of πS의 요소에 입력 세트를 매핑하는 단일 해시 함수 h를 정의한다.

함수 패밀리 H를 모든 그러한 함수의 집합으로 정의하고 D를 균일한 분포로 한다.Given two sets ${\displaystyle A,B\subseteq S}$ the event that ${\displaystyle h(A)=h(B)}$ corresponds exactly to the event that the minimizer of π over ${\displaystyle A\cup B}$ lies inside ${\displaystyle A\cap B}$. As h was chosen uniformly at random, P r [ h ( A ) = h ( B ) ]= J( A, B) ${\$ 및(H, D) ${\$은(는) 자카드 색인에 대한 LSH 체계를 정의한다.

n 요소의 대칭 그룹은 n! 크기를 가지기 때문에 전체 대칭 그룹에서 실제로 랜덤 순열을 선택하는 것은 적당한 크기의 n에도 적합하지 않다.이러한 사실 때문에, 도메인의 각 요소가 임의로 선택한 π하에서 최소가 될 확률은 동일한 순열 패밀리인 "min-wise 독립적"인 순열 패밀리를 찾는 중요한 연구가 있었다.최소의 순열 독립적 계열이 적어도 lcml{ 1,2,…, n} e -e e -o (n ) ${\$n-o(^[18]n)}의 크기이며, 이 구속은 엄격한 것으로 확인되었다.^[19]

실제 적용하기에는 Min-wise 독립가족이 너무 크기 때문에, Min-wise 독립성에 대한 두 가지 변형 개념, 즉 제한된 Min-wise 독립가족과 대략적인 Min-wise 독립가족이 도입된다.제한된 최소값 독립성은 최소값에서 특정 세트의 카디널리티로 제한된 최소값 독립 재산이다.^[20]대략적인 최소 독립성은 재산과 기껏해야 고정된 ε에 의해 다르다.^[21]

오픈 소스 메서드

닐심사 해시

닐심사는 안티스팸 작업에 사용되는 지역성 민감 해싱 알고리즘이다.^[22]닐심사의 목표는 전자 메일 메시지의 해시 다이제스트를 생성하여 두 개의 유사한 메시지의 다이제스트가 서로 유사하도록 하는 것이다.이 논문은 닐심사가 다음과 같은 세 가지 요건을 충족시킬 것을 제안한다.

1. 각 메시지를 식별하는 요약은 자동으로 생성될 수 있는 변경에 따라 크게 달라지지 않아야 한다.
2. 인코딩은 의도적인 공격에 대해 견고해야 한다.
3. 인코딩은 잘못된 긍정의 극히 낮은 위험을 지원해야 한다.

TLSH

TLSH는 다양한 보안 및 디지털 포렌식 애플리케이션을 위해 설계된 로컬리티 민감 해싱 알고리즘이다.^[23]TLSH의 목적은 다이제스트 사이의 거리가 낮으면 해당 메시지가 비슷할 가능성이 있음을 나타내는 메시지 해시 다이제스트를 생성하는 것이다.

다양한 파일 형식에 대한 논문에서 수행된 시험은 TLSH, Ss딥 및 Sdhash와 같은 다른 유사성 다이제스트 체계와 비교할 때 Nilsimsa 해시가 거짓 양성률이 현저히 높은 것으로 확인되었다.

TLSH의 구현은 오픈 소스 소프트웨어로서 이용할 수 있다.^[24]

랜덤 투영법

모세 차리카르에^[6] 의한 LSH의 무작위 투영법은 심해시(Arccos라고도^[25] 함)라고 불리기도 한다.이 기법의 기본 개념은 처음부터 무작위 하이퍼플레인(정상 단위 벡터 r로 정의)을 선택하고 하이퍼플레인(hyperplane)을 사용하여 입력 벡터를 해시하는 것이다.

입력 벡터 v와 r에 의해 정의된 하이퍼플레인에서 h(v)= s g n (v ⋅ r) ${\displaystyle h(v)=sgn(v\cdot r)}$을(를) 허용한다.즉, h(v)=± 1 ${\displaystyle h(v)=\pm 1}$이(가) 하이퍼플레인 v의 어느 쪽이 눕느냐에 따라 달라진다.

각각의 가능한 r 선택은 단일 함수를 정의한다.H를 그러한 모든 함수의 집합으로 하고 D를 다시 한번 균일한 분포로 한다.It is not difficult to prove that, for two vectors ${\displaystyle u,v}$, ${\displaystyle Pr[h(u)=h(v)]=1-{\frac {\theta (u,v)}{\pi }}}$, where ${\displaystyle \theta (u,v)}$ is the angle between u and v. ${\displaystyle 1-{\frac {\$$teta (u,v)}{\pi }}}$은(는) coscos(u, v ) ${\displaystyle \cos(\theta (u,v)}}}$과(와) 밀접하게 관련되어 있다.

이 경우 해싱은 단 하나의 비트만 생성한다.두 벡터의 비트는 그들 사이의 각도의 코사인에 비례하는 확률과 일치한다.

안정분포

해시함수 h a ,b (υ ): R d→ N ${\$},b$}({\boldsymbol {\upsilon }}}):$${\mathcal{R}^{d}\to {\mathcal{N}}$는 d차원 벡터 vector${\${\$upsilon}}}을($를) 정수 집합에 매핑한다.패밀리의 각 해시함수는 무작위a {\$displaystyle$ \$mathbf {a}$및 b {\$displaystyle$ $b$$}$을(를) 선택하여 인덱싱되며, 여기서 ${\displaystyle$$\mathbf {a}$은(는$)$ 안정적인 분포에서 독립적으로 선택된 항목과 b {\d차원 벡터가 된다.범위[0,r]For a fixed ${\displaystyle \mathbf {a} ,b}$ the hash function ${\displaystyle h_{\mathbf {a} ,b}}$ is given by ${\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }})=\left\lfloor {\frac {\mathbf {a} \cdot {\boldsymbol {\upsilon }}+b}{r}}\right\rfloor$$}$.

해시함수에 대한 다른 구성방법은 데이터에 더 잘 맞도록 제안되었다.^[27] 특히 k-평균 해시함수는 투영기준 해시함수보다 실전에 더 좋지만 이론적 보장이 없다.

의미 해싱

의미 해싱은 입력 항목을 보다 가까운 입력이 더 높은 의미 유사성을 갖도록 어드레싱에 매핑하려는 기법이다.^[28]해시코드는 인공신경망이나 그래픽 모델의 훈련을 통해 발견된다.^{[citation needed]}

가장 가까운 인접 검색에 대한 LSH 알고리즘

LSH의 주요 응용 프로그램 중 하나는 효율적인 근접한 근접한 이웃 검색 알고리즘을 위한 방법을 제공하는 것이다.LSH 계열 F ${\$을(를) 고려하십시오. 알고리즘에는 두 가지 주요 매개변수인 폭 매개변수 k와 해시 테이블 수 L이 있다.

In the first step, we define a new family ${\displaystyle {\mathcal {G}}}$ of hash functions g, where each function g is obtained by concatenating k functions ${\displaystyle h_{1},\ldots ,h_{k}}$ from ${\displaystyle {\mathcal {F}}}$, i.e., ${\$$displaystyle g(p)=[h_{1}(p),\ldots, h_{k}(p$ 다시 말하면 F ${\$에서 무작위로 선택한 해시함수 k를 연결함으로써 랜덤 해시함수 g를 얻는 것이다. 그런 다음 알고리즘은 L 해시 테이블을 각각 랜덤함수 g에 대응한다.

사전 처리 단계에서 우리는 데이터 세트 S의 모든 n d-차원 점을 각 L 해시 테이블로 해시한다.결과 해시 테이블에는 0이 아닌 항목이 n개뿐이라는 점에서 각 해시 테이블당 사용되는 메모리 양을 표준 해시 함수를 사용하여 $){\displaystyle O(n)}$로 줄일 수 있다.

쿼리 포인트 q가 주어진 알고리즘은 L 해시 함수 g에 대해 반복된다.고려된 각 g에 대해, q와 동일한 버킷으로 해시된 데이터 포인트를 검색한다.q에서 거리 c R ${\displaystyle cR}$ 내의 점이 발견되는 즉시 프로세스가 중지된다.

매개변수 k와 L에 따라 알고리즘에는 다음과 같은 성능 보증이 있다.

• 사전 처리 시간: O(N Lk t) ${\displaystyle O(nLkt$ 여기서 t는 입력 지점 p에서 함수 h ∈ F ${\${\$mathcal {F}$을(를) 평가하기 위한 시간;
• 공간: O( n L) ${\displaystyle O(nL)}$및 데이터 지점 저장을 위한 공간.
• 쿼리 시간: O( L(k t+ d P 2k)${\displaystyle O(kt+dnP_{2}^{k$
• 알고리즘은 최소 1-(1- P 1 k)L {\$displaystyle 1-(1-P_{1}^{k$})^{{k$}}^{{$k}}}{{displaystystyle) q에서 거리 c ${\displaysty cR}$ 내에 점을 찾는 데 성공한다.$L}$;

For a fixed approximation ratio ${\displaystyle c=1+\epsilon }$ and probabilities ${\displaystyle P_{1}}$ and ${\displaystyle P_{2}}$, one can set ${\displaystyle k={\big \lceil }{\tfrac {\log n}{\log 1/P_{2}}}{\big \rceil }}$ and L = ⌈ P 1${\displaystyle L=\lceil P_{1}^{-k}\rceil =O(n^{\rho }P_{1}^{-1})}$, where ${\displaystyle \rho ={\tfrac {\log P_{1}}{\log P_{2}}}}$.그 후 다음과 같은 성과보증을 받는다.

• 사전 처리 시간: O( n 1+ ρ P 1- 1 k t) ${\displaystyle O(n^{1+\rho }}P_{1}^{-1}kt$
• 공간: O( n 1+ ρ P 1- 1) ${\displaystyle O(n^{1+\rho }}P_{1}^{-1$ 그리고 데이터 지점 저장 공간.
• 쿼리 시간: O( n ρ P 1- 1( k t+ d)${\displaystyle O(n^{\rho }}P_{1}^{1$}^{-1$}(kt+d$

개선사항

t가 크면 O(n ρ $){\displaystyle O(n^{\rho }})$부터 해싱 시간을 재사용할 수 있다.이것은 에 의해 보여졌고 그리고 그것은 주어졌다.

• 쿼리 시간: O( t log 2 ⁡( 1/ P 2)/ P 1+ n ρ(d+ 1/ P 1) ${\displaystyle$ O$(t\log ^{2}(1/P_{2})/P_{$1}}/$P_{$1}+n$^{$1}+n$^{}(d+1/P_{1})}$;
• 공간: O( 1+ ρ/ P 1 + 로그 2⁡( 1/ P 2)/ P 1 )${\displaystyle O(n^{1+\rho }}/P_{1}+\log ^{2$}(1$/P_{2}}/P_{1$

인자 1/ P 1 ${\$ 스타일$1/P_{1$}가 매우 클 수 있는 경우도 있다.예를 들어, 가장 유사한 이웃도 질의와 상당히 낮은 Jaccard 유사성 데이터를 가지고 있는 Jaccard 유사성 데이터를 예로 들 수 있다.이 그림에서는 조회 시간을 O(n ρ/ P 1 -$){\displaystyle O(n^{\rho }/P_{1}^{1-\rho }})$로 단축하는 방법과 유사하게 공간 사용량을 보여 주었다.

참고 항목

• 블룸 필터
• 차원성의 저주
• 피쳐 해싱
• 푸리에 관련 변환
• 지오하시
• 다변형 서브공간 학습
• 주성분 분석
• 랜덤 인덱싱^[32]
• 롤링 해시
• 단수 값 분해
• 스파스 분산 메모리
• 웨이브렛 압축

참조

추가 읽기

• Samet, H. (2006) 다차원 및 미터법 데이터 구조의 기초.모건 카우프만ISBN 0-12-369446-9

• Indyk, Piotr; Motwani, Rajeev; Raghavan, Prabhakar; Vempala, Santosh (1997). "Locality-preserving hashing in multidimensional spaces". Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. STOC '97. pp. 618–625. CiteSeerX 10.1.1.50.4927. doi:10.1145/258533.258656. ISBN 978-0-89791-888-6. S2CID 15693787.
• Chin, Andrew (1994). "Locality-preserving hash functions for general purpose parallel computation" (PDF). Algorithmica. 12 (2–3): 170–181. doi:10.1007/BF01185209. S2CID 18108051.

외부 링크

• 알렉스 안도니의 LSH 홈페이지
• LSHKIT: C++ 로컬리티 민감 해싱 라이브러리
• Redis를 통해 선택적으로 지속성을 지원하는 Python Locality 민감 해싱 라이브러리
• Caltech Large Scale Image Search Toolbox: Kd-Tree, 계층적 K-Means, 반전 파일 검색 알고리즘 외에 여러 LSH 해시 함수를 구현하는 Matlab 툴박스.
• 슬래시: C++ LSH 라이브러리, Terasawa, K, Tanaka, Y에 의한 구형 LSH 구현
• LSHBOX: 대규모 이미지 검색을 위한 로컬리티 민감 해싱의 오픈 소스 C++ 도구 상자, Python 및 MATLAB도 지원.
• SRS: P-stable Random Projection에 의한 In-memory의 공간효율적인 근접한 이웃 쿼리 처리 알고리즘의 C++ 구현
• Github의 TLSH 오픈 소스
• Node.js 모듈로 번들로 제공된 TLSH(Trend Micro Locality Censitive Hashing)의 JavaScript 포트
• Maven 패키지로 번들로 제공되는 TLSH(Trend Micro Locality Censitive Hashing)의 Java 포트