HNSW (Hierarchical Navigable Small World) - 4

실제 코드

1. HNSW의 기본 개념:
   도서관에서 책을 찾는 과정으로 비유하면:

• 일반 KNN: 모든 책장을 하나씩 둘러보며 찾기
• HNSW:
  • 1층: 대표 도서 몇 권만 있는 안내데스크
  • 2층: 주요 분류별 책장
  • 3층: 모든 도서가 있는 책장
    이렇게 계층적으로 검색하여 빠르게 찾는 방식

2. 코드 상세 설명:

# m: HNSW 그래프의 각 노드당 최대 연결 수
# 마치 도서관에서 한 책에서 참조할 수 있는 다른 책의 수와 같음
for m in [8, 16, 32, 64]:
    # HNSW 인덱스 생성
    index = faiss.IndexHNSWFlat(d, m)
    
    # 시스템 안정화를 위한 3초 대기
    time.sleep(3)
    
    # 색인 시작 전 메모리와 시간 기록
    start_memory = get_memory_usage_mb()
    start_index = time.time()
    
    # 데이터 색인
    index.add(xb)
    
    # 색인 후 메모리와 시간 기록
    end_memory = get_memory_usage_mb()
    end_index = time.time()
    
    # 성능 측정 결과 출력
    print(f"M: {m} - 색인 시간: {end_index - start_index} s, 메모리 사용량: {end_memory - start_memory} MB")

    # 검색 시간 측정
    t0 = time.time()
    D, I = index.search(xq, k)
    t1 = time.time()

    # 정확도(Recall) 계산
    # gt는 실제 정답 데이터
    recall_at_1 = np.equal(I, gt[:nq, :1]).sum() / float(nq)
    print(f"{(t1 - t0) * 1000.0 / nq:.3f} ms per query, R@1 {recall_at_1:.3f}")

3. 실제 결과 예시와 해석:

M: 8 - 색인 시간: 5.2 s, 메모리 사용량: 150 MB
0.250 ms per query, R@1 0.850

M: 16 - 색인 시간: 6.5 s, 메모리 사용량: 200 MB
0.300 ms per query, R@1 0.920

M: 32 - 색인 시간: 8.0 s, 메모리 사용량: 280 MB
0.350 ms per query, R@1 0.960

M: 64 - 색인 시간: 10.5 s, 메모리 사용량: 400 MB
0.400 ms per query, R@1 0.985

이 결과에서 볼 수 있는 트레이드오프:
1. M값이 증가할수록:

• 메모리 사용량 증가
• 색인 시간 증가
• 검색 시간 증가
• 정확도(Recall) 향상

4. Recall@1의 의미:

• 예: R@1이 0.850이라면
• 1000개의 쿼리 중 850개에서 정확한 최근접 이웃을 찾았다는 의미
• 나머지 150개는 근사값(두 번째나 세 번째로 가까운 이웃)을 찾음

5. 실제 활용 사례:

• 대규모 이미지 검색 시스템
• 상품 추천 엔진
• 대규모 문서 유사도 검색

6. 이전 코드(KNN)와의 차이점:

• KNN: 100% 정확도, 하지만 느림
• HNSW: 약간의 정확도를 포기하고 매우 빠른 검색 속도

예를 들어:

• 100만 개의 데이터에서 검색 시
  • KNN: 1회 검색에 10ms
  • HNSW: 1회 검색에 0.3ms (정확도 95%)

이 알고리즘은 특히 대규모 데이터셋에서 매우 효과적이며, 약간의 정확도 손실을 감수하고 훨씬 빠른 검색 속도를 얻을 수 있습니다.