국소 민감 해싱

수치해석 통계 소프트웨어 마지막 수정: 2026-08-29 04:18:12

1. 개요[편집]

좋은 해시는 비슷한 입력을 최대한 흩뜨린다. 이건 좋은 해시가 아니다.

국소 민감 해싱(Locality-Sensitive Hashing, LSH)은 가까운 두 점이 같은 값으로 충돌할 확률이 먼 두 점보다 높도록 설계된 무작위 해시 함수족, 그리고 그 족을 증폭해 근사 최근접 이웃 질의를 푸는 알고리즘 틀이다. 인디크와 모트와니가 1998년 STOC 논문 「Approximate nearest neighbors: towards removing the curse of dimensionality」에서 제안했고, 제목이 야심을 다 말해 준다 — 차원의 저주를 없애지는 못하고 지수를 1 미만으로 깎는 것이 이 이론의 성취다.

발상의 뒤집기가 전부다. 해시 테이블의 통상적인 미덕은 균등 분산이고, 암호학적 해시는 1비트만 바뀌어도 출력이 완전히 달라지는 눈사태 효과를 목표로 한다. LSH는 그 반대를 원한다 — 입력이 조금 바뀌면 출력도 그대로이길 바란다. 그러면 “버킷을 공유한다”는 사건 자체가 “가깝다”의 증거가 되고, 질의는 해시 한 번과 버킷 하나 뒤지기로 끝난다. 문제 전체의 지도와 경쟁 기법 비교는 최근접 이웃 탐색 문서에 있고, 여기서는 해시족의 구성과 증폭, 그리고 지수 $\rho$ 를 판다.

2. 민감도의 정의[편집]

거리공간 $(\mathcal X, \delta)$ 위의 해시족 $\mathcal H$ 가 $(r_1, r_2, p_1, p_2)$ -민감하다는 것은, $h$ 를 $\mathcal H$ 에서 균등하게 뽑을 때 임의의 $p, q$ 에 대해

\delta(p,q) \le r_1 \;\Rightarrow\; \Pr_h[h(p)=h(q)] \ge p_1, \qquad \delta(p,q) \ge r_2 \;\Rightarrow\; \Pr_h[h(p)=h(q)] \le p_2

가 성립하고 $r_1 < r_2$ , $p_1 > p_2$ 인 경우를 말한다. 조건이 $r_1$ 이하와 $r_2$ 이상에서만 걸려 있다는 점을 놓치면 안 된다 — 그 사이 구간에서는 아무 약속도 하지 않는다. 그래서 LSH가 푸는 문제는 처음부터 정확 NN이 아니라 $c = r_2/r_1$ 짜리 근사 NN이고, 이 애매한 띠가 근사 인자의 정체다.

주의할 것은 $p_1$ 과 $p_2$ 의 절대값이 아니라 비다. 실제 해시족의 $p_1$ 은 0.9 같은 큰 값이 아니라 0.5 근방이거나 그 이하인 경우가 흔하고, 그래도 상관없다. 다음 절의 증폭이 격차를 얼마든지 벌려 주기 때문이다.

3. 해시족 카탈로그[편집]

거리마다 족이 따로 있고, 각각이 독립된 아이디어다.

거리·유사도	해시족	한 줄 정의
해밍 거리	비트 샘플링	좌표 하나를 무작위로 골라 그 비트를 출력
자카드 유사도	MinHash	무작위 순열에서 집합의 최솟값 원소를 출력
코사인·각도	SimHash(랜덤 초평면)	무작위 초평면의 어느 쪽인지 부호를 출력
유클리드 거리	p-안정 분포 사영	가우시안 방향으로 사영해 폭 w 로 양자화

비트 샘플링. $d$ 비트 문자열에 대해 $h_i(x) = x_i$ , $i$ 는 균등 무작위. 충돌 확률이 정확히 $1 - \delta_H(p,q)/d$ 라서 계산이 제일 깔끔하고, $\rho = 1/c$ 가 나온다. 이론 논문이 항상 여기서 출발하는 이유다.

MinHash(브로더, 1997). 집합 $A$ 에 무작위 순열 $\pi$ 를 씌우고 $h_\pi(A) = \min \pi(A)$ 로 정의하면

\Pr_\pi[h_\pi(A) = h_\pi(B)] = \frac{|A \cap B|}{|A \cup B|} = J(A,B)

