위키득계정 ↗
기술

하이퍼로그로그

하이퍼로그로그기술
영어
HyperLogLog
약칭
HLL
추정 대상
서로 다른 항목의 수
주요 특성
공간 절약과 근사 결과
하이퍼로그로그는 데이터에 등장한 서로 다른 항목의 수를 작은 요약 정보로 추정하는 확률적 자료구조다. 중복을 제거한 개수를 근사하며, 전체 항목 목록을 보관하는 정확한 집합과는 저장 내용과 기능이 다르다.

중복과 개수

입력이 A, B, A, C, B라면 전체 입력 횟수는 5이고 서로 다른 항목은 3개다. 하이퍼로그로그가 추정하는 것은 후자다. 특정 항목이 몇 번 나왔는지 세는 빈도 추정이나 항목이 들어 있는지 확인하는 포함 검사와 질문 자체가 다르다.

보관하지 않는 정보

정확한 집합은 항목을 다시 나열할 수 있지만 이 요약 구조는 원래 목록을 복원하기 위한 저장소가 아니다. 추정 개수가 나왔다고 해서 어떤 항목이 들어 있었는지 모두 알 수는 없다. 감사 기록이나 원본 데이터가 필요한 경우에는 이를 별도로 유지해야 한다.

여러 집합을 합칠 때

호환되는 요약들을 병합하면 합집합의 서로 다른 항목 수를 추정할 수 있다. 예를 들어 두 구간에 같은 항목이 등장할 수 있으므로 각 구간의 추정 개수를 단순히 더하면 중복이 포함된다. 병합은 합계를 더하는 연산과 구분해야 하며, 입력 식별 방식도 일관되어야 한다.

정확도와 구현

작은 공간을 쓰는 대신 결과에 통계적 오차가 생긴다. 표준 오차는 모든 입력에서 절대로 넘지 않는 최대 오차와 같은 의미가 아니다. 사용하는 구현과 설정에 따라 공간과 정확도가 달라지므로 특정 제품의 메모리 수치를 알고리즘 전체의 고정된 요구량으로 해석해서는 안 된다.

관련 문서

집합 / 자료구조 / 확률 / 메모리 / 블룸 필터 / 카운트 민 스케치 / 데이터베이스 / 합집합