대표적인 ANN(Approximate Nearest Neighbors) 알고리즘

LSH (Locality-Sensitive Hashing)

메모리 사용량:

• 일반적으로 중간 수준. 해시 테이블(버킷)을 만들기 위해 별도의 메모리가 필요하지만, 다른 그래프 기반 기법(HNSW) 보다는 적음
• 이유: 벡터 개수에 비례하여 버킷 구조를 구성. 해시 매핑이 단순해서 구조 자체가 복잡하지 않음

인덱싱 속도:

• 보통~빠름 수준
• 이유: 해시 함수를 적용해 벡터를 버킷에 할당하는 과정이 상대적으로 단순

검색 속도:

• 빠른 편(버킷 조회 후 후보 집합만 확인)
• 이유: 해시를 통해 데이터 공간이 미리 분할되어 있으므로, 검색 시 탐색 범위가 크게 줄어듦

정확도:

• 낮거나 중간 수준 (고차원으로 갈수록 해시 충돌이 발생하거나 정확도가 떨어질 수 있음)적용 사례:
• 이유: 동일한 해시 값이지만 실제로는 거리가 먼 벡터가 같은 버킷에 들어갈 수 있음

적용 사례:

• 매우 대규모 분산 환경에서 빠른 근사 검색이 필요한 경우 (예: 로그 스트리밍, 분산 시스템에서 단순한 유사도 탐색 등)

 

ANNOY (Approximate Nearest Neighbors Oh Yeah)

메모리 사용량:

• 중간 ~ 낮은 편 (특히, 디스크 기반 인덱스인 파일 매핑(Memory Mapping)을 활용하면 메모리를 효율적으로 쓸 수 있음)
• 이유: 검색 시 필요한 인덱스를 디스크(파일)로부터 직접 매핑하여 참조할 수 있어, 전체를 메모리에 상주시킬 필요가 없음

인덱싱 속도:

• 상대적으로 느림 (트리 여러 개를 무작위 투영 방식으로 생성해야 함)
• 이유: 각각의 트리를 무작위로 만들고, 충분한 트리 수가 있어야 검색 정확도가 올라가기 때문에 사전 구축 비용이 큼

검색 속도:

• 빠름 (여러 트리를 병렬로 탐색하고, 결과를 종합)
• 이유: 각 트리는 깊이가 비교적 작고, 무작위 투영으로 빠르게 후보를 좁힐 수 있음

정확도:

• 중간 ~ 높은 편 (트리를 많이 만들수록 정확도가 올라가지만, 그만큼 인덱스 빌드 비용 증가)

적용 사례:

• 온라인 서비스에서 미리 인덱스를 빌드해두고, 이후 실시간으로 빠른 근사 검색을 해야 하는 경우 (음악 추천, 상품 추천 등)
• 인덱스를 디스크에 보관하면서도 빠른 검색이 필요한 환경

 

HNSW (Hierarchical Navigable Small World)

메모리 사용량:

• 상대적으로 높음
• 이유: 각 벡터 간 연결(그래프 간선)을 많이 유지해야 하며, 계층적 구조 자체가 방대할 수 있음

인덱싱 속도:

• 보통
• 이유: 데이터 양이 많아질수록 계층적 그래프(스몰 월드 네트워크)를 구성해야 하므로 시간과 메모리가 많이 듦

검색 속도:

• 매우 빠름 (계층적 그래프를 통해 위 레벨에서 광범위한 탐색 → 아래 레벨에서 정교화)
• 이유: 상위 레이어에서 “큰 점프”로 전체 공간을 빠르게 축소 가능, 하위 레이어에서 미세 조정

정확도:

• 매우 높음 (ANN 알고리즘 중에서도 높은 정확도를 유지하는 것으로 잘 알려짐)
• 이유: 그래프 구조상 실제 유사 벡터들끼리 연결이 형성되어 탐색 경로가 짧고 직관적

적용 사례:

• 실시간 검색(예: 이미지 검색, 페이스 레코그니션, 개인화 추천 등)에서 높은 정확도 + 빠른 응답이 동시에 필요한 경우
• 대용량 데이터셋이라도 메모리 리소스 확보가 가능한 환경(서버 메모리를 여유 있게 쓸 수 있는 경우)

 

FAISS (Facebook AI Similarity Search)

메모리 사용량:

• 유연함 (인덱싱 옵션, 양자화 단계, 클러스터 개수 등에 따라 달라짐)
• GPU를 사용하면 그래픽 메모리가 필요하고, 양자화를 강하게 적용하면 메모리 사용량이 줄지만 정확도가 떨어짐

인덱싱 속도:

• 보통 ~ 빠름(GPU 가속 시 매우 빠름)
• 이유: Facebook이 초대규모 데이터셋에 맞춰 최적화했으며, GPU 병렬 처리를 적극 활용 가능

검색 속도:

• 매우 빠름 (특히 GPU와 병행하면 대규모 벡터에 대해 초당 수백만~수천만 쿼리 처리도 가능)
• 이유: 클러스터링 + 코스 양자화 → 후보 군을 대폭 줄인 뒤, 세밀한 검색 수행

정확도:

• 중간 ~ 높음 (양자화 방식을 얼마나 정교하게 설정하느냐에 따라 달라짐)
• 이유: 고차원 벡터를 클러스터로 분할 후, 클러스터 내부에서만 정밀 검색

적용 사례:

• 페이스북 규모의 초대형 데이터셋에서 GPU 가속을 통한 대규모 검색
• 대규모 이미지·텍스트 임베딩 검색, 얼굴 인식, 추천 시스템 등

 

ScaNN (Scalable Nearest Neighbors)

메모리 사용량:

• 중간 수준
• 이유: FAISS처럼 양자화(quantization)를 활용하되, “비등방성(Anisotropic)” 특성 때문에 일부 추가 메타데이터가 필요

인덱싱 속도:

• 보통 (벡터 양자화 과정이 필요)
• 이유: 내적(Inner Product)을 최대한 보존하도록 양자화 방식을 맞춰야 하므로 사전 계산이 꽤 들어감

검색 속도:

• 빠름
• 이유: 내적값을 잘 보존함으로써 빠른 근사 검색이 가능해지고, 후보 추려내기가 효율적

정확도:

• 상당히 높음 (내적 기반 추천에서 높은 성능)
• 이유: “가장 가까운 중심점”만 고려하는 게 아니라, 실제 내적값을 최대한 맞추는 방향으로 양자화

적용 사례:

• 내적(Inner Product) 기반 추천 시스템(광고/마케팅, 추천 모델) (ANN 은 모두 내적 기반 알고리즘이 아님) 
• 고차원 텍스트/이미지 임베딩을 빠르게 검색해야 하면서도, 정확도를 일정 수준 이상 유지해야 하는 경우