HNSW (Hierarchical Navigable Small World) - 2

네이버 쇼핑의 "비슷한 상품 찾기"를 예로 설명

1. 기본 구조:

상품 데이터 저장 방식:

각 상품을 벡터로 변환:
나이키 검은색 운동화의 경우:
- 브랜드: [1,0,0,0] (나이키)
- 색상: [0,0,1,0] (검은색)
- 카테고리: [1,0,0] (운동화)
=> 최종벡터: [1,0,0,0, 0,0,1,0, 1,0,0]

레벨별 구조:
레벨 3: 대표 상품 20개
레벨 2: 인기 상품 100개
레벨 1: 주요 상품 1000개
레벨 0: 전체 상품 100000개

2. 상품 추가 과정:

새 운동화 등록 시:

1) 벡터 변환
   상품 정보 → 숫자 벡터

2) 레벨 배정 (동전 던지기)
   레벨 0: 무조건 들어감
   레벨 1: 50% 확률
   레벨 2: 25% 확률
   레벨 3: 12.5% 확률

3) 각 레벨에서 이웃 설정
   레벨 3: 최대 4개 연결
   레벨 2: 최대 8개 연결
   레벨 1: 최대 16개 연결
   레벨 0: 최대 32개 연결

3. 검색 과정:

검색어: "검은색 나이키 운동화"

1) Query 벡터 생성:
   검색어 → [1,0,0,0, 0,0,1,0, 1,0,0]

2) 레벨 3 검색:
   - 시작점: 아디다스 운동화
   - 레벨 3 모든 상품과 거리 계산:
     * 아디다스 운동화: 거리 4.5
     * 나이키 운동화: 거리 2.8
     * 뉴발란스 운동화: 거리 5.1
   - 가장 가까운 나이키 운동화로 이동

3) 레벨 2 검색:
   - 현재 위치: 나이키 운동화
   - 주변 상품들과 거리 계산:
     * 나이키 에어맥스: 거리 2.1
     * 나이키 조던: 거리 2.4
     * 나이키 줌: 거리 2.6
   - 에어맥스로 이동

4) 레벨 1 검색:
   - 현재 위치: 에어맥스
   - 주변 상품들과 거리 계산:
     * 검은색 에어맥스: 거리 1.2
     * 흰색 에어맥스: 거리 2.5
     * 회색 에어맥스: 거리 2.3
   - 검은색 에어맥스로 이동

5) 레벨 0 검색:
   - 가장 유사한 상품들 찾기
   - 최종 결과 반환

4. 거리 계산 방법:

두 벡터 간 거리 계산:

1) 유클리디안 거리:
   √((a1-b1)² + (a2-b2)² + ...)

2) 가중치 적용:
   중요 특성에 더 높은 가중치
   - 브랜드: 0.3
   - 색상: 0.3
   - 카테고리: 0.2
   - 가격: 0.2

3) 거리 해석:
   0.0~1.0: 매우 유사
   1.0~2.0: 유사
   2.0~3.0: 관련 있음
   3.0 이상: 관련성 적음

5. 장점:

1) 빠른 검색
   - 전체 상품 대신 일부만 확인
   - 계층적 구조로 빠른 이동

2) 정확한 결과
   - 95% 이상의 정확도
   - 가장 유사한 상품 발견

3) 확장성
   - 상품 증가해도 성능 유지
   - 동적 업데이트 가능

6. 실제 활용:

1) 상품 추천
   - "비슷한 상품" 추천
   - "함께 본 상품" 추천

2) 이미지 검색
   - 유사 이미지 찾기
   - 스타일 검색

3) 가격 비교
   - 유사 상품 가격 비교
   - 최적 가격 추천

이처럼 HNSW는 계층적 구조와 효율적인 검색 방식을 통해 대규모 데이터에서도 빠르고 정확한 검색을 가능하게 합니다.