95%, 99% (통계) 빠르게 계산하기

이 글은 모바일 애플리케이션 모니터링 서비스 IMQA에서 통계, 특히 백분위수(Percentile)를 빠르고 정확하게 계산하는 방법에 대한 고민에서 시작되었습니다. 기존의 백분위수 계산 방식은 모든 데이터를 수집하고 정렬해야 하므로 데이터 양이 많아질수록 시간 및 공간 복잡도가 증가하는 문제가 있습니다.

이를 해결하기 위해 VLDB19에서 소개된 DD-Sketch 자료구조를 소개하며, 이 자료구조가 모든 데이터를 가지고 있지 않아도 백분위수를 효율적으로 계산할 수 있는 원리를 탐구합니다. 또한, DD-Sketch와 유사한 알고리즘인 GKArray, HDRHistogram, T-digest 등과의 성능 비교 결과를 제시하여 데이터 분석 및 통계 처리의 성능 최적화 방안을 모색합니다.