가 정확히 성립한다. 증명은 한 줄이다 — $\pi$ 로 옮긴 뒤 $A \cup B$ 원소 중 가장 앞에 오는 것이 무엇이냐만 보면 되고, 그것이 $A \cap B$ 에 속할 확률이 곧 자카드 유사도다. 충돌 확률이 유사도 그 자체인 족은 흔치 않고, 그래서 MinHash 스케치는 해싱을 넘어 자카드 유사도 추정량으로도 쓰인다. 실무 구현은 진짜 순열 대신 독립 해시 함수 $k$ 개를 쓰거나, 해시 하나로 하위 $k$ 개를 취하는 bottom- $k$ 스케치를 쓴다.

SimHash(차리카르, 2002). 무작위 가우시안 벡터 $\mathbf a$ 를 뽑아 $h_{\mathbf a}(\mathbf v) = \mathrm{sign}(\mathbf a \cdot \mathbf v)$ . 두 벡터 사이각을 $\theta$ 라 하면

\Pr[h(\mathbf u) = h(\mathbf v)] = 1 - \frac{\theta(\mathbf u, \mathbf v)}{\pi}

이다. 초평면의 법선이 균등한 방향이면 두 벡터를 가르는 사건이 $\theta/\pi$ 확률이라는 2차원 논증이 그대로다.¹ 출력이 1비트뿐이라 벡터를 $b$ 비트 서명으로 압축하는 용도로도 그만이고, 서명 사이의 해밍 거리가 각도의 추정량이 된다.

p-안정 분포 사영(다타르 외, 2004). $\ell_2$ 용 표준 처방으로

h_{\mathbf a, b}(\mathbf v) = \left\lfloor \frac{\mathbf a \cdot \mathbf v + b}{w} \right\rfloor, \qquad \mathbf a \sim \mathcal N(0, I),\ b \sim \mathrm{Unif}[0, w)

를 쓴다. 가우시안이 2-안정 분포라는 성질 — $\mathbf a \cdot (\mathbf u - \mathbf v)$ 가 $\lVert \mathbf u - \mathbf v \rVert$ 배 스케일된 가우시안이 된다는 것 — 덕분에 사영값의 차이가 원래 거리에 비례하고, 그 차이가 폭 $w$ 짜리 칸 하나를 못 넘길 확률이 곧 충돌 확률이다. 무작위 오프셋 $b$ 가 칸 경계의 위치를 흐트러뜨리는 역할을 한다. $p$ 가 1이면 코시 분포로 $\ell_1$ 이 되고, 이 자리에 무작위 사영의 기계가 통째로 들어가 있다.

4. 증폭 — AND와 OR로 S자를 만든다[편집]

원시 해시 하나로는 아무것도 못 한다. $p_1 = 0.6$ , $p_2 = 0.4$ 정도의 격차로는 버킷이 데이터의 절반을 담는다. 그래서 두 방향으로 증폭한다.

AND 구성(연접). 해시 $k$ 개를 이어 붙여 $g(\cdot) = (h_1(\cdot), \dots, h_k(\cdot))$ 를 만든다. 전부 일치해야 충돌이므로 확률이 $p^k$ 로 눌린다. 격차를 벌리지만 가까운 쌍도 같이 눌린다.
OR 구성(다중 테이블). 그런 $g$ 를 $L$ 개 독립으로 만들어 테이블 $L$ 개를 세우고, 어느 하나에서라도 충돌하면 후보로 채택한다. 확률이 $1 - (1-p^k)^L$ 로 올라간다.

둘을 합치면 유사도 $s$ 에 대한 후보 채택 확률이

P(s) = 1 - \left(1 - s^{k}\right)^{L}

인 S자 곡선이 된다(MinHash처럼 충돌 확률이 곧 유사도인 족에서 이 식이 그대로 성립한다). 문서 중복 제거 문헌에서는 이 구성을 밴딩(banding)이라 부르고 $k$ 를 밴드당 행 수, $L$ 을 밴드 수라 쓴다. 변곡점, 즉 사실상의 판정 문턱은

s^\star \approx \left(\frac{1}{L}\right)^{1/k}

근방이고, $k$ 와 $L$ 을 키울수록 곡선이 그 점에서 계단에 가까워진다. “유사도 0.8 이상만 뽑고 싶다”를 $(k, L)$ 두 정수로 번역하는 것이 실무에서 LSH를 쓴다는 것의 90%다.²

5. 질의 비용과 지수 ρ[편집]

