hnsw algorithm

논문

• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

nsw(기반 알고리즘)

• k-NN search를 위해 greedy 알고리즘의 변형 사용

  • 한 node에서 다른 node로 방문한 적 없는 이웃 node를 선택하여 graph traverse

  • edge들의 역할

    • approximation of the Delaunay graph의 역할을 하는 short-range link들의 subset → greedy search algorithm에 필요

    • greedy search의 logarithmic scaling을 위한 long-range link의 subset.

      

  • graph construction

    • 모든 element를 연속적으로 추가하며 새로운 element에 대해 Delaunay 그래프를 이용해 가까운 이웃을 찾아 해당 element와 연결한다.
    • element들이 추가될수록 short-range link의 역할을 하던 edge들은 long-range link가 되고, navigable small world를 만든다.

  • Search algorithm

    • Basic greedy search
      1. query vertex와 entry point를 입력받아 탐색을 시작한다.
      2. entry point의 이웃 vertex들과 query 사이의 거리를 계산해 최소거리를 가진 vertex를 선택한다.
      3. query와 선택한 vertex의 거리가 현재 vertex와의 거리보다 작은 경우, 선택한 vertex를 현재 vertex로 바꾼다.
      • 위 알고리즘은 local minimum, 즉 현재 vertex의 friend 중 query와 더 가까운 vertex가 없는 경우 멈춘다.
    • k-nn search modification
      • 다른 종료조건 적용: query에 대한 k closest result가 다음 iteration에도 바뀌지 않으면 종료됨.
      • 이미 방문한 element들이 list(visitedSet)로 관리되어 중복 extraction을 방지한다.

구현체

ALGO_PARAMS

Search parameters

• ef
  - 검색 중 nearest neighbors를 저장하는 dynamic list의 크기. ef가 클수록 검색이 정확해지지만 느려진다.
  • k보다 작을 수 없다.
  • ef 값의 범위는 k~dataset size
• k
  - 쿼리 결과로 반환되는 nearest neighbors의 수
  • knn_query 함수는 nearest neighbor의 label과 각각에 대한 거리를 두 개의 numpy array로 반환한다.
  • k개만큼의 neighbor를 찾을 수 없는 경우 exception 발생

Construction parameters

• M
  - index를 만드는동안 생성되는 새로운 element에 대한 bi-directional link의 수
  • reasonable range는 2~100
  • M이 클수록 차원이 높거나 recall이 높은 데이터셋에 유리
  • 또한 M은 memory consumption을 결정한다. 대충 M * 8-10 bytes per stored element 라고 생각하면 됨
  • M을 설정해주지 않으니 무작위 vertex에서 아래와 같은 오류 발생

	Cannot return the results in a contigious 2D array. Probably ef or M is to small

• M = 64로 설정하고 해결됨

• ef_construction

  • ef와 같은 의미지만, ef_construction은 index_time/index_accuracy를 조정한다.
  • ef_construction이 클수록 construction에 오래 걸리고, index의 성능이 좋아진다.
  • 하지만 무조건 비례하는 것은 아니고, ef_construction을 증가시키는 것이 성능에 더이상 영향을 주지 못하는 지점이 있다.
    • ef_construction이 적정한지 알기 위해서는 ef = ef_construction일때 M nearest neighbor에 대한 recall을 확인하면 된다. recall이 0.9보다 낮은 경우, 개선의 여지가 있다는 의미.

• num_elements

  • index에 들어갈 element의 maximum number