ParlayANN: 확장 가능하고 결정론적인 병렬 그래프 기반 근접 이웃 검색 알고리즘

근접 이웃 검색(ANNS) 알고리즘은 데이터의 고차원 벡터 공간 표현(즉, 임베딩)에 대한 효율적인 유사성 검색을 가능하게 하여 현대 딥 러닝 스택의 핵심 요소입니다. 다양한 ANNS 알고리즘 중에서 그래프 기반 알고리즘은 최고의 처리량-재현율 절충을 달성하는 것으로 알려져 있습니다. 현대 ANNS 데이터 세트의 대규모에도 불구하고, 기존의 병렬 그래프 기반 구현은 잠금 사용과 기타 순차적 병목 현상으로 인해 대규모 데이터 세트로 확장하는 데 상당한 어려움을 겪고 있습니다. 이는 1) 많은 프로세서로 효율적으로 확장하는 것을 방해하고, 2) 특정 응용 프로그램에서 바람직하지 않은 비결정론성을 초래합니다.