Locality Sensitive Hashing(LSH)이란?

1. 개요

Locality Sensitive Hashing(LSH)은 유사한 데이터를 높은 확률로 같은 해시 버킷에 매핑하여 최근접 이웃(Nearest Neighbor) 검색을 효율적으로 수행하는 기법입니다. 특히 고차원 데이터에서 브루트 포스 방식(모든 데이터와 거리 계산)보다 훨씬 빠른 검색이 가능하여 이미지 검색, 추천 시스템, 생물정보학 등의 분야에서 널리 활용됩니다.

2. 전통적인 해싱과 LSH의 차이점

일반적인 해싱(Hashing)은 서로 다른 입력 값에 대해 균등하게 해시 값을 배정하여 충돌을 최소화하는 것이 목적입니다. 그러나 LSH는 정반대로, 유사한 데이터는 같은 해시 값으로 매핑될 확률이 높고, 비슷하지 않은 데이터는 다른 해시 값으로 매핑될 확률이 높도록 설계됩니다.

	전통적 해싱	LSH
목적	충돌 최소화	유사한 데이터는 같은 버킷에 배치
활용 분야	데이터 무결성, 보안	최근접 이웃 검색, 추천 시스템
충돌 허용	낮음	의도적으로 허용

3. LSH의 핵심 개념

LSH는 다음과 같은 과정을 통해 유사한 데이터를 같은 버킷으로 매핑합니다:

1. 특정 거리 메트릭(예: 유클리드 거리, 코사인 유사도)에 대해 유사성 보존 해시 함수를 설계합니다.
2. 여러 개의 해시 함수를 조합하여 해시 테이블을 구축합니다.
3. 입력 데이터를 해시 함수에 적용하여 해시 테이블에 저장합니다.
4. 주어진 쿼리 데이터에 대해 동일한 해시 값을 갖는 데이터들을 검색합니다.

4. LSH의 주요 유형

LSH는 거리 메트릭에 따라 여러 유형이 존재합니다.

4.1 유클리드 거리 기반 LSH (E2LSH)

• 유클리드 거리(Euclidean Distance)를 기반으로 데이터가 가까울수록 같은 해시 버킷에 배치되도록 설계
• 해시 함수:
  • 여기서 는 임의의 벡터, 는 임의의 값, 는 윈도우 크기

4.2 코사인 유사도 기반 LSH

• 코사인 유사도(Cosine Similarity)를 측정하여 유사한 방향을 가진 벡터들이 같은 해시 버킷에 배치됨
• 해시 함수: 임의의 초평면을 선택하고, 데이터가 초평면의 어느 방향에 있는지를 확인 (양수/음수 여부)

5. LSH의 장점과 한계

장점

• 고차원 데이터에서 유사한 항목을 빠르게 찾을 수 있음
• 전체 데이터와 비교하는 것이 아니라, 일부 후보만 비교하므로 속도가 빠름

한계

• 정확도가 완벽하지 않음 (근사 최근접 이웃 검색)
• 데이터에 따라 적절한 해시 함수 설계가 필요함
• 해시 테이블이 여러 개 필요하여 메모리 사용량이 증가할 수 있음

6. LSH의 활용 사례

• 이미지 검색: 유사한 이미지를 빠르게 검색 (Google 이미지 검색)
• 추천 시스템: 사용자 취향과 유사한 아이템 추천
• 문서 검색: 대량의 문서에서 유사한 문서를 빠르게 찾기
• 유전자 분석: DNA 서열 비교를 위한 빠른 검색

요약

Locality Sensitive Hashing(LSH)은 고차원 공간에서 유사한 데이터를 빠르게 검색할 수 있는 강력한 기법입니다. 다양한 거리 메트릭에 따라 여러 변형이 존재하며, 이미지 검색, 추천 시스템 등 다양한 분야에서 활용되고 있습니다. 다만, 정확도를 높이기 위해 적절한 해시 함수 선택과 다중 해시 테이블 활용이 필요합니다.