[DIP] Nearest Neighbor Search: Locality Sensitive Hashing

1. Locality Sensitive Hashing (LSH)란 무엇인가?

• Locality Sensitive Hashing (LSH): 대규모 데이터셋에서 유사한 항목을 빠르게 찾기 위한 해싱 기법.
• 개발 연도: 1998년
• 대표 논문:
  • Indyk, P., & Motwani, R. "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality." Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), 1998.
  • Andoni, A. and Indyk, P. (2008) Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. Communications of the ACM, 51, 117-122.

일반 Hashing은 서로 다른 입력에 대해 고유한 해시 값을 생성하는 것을 목표로 하는 것과 달리,
LSH는 '근접한 데이터는 동일한 bucket 에 해시될 가능성이 높다'는 아이디어를 기반으로 설계됨.

• LSH는 데이터 간 유사성에 기반한 검색 속도를 크게 높임.
• 고차원의 벡터나 이미지 같은 대규모 데이터의 유사성 탐색 문제에서 매우 유용함.

---

참고: Bucket(버킷)이란?

• Hash function은 데이터를 고유한 숫자(hash value)로 매핑하는 역할을 수행하는데,
  반환된 해당 hash value는 해시 테이블의 특정 위치(즉, bucket)을 가리키는 일종의 address임.
• bucket은 동일한 hash value를 가진 여러 데이터가 저장될 수 있는 공간임.
• 데이터가 hash table에 삽입될 때, 해시 함수에 의해 특정 bucket으로 매핑됨.

예를 들어, 어떤 해시 함수가 두 개의 데이터 항목을 동일한 해시 값으로 매핑한다면, 이 두 항목은 동일한 버킷에 저장

---

2. Locality Sensitive Hashing (LSH) 설명

Locality Sensitive Hashing (위치 민감 해싱)에서는

• 여러 개의 해시 함수 집합(hash function set)을 동시에 사용하여 해싱을 구현하고,
• 이를 통해 근접 이웃(Nearest Neighbor, NN)을 찾음.

 

2-1. 여러 개의 Hash Function Set을 사용.

LSH에서는 단일 해시 함수가 아닌  여러 개의 해시 함수를 동시에 사용함.

다음과 같은 방식으로 여러 해시 함수를 결합하여 LSH가 구현됨:

1. 여러 개의 해시 함수 생성:
   • LSH에서는 기본 해시 함수 집합 $\mathcal{H} = \{h_1, h_2, \dots, h_k\}$ 을 사용.
   • 각 해시 함수 $h_i$ 는 데이터의 특정 방향으로 투영하거나, 특정한 방식으로 데이터를 나누는 역할을 수행.
   • 이 해시 함수들은 독립적으로 정의되며, 서로 다른 랜덤 파라미터 $r,b,w$ 등을 사용하여 임의로 생성.
2. 결합된 해시 버킷 만들기:
   • 각 해시 함수가 독립적으로 하나의 데이터를 해시하고, 결과적으로 나온 해시 값들을 concatenation(결합) 수행.
   • 예를 들어, 여러 해시 함수를 사용해 얻은 값들을 결합하여 하나의 큰 hash bucket 인덱스를 만들어냄.
3. 랜덤하게 해시 테이블 선택:
   • 여러 개의 해시 함수 집합을 이용해 여러 개의 해시 테이블을 만듭니다.
   • 예를 들어, $L$ 개의 서로 다른 해시 테이블을 사용하며, 각 테이블은 서로 다른 해시 함수 집합에 의해 구성됨.
   • 이 방식으로 각기 다른 해시 테이블에서 유사한 데이터가 중복해서 나타날 가능성이 높아지므로 검색 효율을 높일 수 있음.

따라서, LSH는 단일 해시 함수로 유사 항목을 찾는 것이 아니라, 여러 개의 해시 함수를 동시에 사용하여 서로 다른 해시 테이블을 만들고, 이를 결합함으로써 유사성을 검색함. 이를 통해 효율적으로 근접 이웃을 찾을 수 있게 하는 것이 LSH의 핵심 전략임.

 

여러 해시 테이블을 사용하는 LSH의 개념은
여러 개의 트리를 사용하는 k-d 트리 기반 접근법과 매우 비슷

---

2-2. LSH 해시 함수의 조건 설명

LSH의 해시 함수는 두 가지 주요 조건을 만족해야 함:

