하이퍼로그로그

1 개요

HyperLogLog

하이퍼로그로그

• 다중 집합의 고유 요소 수를 근사화하는 고유 개수 문제에 대한 알고리즘
• 다중 집합의 정확한 카디널리티를 계산하려면 카디널리티에 비례하는 메모리 양이 필요한데, 이는 매우 큰 데이터세트에는 비실용적이다.
• HyperLogLog 알고리즘과 같은 확률적 카디널리티 추정기는 카디널리티의 근사값만 얻는 비용으로 이보다 훨씬 적은 메모리를 사용한다.
• HyperLogLog 알고리즘은 1.5kB의 메모리를 사용하여 2%의 일반적인 정확도(표준 오류)로 > 10⁹의 카디널리티를 추정할 수 있다.
• HyperLogLog는 1984년 Flajolet-Martin 알고리즘에서 파생된 LogLog 알고리즘의 확장판이다다.

2 같이 보기

• Flajolet-Martin 알고리즘

3 참고

• 영어 위키백과 "HyperLogLog"
• 다음백과 "하이퍼로그로그"
• 네이버백과 "하이퍼로그로그"
• https://d2.naver.com/helloworld/711301 확률적 자료구조를 이용한 추정 - 유일한 원소 개수(Cardinality) 추정과 HyperLogLog 《NAVER D2》 2014-03-27 송기선