지역 민감 해싱 (locality-sensitive hashing)
한 줄 정의: 비슷한 데이터가 높은 확률로 같은 해시 버킷에 들어가도록 설계한 해시 기법으로, 빠른 유사도 검색에 쓰여요.
쉽게 풀면
보통의 해시 함수는 입력이 조금만 달라도 전혀 다른 값을 내요. 지역 민감 해싱은 반대로 비슷한 데이터가 같은 값으로 모이도록 만들어요. 그러면 수백만 개의 데이터 중에서 비슷한 것을 찾을 때 같은 버킷만 확인하면 돼서 훨씬 빨라져요.
왜 중요한가
중복 문서 탐지, 이미지·음악 검색, 추천 시스템, 임베딩 검색에서 쓰이는 근사 검색의 기본 기법이에요. 이론적 성능 보장이 있어 알고리즘 연구에서도 중요해요.
논문에서는 이렇게 쓰입니다
"MinHash 기반 지역 민감 해싱으로 1억 개 웹 문서에서 유사 중복 문서를 수 시간 안에 찾아냈다."
대규모 중복 탐지에 LSH를 쓴 전형적인 문장이에요.
조금 더 깊게 보면
Indyk과 Motwani(1998)가 근사 최근접 이웃 문제를 풀기 위해 정식화했어요. 거리 척도마다 알맞은 해시 계열이 있어서, 자카드 유사도에는 MinHash, 코사인 유사도에는 무작위 초평면(SimHash), 유클리드 거리에는 무작위 투영 방식을 써요. 해시 여러 개를 묶어 밴드를 만들고 테이블을 여러 개 두어 정밀도와 재현율의 균형을 조절해요. 최근 임베딩 검색에서는 그래프 기반 방법이 더 많이 쓰이기도 해요.
주의할 점
근사 최근접 이웃 탐색은 풀려는 문제이고, 지역 민감 해싱은 그 문제를 푸는 여러 방법 중 하나예요. 일반 해시 함수가 충돌을 피하려 하는 것과 달리 LSH는 비슷한 항목의 충돌을 일부러 유도한다는 점이 반대예요.