HNSW (Hierarchical Navigable Small World) - 6

이 코드는 HNSW에서 검색 시 탐색할 이웃의 수(efSearch)를 변경하며 성능을 테스트하는 코드입니다.

# ef_search: 검색 시 각 계층에서 탐색할 후보 노드의 수
for ef_search in [16, 32, 64, 128]:
    # 검색 파라미터 설정
    index.hnsw.efSearch = ef_search

    # 검색 시작 시간 기록
    t0 = time.time()
    
    # 1000개의 쿼리에 대해 검색 수행
    # D: 찾은 이웃까지의 거리
    # I: 찾은 이웃의 인덱스
    D, I = index.search(xq, k)
    
    # 검색 종료 시간 기록
    t1 = time.time()

    # 정확도 계산
    # gt: 실제 가장 가까운 이웃(ground truth)
    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}")

실제 검색 과정 예시:

1. efSearch = 16인 경우:

쿼리: "검은 고양이 이미지"

[검색 과정]
시작 노드: 흰 고양이
확인할 이웃: 최대 16개

Step 1: 현재 이웃 확인
- 회색 고양이 (거리: 0.5)
- 삼색 고양이 (거리: 0.6)
... (최대 16개)

결과: 80% 정확도, 0.2ms/쿼리

2. efSearch = 64인 경우:

쿼리: 동일한 "검은 고양이 이미지"

[검색 과정]
시작 노드: 흰 고양이
확인할 이웃: 최대 64개

Step 1: 더 많은 이웃 확인
- 회색 고양이 (거리: 0.5)
- 삼색 고양이 (거리: 0.6)
- 치타 (거리: 0.7)
... (최대 64개)

결과: 95% 정확도, 0.4ms/쿼리

예상되는 전체 결과:

efSearch: 16 - 0.200 ms per query, R@1 0.800
efSearch: 32 - 0.300 ms per query, R@1 0.900
efSearch: 64 - 0.400 ms per query, R@1 0.950
efSearch: 128 - 0.500 ms per query, R@1 0.980

주요 특징:
1. efSearch가 증가할수록:

• 더 많은 이웃을 탐색
• 검색 시간 증가
• 정확도(Recall) 향상

2. 트레이드오프:

   • 낮은 efSearch: 빠른 검색, 낮은 정확도
   • 높은 efSearch: 느린 검색, 높은 정확도

3. 실제 서비스에서:

   • 실시간 검색이 중요하면 낮은 efSearch
   • 정확도가 중요하면 높은 efSearch
   • 보통 32~64 정도가 좋은 균형점

이는 마치 도서관에서 책을 찾을 때:

• efSearch = 16: 빠르게 둘러보고 비슷한 책 선택
• efSearch = 128: 꼼꼼하게 많은 책을 비교하여 선택
  하는 것과 유사합니다.