ANN 알고리즘, 단순 구현 넘어선 엔지니어링적 설계의 중요성
ANN(Approximate Nearest Neighbor) 알고리즘 구현 시, 알고리즘 자체보다 데이터 구조(Data Structure) 선택이 성능에 더 큰 영향을 미침
무차별 대입(Brute Force) 방식보다 느린 초기 구현의 원인은 데이터 구조의 비효율성에 있었음
성능 향상을 위해 정렬된 후보군(Sorted Candidates), 중복 방지(Duplicate Prevention), 방문 여부 확인(Visited Checks) 등 알고리즘의 핵심 불변성(Invariants)을 코드에 반영
벤치마크(Benchmark) 결과를 통해 알고리즘의 실제 성능을 검증하고, 엔지니어링적 사고의 중요성을 강조
ANN 알고리즘 구현의 핵심: 데이터 구조
게시물에서는 ANN 알고리즘 구현 시, 알고리즘 자체보다 데이터 구조(Data Structure)의 선택이 성능에 결정적인 영향을 미친다고 강조한다. 특히, Vamana 알고리즘의 경우, 정렬된 후보군(Sorted Candidates), 중복 방지(Duplicate Prevention), 방문 여부 확인(Visited Checks) 등의 핵심 불변성을 유지하는 데이터 구조를 선택하는 것이 중요하다고 언급한다. 이는 알고리즘의 효율성을 극대화하고, 무차별 대입 방식보다 빠른 성능을 확보하기 위한 핵심 요소로 작용한다.
성능 최적화를 위한 데이터 구조 설계
저자는 초기 구현에서 std::unordered_set, vector, 반복적인 정렬 및 삭제 연산을 사용함으로써 성능 저하를 겪었다고 설명한다. 이러한 문제점을 해결하기 위해, SortedBoundedVector를 사용하여 후보군을 정렬하고, 중복을 방지하며, 검색 목록 크기를 제한했다. 또한, boost::dynamic_bitset을 활용하여 방문 여부를 효율적으로 확인했다. 이러한 데이터 구조의 변경을 통해 알고리즘의 핵심 연산에 최적화된 환경을 구축했다.
벤치마크를 통한 성능 검증
게시물에서는 작은 데이터셋에서 무차별 대입 방식(Brute Force)보다 느린 초기 구현의 문제점을 지적하며, 벤치마크를 통해 성능을 검증하는 과정을 상세히 설명한다. 최적화 이후, Vamana 알고리즘은 gnews-6500.bin 데이터셋에서 5.34배의 쿼리 처리량(Query Throughput) 증가를 보였다. 이러한 벤치마크 결과는 알고리즘의 엔지니어링적 측면, 즉 데이터 구조의 중요성을 강조하는 근거로 활용된다.
엔지니어링적 사고의 중요성
저자는 알고리즘을 구현할 때, 의사 코드(Pseudocode)에 나타난 추상적인 개념(L, V, remove 등)을 단순히 구현 세부 사항으로 치부해서는 안 된다고 강조한다. 각 연산에 필요한 데이터 구조와 연산의 비용을 고려하여, 알고리즘의 핵심 불변성을 유지하는 데이터 구조를 선택해야 한다고 주장한다. 이는 알고리즘의 성능과 정확성을 확보하기 위한 엔지니어링적 사고의 핵심이라고 할 수 있다.