$c$ -근사 NN을 풀도록 파라미터를 정해 보자. 요령은 먼 점의 오탐이 테이블당 평균 한 개 정도가 되게 $k$ 를 잡는 것이다. 먼 점 $n$ 개가 각각 $p_2^k$ 확률로 충돌하니 $n p_2^k = O(1)$ , 즉

k = \log_{1/p_2} n \quad\Longrightarrow\quad p_1^{k} = n^{-\rho}, \qquad \rho = \frac{\ln(1/p_1)}{\ln(1/p_2)} = \frac{\log p_1}{\log p_2}

가 된다. 가까운 점을 한 테이블에서 잡을 확률이 $n^{-\rho}$ 이므로 상수 성공확률을 얻으려면 테이블이 $L = O(n^{\rho})$ 개 필요하고, 결론은

\text{질의 } O(n^{\rho} \cdot d), \qquad \text{공간 } O(n^{1+\rho} + nd)

다. $\rho < 1$ 이면 전수탐색보다 점근적으로 빠르다는 것, 그리고 그 지수를 데이터 크기와 무관하게 해시족의 두 확률만으로 계산할 수 있다는 것이 이 이론의 전부이자 아름다운 부분이다.

지수의 역사는 짧게 정리된다.

해밍 거리 비트 샘플링: $\rho = 1/c$ .
$\ell_2$ 에서 안도니·인디크(2006)가 격자 기반 해시로 $\rho \to 1/c^2$ 를 달성했고, 이후 하한 결과들이 데이터 비의존 LSH 틀 안에서는 그것이 최적임을 보였다.
안도니·라젠슈테인(2015)의 데이터 의존 해싱은 틀 자체를 넓혀 $\rho = 1/(2c^2-1)$ 로 내려갔다. 데이터 분포를 보고 해시를 고른다는 것이 요지이고, “무작위 해시가 최적”이라는 통념이 깨진 지점이다.

$c=2$ 를 넣어 보면 $\rho$ 가 0.5 → 0.25 → 0.14 로 내려간다. 그런데 이 숫자들을 실무 감각으로 옮기면 김이 좀 샌다. $c=2$ 는 “최적해의 두 배까지는 봐준다”인데, 고차원에서는 거리들이 어차피 다 비슷하므로 두 배면 사실상 아무 점이나 돌려줘도 된다는 뜻에 가깝다. 보증이 강한 구간과 실무가 원하는 구간이 어긋나 있다는 것이 이 분야의 오래된 불편함이다.

6. 실무 — 중복 제거가 진짜 무대[편집]

LSH가 가장 확실하게 값을 하는 곳은 벡터 검색이 아니라 거의 같은 것 찾기다.

웹 문서 근중복 제거. 문서를 $k$ -shingle 집합으로 바꾸고 MinHash 서명을 만든 뒤 밴딩으로 후보를 뽑는다. 브로더가 알타비스타에서 실제로 굴린 파이프라인이고, 크롤 코퍼스에서 사실상 같은 페이지 수억 쌍을 쳐내는 데 쓰였다. 구글은 나중에 64비트 SimHash 서명으로 같은 문제를 풀었다(만쿠 외, 2007). 요즘도 LLM 학습 코퍼스 정제의 표준 도구가 MinHash-LSH다.
유전체 거리 추정. 리드나 어셈블리를 $k$ -mer 집합으로 보고 MinHash 스케치로 자카드를 추정하면, 정렬 없이 게놈 수만 개의 거리 행렬이 나온다. Mash 계열 도구가 이 방식이다. 스케치가 원본의 수천분의 일이라 디스크가 아니라 이메일로 게놈을 비교하는 수준이 된다.
엔티티 해소·표절 탐지·로그 클러스터링. 전부 같은 뼈대다. 「비슷한 쌍만 골라 정밀 비교로 넘긴다」는 브로드페이즈-내로페이즈 구조이고, 이 점에서 공간 분할 자료구조의 충돌 감지 파이프라인과 정확히 같은 사고방식이다.

구현에서 자주 쓰는 개선은 멀티프로브 LSH(2007)다. 테이블 수 $L$ 을 늘려 재현율을 올리는 대신, 테이블 하나에서 질의 버킷뿐 아니라 해시값이 한두 자리만 다른 이웃 버킷까지 순서대로 열어 본다. 메모리를 한 자릿수 줄이면서 같은 재현율을 내므로, 실제 라이브러리(E2LSH, FALCONN)는 거의 항상 멀티프로브를 켠다.

7. 왜 그래프 기반에 밀렸나[편집]

