가장 가까운 최적 업데이트 시간의 완전 동적 k-평균 코어셋

이 논문에서는 완전 동적 환경에서 k-중앙값 및 k-평균 클러스터링의 해를 유지하는 문제를 연구합니다. 이를 위해, 쿼리 시간에 클러스터링 솔루션을 쉽게 계산할 수 있도록 데이터셋의 압축 버전인 코어셋을 효율적으로 유지하는 알고리즘을 제시합니다. 우리의 코어셋 알고리즘은 일반 메트릭 공간에서 O (k)의 거의 최적 업데이트 시간을 가지며, 유클리드 공간 Rᵈ에서는 O (d)로 줄어듭니다. 쿼리 시간은 일반 메트릭에서 O (k²)이고, Rᵈ에서는 O (kd)입니다. 유클리드 공간에서 k-중앙값 및 k-평균 클러스터링의 상수 인자 근사를 유지하기 위해, 이는 직접적으로 알고리즘 업데이트 시간을 O (d), 쿼리 시간을 O (kd + k²)로 이끕니다. O (polylog~k) 근사를 유지하기 위해 쿼리 시간은 O (kd)로 줄어듭니다.