1. 가까운 점의 동일 버킷 매핑 확률

두 feature vector $\mathbf{a}$ 와 $\mathbf{b}$가 가까운 경우 ( $|\mathbf{a} -\mathbf{b}| \leq R $),

동일한 bucket 으로 해시될 확률이 높아야 함.

 

이를 수식으로 표현하면:
$$P\left(h(\mathbf{a}\right) = h(\mathbf{b})) \geq p_1$$

여기서

• $p_1$은 높은 확률 값이며, $\mathbf{a}$와 $\mathbf{b}$가 유사한 경우 해시 값이 동일할 가능성을 나타냄.

---

2. 먼 점의 동일 버킷 매핑 확률

두 feature vector $\mathbf{a}$ 와 $\mathbf{b}$가 먼 경우 ($|\mathbf{a} -\mathbf{b}| \geq cR $),

동일한 bucket으로 해시될 확률이 낮아야 함.

 

이를 수식으로 표현하면:
$$P\left(h(\mathbf{a}\right) = h(\mathbf{b})) \leq p_2$$

여기서

• $p_2$은 낮은 확률 값이며, $\mathbf{a}$와 $\mathbf{b}$가 다를 때 해시 값이 같을 가능성이 낮다는 것을 의미.

위의 두 조건은
LSH 해시 함수가
근접한 데이터는 동일한 버킷에 매핑되도록
설계됨을 보장.

---

2-3. 예제: 해시 함수

LSH에서 사용하는 해시 함수는 보통 다음과 같이 정의됨:

$$h(\mathbf{x}) = \left\lfloor \frac{\mathbf{r} \cdot \mathbf{x} + b}{w} \right\rfloor$$

 

여기서:

• $\mathbf{r}$:
  • 랜덤 벡터로, 입력 벡터 $\mathbf{x}$와 동일한 차원을 가짐.
  • 이는 입력 데이터를 랜덤하게 projection(투영)하여 해시하는 데 사용됨.
• $b$:
  • 랜덤 변수로, $ (0, w) $ 범위 내에서 선택됨.
  • 이는 해시 함수의 bias로 작용하여 해시 버킷을 결정하는 데 영향을 줌.
• $w$: 고정된 상수로, 해시 공간을 구분하는 크기.
• $ \lfloor q \rfloor $: floor 함수로, 실수 $q$보다 작거나 같은 최대 정수 값을 반환.

이 해시 함수는

• 랜덤한 방향으로 데이터를 투영하고,
• 이를 버킷으로 나누는 방식으로
• 데이터 간의 유사성을 반영하여 같은 해시 버킷에 속할 가능성을 높임.

이를 통해 비슷한 데이터들이 같은 버킷에 해시될 확률이 높아져, 검색 효율이 증가함.

---

2-4. 일반적인 Hashing과의 차이점

• LSH의 키(key)는 단일 값이 아니라 실수 벡터(real number vector)로 구성됨.
• 일반 해시 함수는 데이터를 해시 테이블에 고르게 배치하는 것이 목표: Data에 대해 Random Access를 가능하게 함.
• 이와 달리, LSH는 근접한 데이터가 동일하거나 유사한 주소값을 갖도록 하여 동일한 파티션(partition)에 위치하도록 함.

Random Access란 데이터를 특정한 인덱스를 통해 바로 접근할 수 있는 방식을 의미함.

배열(array)과 같이 고정된 인덱스를 통해 특정 위치의 데이터를 O(1) 시간에 접근할 수 있는 구조들이 random access를 지원.

https://dsaint31.me/mkdocs_site/CE/ch03_seq/ce03_02_2_RAM/#random-access-memory-ram

BME228

---

3. LSH와 Nearest Neighbor Search

Nearest Neighbor Search란

• 데이터셋 내에서 특정 쿼리 벡터와 가장 가까운 데이터를 찾는 문제임.
• 이 문제는 고차원 데이터(예: 이미지, 오디오, 문서의 특징 벡터)에서 특히 중요하며, 다양한 응용 분야에서 효율적인 검색 성능이 요구됨.

LSH (Locality Sensitive Hashing)는

• 이러한 Nearest Neighbor Search 문제를 해결하기 위해 개발된 대표적인 근사 검색 알고리즘임.
• LSH의 목표는 유사한 데이터들이 동일한 해시 버킷에 해싱될 가능성을 높이는 것임.
• LSH를 통해 데이터셋 전체를 탐색하지 않고도 근사적으로 가장 가까운 이웃을 빠르게 찾을 수 있음.