2010년대 후반 이후 벡터 검색의 실무 표준은 HNSW 같은 근접 이웃 그래프이고, LSH는 벤치마크의 재현율-QPS 곡선에서 대체로 아래에 있다. 이유는 명확하다.

보증이 최악 케이스 기준이다. $\rho$ 는 어떤 데이터가 들어와도 성립하는 숫자이고, 그 대가로 실제 데이터의 구조를 하나도 이용하지 않는다. 실제 임베딩은 내재 차원이 명목 차원보다 훨씬 낮은데, 무작위 해시는 그 사실을 모른다.
메모리 상수가 크다. $O(n^{1+\rho})$ 의 지수는 예뻐 보여도 $\rho = 0.5$ 면 테이블이 $\sqrt n$ 벌이다. 십억 개면 그 자체로 재앙이다.
손잡이가 이산적이다. $(k, L)$ 은 정수라 정확도-속도 곡선을 매끄럽게 훑기 어렵다. HNSW의 $ef$ 나 IVF의 탐색 클러스터 수처럼 연속적으로 돌릴 손잡이가 없다.

그럼에도 LSH를 배워야 하는 이유는 셋이다. 첫째, 이론적 보증이 남아 있는 유일한 계열이다 — 그래프 기반이 왜 잘 되는지는 아직 아무도 증명하지 못했다. 둘째, 중복 제거처럼 문턱이 명시된 문제에서는 여전히 최선이고 분산 처리(맵리듀스 한 판)가 자연스럽다. 셋째, 부산물인 이진 서명이 곱양자화 같은 압축 계열과 곧바로 섞인다 — SimHash 비트를 만드는 회전 학습(ITQ)과 곱양자화의 회전 학습(OPQ)은 사실상 같은 최적화 문제다.³

8. 쓸 때 정해야 하는 것[편집]

거리를 먼저 확정한다. 자카드면 MinHash, 코사인이면 SimHash, $\ell_2$ 면 p-안정. 코사인을 쓸 거면 벡터를 미리 정규화해 각도 문제로 못 박아라. 거리를 안 정하고 LSH를 고르는 것은 순서가 뒤집힌 것이다.
문턱 $s^\star$ 를 숫자로 적는다. 그다음 $(k, L)$ 을 $s^\star \approx (1/L)^{1/k}$ 로 역산하고, $P(s)$ 곡선을 실제로 그려서 원하는 유사도 구간의 재현율과 오탐률을 눈으로 확인한다.
후보 검증을 반드시 붙인다. LSH는 후보를 주는 장치일 뿐, 최종 답은 원본 거리로 다시 재야 한다. 이 단계를 빼면 오탐이 그대로 결과가 된다.
$n$ 을 재 본다. 십만 개짜리 코사인 유사도라면 GPU 전수 행렬곱이 LSH 튜닝보다 빠르고 정확하다. 자료구조를 짜기 전에 전수탐색을 재는 것이 이 바닥의 첫 번째 국룰이다.

9. 관련 문서[편집]

랜덤 초평면 반올림은 원래 최근접 이웃과 무관한 곳에서 나왔다. 괴만스와 윌리엄슨이 1995년 MAX-CUT의 0.878 근사를 만들 때 반정정계획 해를 정수해로 되돌리는 도구로 쓴 것이 그것이고, 차리카르가 7년 뒤 “이거 그냥 해시로 쓰면 되잖아”를 한 셈이다. 근사 알고리즘의 반올림 기법이 검색 인프라의 부품이 되는 경로. ↩
밴딩 파라미터를 잘못 잡으면 두 가지 방식으로 조용히 망한다. $k$ 가 너무 크면 후보가 거의 안 나와서 “우리 시스템엔 중복이 없네요”라는 보고서가 나가고, $L$ 이 너무 크면 후보가 전체 쌍에 가까워져서 LSH를 끼얹은 전수탐색이 된다. 둘 다 에러 없이 돌아가는 것이 무서운 점이다. ↩
ITQ(반복 양자화, 2011)는 데이터를 회전시켜 좌표축 부호로 이진화할 때의 양자화 오차를 최소화하는 직교행렬을 찾는다. OPQ는 회전시켜 부분공간으로 쪼갤 때의 오차를 최소화하는 직교행렬을 찾는다. 둘 다 직교 프로크루스테스 문제를 반복해서 푸는 같은 골격이고, 결국 «좌표축이 데이터에 맞게 놓여 있지 않다»는 하나의 불만에서 나왔다. ↩