HNSW (Hierarchical Navigable Small World) - 3

HNSW의 레벨 결정 과정

1. 기본 원리 (동전 던지기):

새 상품이 들어올 때:
1) 레벨 0: 무조건 들어감 (100%)
2) 레벨 1: 앞면이 나오면 진출 (50%)
3) 레벨 2: 또 앞면이 나오면 진출 (25%)
4) 레벨 3: 또 앞면이 나오면 진출 (12.5%)

예시) 나이키 운동화 등록:
- 레벨 0: 진입 (확실)
- 동전: 앞면 → 레벨 1 진입
- 동전: 앞면 → 레벨 2 진입
- 동전: 뒷면 → 레벨 3 실패
=> 레벨 2까지 진입

2. 수학적 계산:

총 상품 100,000개일 때:

레벨 0: 100,000개 (100%)
레벨 1: 50,000개 (50%)
레벨 2: 25,000개 (25%)
레벨 3: 12,500개 (12.5%)

실제 조정 후:
레벨 0: 100,000개
레벨 1: ~1,000개
레벨 2: ~100개
레벨 3: ~20개

조정 방법:
1) M = 최대 이웃 수 설정
2) 확률 p 조정 (보통 1/M)

3. 실제 구현 예시:

상수 설정:
M_max = 16  # 최대 이웃 수
m_L = 6     # 최소 이웃 수
p = 1/M_max # 상위 레벨 진출 확률

레벨 결정 함수:
def get_level(total_levels):
    level = 0
    while random() < p and level < total_levels:
        level += 1
    return level

# total_levels는 보통 log(N)으로 설정
# N: 예상되는 전체 데이터 수

4. 동적 조정:

인기도/중요도 반영:

1) 기본 진입 (동전 던지기)
   - 확률 p로 상위 레벨 진입

2) 추가 보정
   조회수 가중치:
   - 상위 10% → 레벨 +1 기회
   - 상위 1% → 레벨 +2 기회
   
   판매량 가중치:
   - 상위 10% → 레벨 +1 기회
   - 상위 1% → 레벨 +2 기회

5. 실제 예시:

나이키 에어맥스 신상품 등록:

1) 첫 등록 시:
   - 레벨 0 확정
   - 동전: 앞면 → 레벨 1 진입
   - 동전: 뒷면 → 종료
   => 레벨 1까지 진입

2) 1주일 후 (인기 상품):
   - 조회수 상위 5%
   - 판매량 상위 3%
   => 레벨 2 진입 기회 추가

3) 1달 후 (베스트셀러):
   - 조회수 상위 1%
   - 판매량 상위 1%
   => 레벨 3 진입 기회 추가

6. 레벨별 특성:

레벨 3 (최상위):
- 베스트셀러 상품
- 카테고리 대표 상품
- 높은 검색 빈도 상품

레벨 2:
- 인기 브랜드 주요 상품
- 판매량 상위 상품
- 높은 리뷰 평점 상품

레벨 1:
- 안정적인 판매 상품
- 일정 수준 이상의 상품
- 검색 빈도 중간 상품

레벨 0:
- 모든 상품 포함
- 신상품
- 판매량 저조 상품

7. 주의사항:

1) 레벨 수 결정:
   - log(N)을 기준으로 설정
   - 너무 많으면 검색 속도 저하
   - 너무 적으면 정확도 하락

2) 확률 p 조정:
   - 데이터 크기에 따라 조정
   - 상위 레벨 데이터 수 고려

3) 동적 업데이트:
   - 정기적인 레벨 재조정
   - 인기도 변화 반영
   - 시스템 부하 고려

이렇게 HNSW는 확률적인 방법과 동적 조정을 통해 효율적인 계층 구조를 만들고 유지합니다.