---

3-1. LSH의 주요 특징

• 근사 근접 이웃 (Approximate Nearest Neighbor, ANN) 탐색:
  • LSH는 엄밀한 근접 이웃 검색이 아니라 근사적으로 가장 가까운 이웃을 빠르게 찾는 방법으로,
  • 모든 이웃을 정확히 비교하는 것보다 훨씬 더 속도가 빠름.
• 차원의 저주 극복:
  • 고차원 데이터에서는 차원의 저주(Curse of Dimensionality) 때문에 전통적인 검색 알고리즘의 성능이 급격히 떨어짐.
  • LSH는 해시 함수를 사용하여 고차원 데이터 공간을 낮은 차원에서 효율적으로 분할하고,
  • 가까운 항목들을 동일한 해시 버킷에 할당하는 방식으로 이 문제를 극복함.
• 검색 속도 향상:
  • LSH는 데이터셋 전체를 탐색하는 대신, 쿼리 벡터와 동일한 해시 버킷에 매핑된 데이터들만을 비교하므로 검색 속도가 대폭 향상됨.
  • 특히 대규모 데이터셋에서 시간 복잡도를 획기적으로 줄일 수 있음.

---

3-2. LSH의 장단점

• 장점:
  • 고차원 데이터에서 효율적인 유사 항목 검색 가능.
  • 대규모 이미지 데이터셋 처리에 유리하며, 데이터가 너무 커서 직접 비교가 불가능한 경우 실질적 솔루션 제공.
• 단점:
  • 특정 거리 메트릭에 맞춰 설계되어야 하므로, 문제의 특성에 맞는 해시 함수를 잘 선택해야 함.
  • 정확성보다는 효율성을 중시하므로, 때로는 최적의 결과를 놓칠 수 있음. 하지만 많은 응용에서는 이러한 효율성과 적당한 정확성의 균형이 중요함.

---

3-3. DIP와 Computer Vision에서의 활용

디지털 이미지 처리(Digital Image Processing, DIP)와 컴퓨터 비전(Computer Vision)에서,
image matching problem은 두 이미지가 유사한지, 동일한 객체를 포함하고 있는지를 비교하는 과제임.

• 이미지 keypoints(예: SIFT, SURF, ORB 등)을 추출하고, 이를 이용해 두 이미지 사이의 매칭을 수행.
• keypoints는 일반적으로 high dimensional vector로 표현되며, 이들 간의 유사성을 빠르게 찾는 것이 성능에 중요함.

LSH는

• 각 이미지의 keypoints를 hash table에 저장하고,
• 새로운 이미지의 keypoints와 기존 데이터베이스의 keypoints를 매칭할 때
• 전체 데이터셋을 탐색(linear search)하는 대신
• 동일한 bucket에 매핑된 keypoints만 탐색함으로써 시간 복잡도를 줄임.

---

3-4. LSH와 다른 Nearest Neighbor Search 기법들과의 비교

3-4-1. Linear Search

• 개발 시기: 매우 초기의 알고리즘, 컴퓨터 과학의 기초로 존재해 왔음.
• 대표 논문: 특별히 지정된 논문은 없으며, 탐색의 기본적인 개념으로 이해됨.
• 활용 사례: 데이터 양이 적고, 정확성이 매우 중요한 경우 주로 사용됨.
• 현재 사용 사례: 간단한 유사 항목 검색을 위한 NumPy나 Pandas를 통한 직접 비교 수행.

2024.11.16 - [Computer/CE] - [CE] Linear Search, Naive Search, Brute Force Search

[CE] Linear Search, Naive Search, Brute Force Search

---

3-4-2. k-d Tree

• 개발 년도: 1975년
• 대표 논문: Bentley, J. L. "Multidimensional Binary Search Trees Used for Associative Searching." Communications of the ACM, 1975.
• 활용 사례: 고차원이 아닌 저차원 데이터에서 효율적으로 근접 항목을 찾는 데 사용됨. 대표적인 라이브러리는 Scikit-learn의 KDTree.
• 현재 사용 라이브러리: Scikit-learn에서 제공하는 KDTree는 저차원 데이터에 대해 자주 활용됨.

