HyperLogLog
HyperLogLog은 대용량 자료에서 중복을 제외한 원소 수를 고정 크기에 가까운 작은 상태로 추정한다 확률적 카디널리티 추정 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용...
| 분류 | 자료구조 · 확률적 카디널리티 추정 |
|---|---|
| 목적 | 대용량 자료에서 중복을 제외한 원소 수를 고정 크기에 가까운 작은 상태로 추정한다 |
| 처리 방식 | 입력 값을 해시하고 일부 비트로 레지스터를 선택하며 남은 비트에서 처음 1이 나타나는 위치 정보를 누적한다 |
| 복잡도·성능 | 원소 처리 평균 O(1), 메모리 O(m) 레지스터; 표준오차는 대략 1.04/√m |
| 필수 조건 | 균일한 해시 분포와 적절한 레지스터 수가 필요하다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
HyperLogLog은 대용량 자료에서 중복을 제외한 원소 수를 고정 크기에 가까운 작은 상태로 추정한다 확률적 카디널리티 추정 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 입력 값을 해시하고 일부 비트로 레지스터를 선택하며 남은 비트에서 처음 1이 나타나는 위치 정보를 누적한다. 레지스터의 통계를 바탕으로 유일 원소 수의 추정치를 계산한다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 원소 처리 평균 O(1), 메모리 O(m) 레지스터; 표준오차는 대략 1.04/√m 올바르게 적용하려면 균일한 해시 분포와 적절한 레지스터 수가 필요하다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 웹 로그·데이터베이스 distinct 집계에 사용한다. 근사 결과이며 실제 원소 집합을 복원할 수는 없다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]