HNSW (Hierarchical Navigable Small World) - 5

• efConstruction: 그래프 구축 시 탐색할 이웃의 수
• 값이 클수록 더 많은 이웃을 탐색하여 정확한 그래프를 구축

# k=1: 각 쿼리당 찾을 가장 가까운 이웃의 수를 1개로 설정
k=1

# d: 입력 데이터의 차원 수
# 예: 이미지 특성이 [색상, 질감, 모양] 3차원이라면 d=3
d = xq.shape[1]

# nq: 테스트할 쿼리의 수를 1000개로 제한
nq = 1000

# 전체 쿼리 데이터에서 1000개만 선택
xq = xq[:nq]

# efConstruction: 그래프 구축 시 탐색할 이웃의 수
# 값이 클수록 더 많은 이웃을 탐색하여 정확한 그래프를 구축
for ef_construction in [40, 80, 160, 320]:
    # HNSW 인덱스 생성, M=32로 고정 (각 노드당 최대 32개 이웃 연결 가능)
    index = faiss.IndexHNSWFlat(d, 32)
    
    # efConstruction 값 설정
    # 예: ef_construction=40이면
    # 새 데이터 추가시 40개의 가장 가까운 이웃을 탐색하여 최적의 연결 구성
    index.hnsw.efConstruction = ef_construction
    
    # 시스템 안정화를 위한 3초 대기
    time.sleep(3)
    
    # 색인 전 메모리 사용량 측정
    start_memory = get_memory_usage_mb()
    
    # 색인 시작 시간 기록
    start_index = time.time()
    
    # 데이터 색인
    # 예: 이미지 데이터 [색상:0.5, 질감:0.3, 모양:0.8] 추가 시
    # ef_construction=40개의 가장 유사한 이미지를 찾아 연결 구성
    index.add(xb)
    
    # 색인 후 메모리 사용량 측정
    end_memory = get_memory_usage_mb()
    
    # 색인 종료 시간 기록
    end_index = time.time()
    
    # 결과 출력
    # 예: "efConstruction: 40 - 색인 시간: 5.2s, 메모리 사용량: 150MB"
    print(f"efConstruction: {ef_construction} - 색인 시간: {end_index - start_index} s, 메모리 사용량: {end_memory - start_memory} MB")

    # 검색 시작 시간 기록
    t0 = time.time()
    
    # 1000개의 쿼리에 대해 각각 가장 가까운 이웃 1개 검색
    # D: 거리 값 배열, I: 찾은 이웃의 인덱스 배열
    D, I = index.search(xq, k)
    
    # 검색 종료 시간 기록
    t1 = time.time()

    # 정확도(Recall) 계산
    # gt: 실제 정답 데이터
    # 예: 1000개 쿼리 중 850개 정확 → recall_at_1 = 0.85
    recall_at_1 = np.equal(I, gt[:nq, :1]).sum() / float(nq)
    
    # 쿼리당 평균 검색 시간과 정확도 출력
    # 예: "0.250 ms per query, R@1 0.850"
    print(f"{(t1 - t0) * 1000.0 / nq:.3f} ms per query, R@1 {recall_at_1:.3f}")

실제 예상 결과:

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

efConstruction: 80 - 색인 시간: 7.5s, 메모리 사용량: 150MB
0.250 ms per query, R@1 0.900

efConstruction: 160 - 색인 시간: 11.0s, 메모리 사용량: 150MB
0.250 ms per query, R@1 0.950

efConstruction: 320 - 색인 시간: 18.5s, 메모리 사용량: 150MB
0.250 ms per query, R@1 0.980

이 결과에서 알 수 있는 점:
1. efConstruction이 증가할수록:

• 색인 시간 증가 (더 많은 이웃 탐색)
• 정확도(Recall) 향상
• 메모리 사용량은 거의 동일 (그래프 구조는 M값에 의해 결정)
• 검색 시간은 거의 동일 (검색은 ef_search 값에 영향 받음)

---

HNSW에서 이웃 확인은 현재 노드와 연결된 노드들부터 시작합니다. 실제 예시로 설명드리겠습니다:

[현재 노드: 회색 고양이]
연결된 이웃들:
- 흰 고양이
- 검은 고양이
- 삼색 고양이
- 치타

1. 기본 탐색 과정:

Step 1: 현재 노드의 직접 연결된 이웃 먼저 확인
- 회색 고양이의 모든 이웃 확인
- 이웃과의 거리 계산

Step 2: 이웃의 이웃 탐색
- 더 가까운 노드가 발견되면 그쪽으로 이동
- 새로운 위치에서 다시 이웃 탐색
- 이 과정을 반복

[제한사항]
- 각 단계에서 최대 40개까지만 확인
- 이미 방문한 노드는 다시 확인하지 않음

2. 실제 탐색 예시:

[시작: 회색 고양이]
직접 연결된 이웃:
1. 흰 고양이 (확인)
2. 검은 고양이 (확인)
3. 삼색 고양이 (확인)
4. 치타 (확인)

[다음 단계]
흰 고양이의 이웃:
5. 페르시안 고양이 (확인)
6. 러시안블루 (확인)
...

검은 고양이의 이웃:
15. 팬더 (확인)
16. 재규어 (확인)
...

이런 식으로 40개까지 확인

3. 우선순위 큐 사용:

# 의사 코드
priority_queue = []  # 거리 기준으로 정렬된 큐
visited = set()     # 방문한 노드 기록

# 시작 노드의 이웃들 큐에 추가
for neighbor in current_node.neighbors:
    distance = calculate_distance(target, neighbor)
    priority_queue.push((distance, neighbor))

# 가장 가까운 이웃부터 처리
checked = 0
while checked < 40 and not priority_queue.empty():
    current = priority_queue.pop()  # 가장 가까운 이웃
    if current not in visited:
        visited.add(current)
        checked += 1
        
        # 새 이웃의 이웃들도 큐에 추가
        for new_neighbor in current.neighbors:
            if new_neighbor not in visited:
                distance = calculate_distance(target, new_neighbor)
                priority_queue.push((distance, new_neighbor))

4. 실제 검색 예시:

[목표: 검은 고양이와 유사한 이미지 찾기]

Step 1: 시작 노드(회색 고양이)의 이웃 확인
거리순 정렬:
1. 검은 고양이 (거리: 0.2)
2. 삼색 고양이 (거리: 0.4)
3. 치타 (거리: 0.5)
4. 흰 고양이 (거리: 0.7)

Step 2: 가장 가까운 '검은 고양이'의 이웃 확인
5. 팬더 (거리: 0.3)
6. 재규어 (거리: 0.4)
...

이런 식으로 계속 진행하며
총 40개 노드를 확인할 때까지 또는
더 이상 개선이 없을 때까지 진행

따라서:

• 랜덤 선택이 아님
• 현재 노드와 연결된 이웃부터 시작
• 거리가 가까운 순서대로 탐색
• 우선순위 큐로 효율적 관리
• efConstruction(40)은 이 과정에서 확인할 최대 노드 수

이렇게 진행되기 때문에 전체 데이터를 다 확인하지 않아도 효율적인 검색이 가능한 것입니다.