2024.11.25 - [Programming/ML] - [ML] Nearest Neighbor Search: k-d Tree

[ML] Nearest Neighbor Search: k-d Tree

---

3-4-3. K-Means Tree

• 개발 년도: 1990년대 중반
• 대표 논문: Fukunaga, K., "Introduction to Statistical Pattern Recognition", 2nd Edition, Academic Press, 1990.
• 활용 사례: 클러스터링을 기반으로 근접 항목을 찾는 구조로, 데이터셋을 계층적으로 분할하여 효율적인 검색 가능. 특히, 이미지 클러스터링 및 텍스트 클러스터링에 사용됨.
• 현재 사용 라이브러리: Faiss (Facebook에서 개발), Scikit-learn의 KMeans.

2024.11.25 - [Programming/DIP] - [DIP] K-Means Tree: Nearest Neighbor Search

[DIP] K-Means Tree: Nearest Neighbor Search

---

3-4-4. Ball Tree

• 개발 년도: 1993년
• 대표 논문: Omohundro, S. M., "Five Balltree Construction Algorithms." International Computer Science Institute, 1989.
• 활용 사례: 고차원 데이터에서 더 나은 성능을 제공하도록 설계됨. 주로 문서 클러스터링 또는 분류 작업에서 사용됨.
• 현재 사용 라이브러리: Scikit-learn에서 제공하는 BallTree.

---

3-4-5. Approximate Nearest Neighbors Oh Yeah (ANNOY)

• 개발 년도: 2013년
• 대표 논문: Erik Bernhardsson, "Annoy: Approximate Nearest Neighbors Oh Yeah", 2013
• 알고리즘 개요:
  • ANNOY는 트리 기반의 근사 최근접 이웃 탐색 알고리즘으로,
  • 여러 트리(forest)를 생성하여 메모리 사용량과 검색 속도 간의 균형을 맞춤.
  • k-d Tree와 유사한 방식으로 데이터를 반복적으로 분할하며,
  • 깊이 우선 탐색(DFS)을 통해 근사 최근접 이웃을 찾음.
• 활용 사례: Spotify 추천 시스템, 이미지 및 텍스트 유사도 검색 등에 사용됨.

장점:

• 높은 검색 속도
• 메모리 효율적 사용
• 고차원 공간에서의 우수한 성능

단점:

• 정확도가 트리 수와 랜덤성에 의존
• 특정 데이터셋에서 성능 최적화를 위한 매개변수 튜닝 필요

https://github.com/spotify/annoy

GitHub - spotify/annoy: Approximate Nearest Neighbors in C++/Python optimized for memory usage and loading/saving to disk

---

3-4-6. Hierarchical Navigable Small World (HNSW)

• 개발 년도: 2016년
• 대표 논문: Malkov, Y. A., & Yashunin, D. A. "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs." IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016.
• 활용 사례: 대규모 데이터셋에서의 근접 항목 검색을 위해 널리 사용되며, 빠른 검색 속도와 높은 정확성 제공.
• 현재 사용 라이브러리: hnswlib (Python 라이브러리로 제공됨). 특히 이미지, 오디오, 추천 시스템에서 사용됨.

Hyper-parameters에 의한 성능 차이가 있는 편이나,
앞서 살펴본 방식들보다 나은 성능을 보일 수 있음.

---

4. 결론

• Locality Sensitive Hashing (LSH)은 디지털 이미지 처리와 컴퓨터 비전 분야에서 매칭 문제를 해결하기 위한 효과적인 도구.
• 고차원 특징 벡터의 유사성을 빠르게 찾아 매칭 과정을 단축할 수 있으며, 대규모 데이터베이스를 활용하는 실시간 응용에서 유용함.
• LSH는 k-D Tree, K-Means Tree와 같은 경쟁 기법에 비해 고차원 데이터에 적합하며, Ball Tree, HNSW 등의 기법과도 보완적으로 사용 가능함.
• DIP나 컴퓨터 비전에서 이미지 매칭을 효율적으로 수행하고자 할 때 LSH나 Annoy, 또는 HNSW와 같은 도구를 활용하는 것은 매우 좋은 접근법임.

---

관련하여 읽어보면 좋은 자료들

https://ds31x.tistory.com/248

[CE] Hashing

 

https://www.scirp.org/reference/referencespapers?referenceid=1460593

Andoni, A. and Indyk, P. (2008) Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. Communicati

 

---