Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation

Meta info.

• Authors: Wentao Xiao, Yueyang Zhan, Rui Xi, Mengshu Hou, Jianming Liao
• Paper: https://arxiv.org/pdf/2407.07871
• Code: https://github.com/xwt1/ICPADS-MN-RU

TL; DR

unreachable points phenomenon을 완화하는 HNSW 기반의 MN-RU(Mutual Neighbor-Replaced Update) 알고리즘 제안

Problem States

HNSW이산업 등에서 ANN으로 가장 손쉽게 사용되는 알고리즘이나, 실시간 업데이트시 성능 크게 저하됨. 주요 원인으로 그래프 연결성이 끊어지는 unreachable points phenomenon (pic1 )가 해결 안 됨.

Suggestion

단점 보완된 HNSW 기반의 MN-RU(Mutual Neighbor-Replaced Update) 알고리즘 제안.

• 2중 구조 index 구성
  • main index: index used for regular operations
  • backup index: index managing the unreachable points
    1. query와 가장 가까운 point 식별을 위해 main index에서 K-NN 검색 수행
    2. K-NN에서 식별 안되는, unreachable points main index에서 제거
    3. main index와 별개로, unreachable point에 대한 새 HNSW 인덱스 구성 (backup index)
• dual index search: main - backup 동시 서치: main에서 unreachable point가 나타나면 backup에서 보완
• MN-RU 알고리즘
  1. Mutual Neighbor Selection: main index 업데이트하는 동안 그래프 연결성 유지
  2. Neighbor Reselection: point가 삭제되면 삭제된 포인트의 이웃과 2홉 이웃이 다시 연결되도록 하여 그래프 연결성 유지

Effects

• 3가지 시나리오에서 확인: 전 범위에서 순차적으로 iteration 돌 때마다 deletion-insertion 수행 / iteration마다 무작위 point에 대해 deletion-insertion 수행 / iteration마다 전 point deletion-insertion 수행
• long period (대량) 실시간 업데이트 개선(최대 2~4배)
• deletion-insertion 반복 수행에도 unreachable points 의 증가 억제로 전반적인 성능 개선
• dual index 구조와 동시검색을 수행함의 이점: 높은 recall을 유지하고 unreachable points 최소화