쿨백-라이블러 발산 위한 Kd-트리

본 논문은 이론적 및 구현적 측면에서 중요한 기여를 한다. 첫째, Kd-트리가 임의의 브레그만 발산으로 측정된 거리를 사용하여 ℝ^d 공간으로 확장될 수 있음을 증명한다. 놀랍게도 이는 Kd-트리에서 정확한 가지치기를 위해 삼각 부등식이 필수가 아님을 보여준다. 둘째, 분해 가능한 브레그만 발산에 대한 최근접 이웃 탐색을 위한 효율적인 알고리즘과 C++ 구현을 제공한다. 이 구현은 확률 벡터 간의 인기 있는 거리 측정법이자 통계 및 기계 학습에서 흔히 사용되는 쿨백-라이블러 발산(상대 엔트로피)을 지원한다. 이는 계산 기하학 알고리즘의 활용 범위를 넓히는 중요한 단계이다. 벤치마크 결과는 우리의 구현이 정확하고 근사적인 최근접 이웃 쿼리 모두를 효율적으로 처리함을 보여준다. 선형 탐색과 비교하여 최대 100차원의 실용적인 시나리오에서 두 자릿수 속도 향상을 달성한다. 본 솔루션은 경쟁 방법론보다 더 간단하고 효율적이다. 이 연구는 계산 기하학의 적용 가능성을 확장하고, 특히 기계 학습 및 통계 분야에서 데이터 탐색 및 분석의 효율성을 크게 향상시킬 잠재력을 가진다.