HyperLogLog 알고리즘은 어떻게 작동합니까?

HyperLogLog 알고리즘은 어떻게 작동합니까?

---

나는 최근에 여가 시간에 다른 알고리즘에 대해 배웠으며 매우 흥미로운 것으로 보이는 HyperLogLog 알고리즘이라고합니다.이 목록에는 몇 개의 고유 항목이 있는지 추정합니다.

이것은 "카디널리티"값을 보았을 때 MySQL 시절로 돌아 왔기 때문에 특히 흥미로 웠습니다 (최근까지는 추정되지 않은 것으로 계산 됨).

그래서 배열에 몇 개의 고유 항목이 있는지 계산하는 알고리즘을 O ( n ) 로 작성하는 방법을 알고 있습니다. 나는 이것을 JavaScript로 썼다 :

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j++) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique++;
    }
    return numUnique;
}

그러나 문제는 내 알고리즘이 O ( n ) 동안 많은 메모리를 사용한다는 것입니다 (값을에 저장 Table).

나는 O ( n ) 시간 내에 목록에서 중복을 계산 하고 최소 메모리를 사용 하는 방법에 대해이 논문을 읽었습니다 .

비트를 해시하고 계산하여 특정 확률 내에서 (목록이 고르게 분포되어 있다고 가정) 목록의 고유 항목 수를 추정 할 수 있다고 설명합니다.

논문을 읽었지만 이해할 수없는 것 같습니다. 누군가 더 평신도의 설명을 줄 수 있습니까? 해시가 무엇인지 알고 있지만이 HyperLogLog 알고리즘에서 어떻게 사용되는지 이해하지 못합니다.

---

이 알고리즘의 주요 요령은 임의의 정수 스트림을 관찰하고 이진 표현이 알려진 접두어로 시작하는 정수를 보는 경우 스트림의 카디널리티가 2 ^ (접두사의 크기) 일 가능성이 높다는 것입니다 .

즉, 임의의 정수 스트림에서 숫자의 약 50 % (2 진)는 "1"로 시작하고 25 %는 "01"로 시작하고 12,5 %는 "001"로 시작합니다. 즉, 임의 스트림을 관찰하고 "001"을 볼 경우이 스트림의 카디널리티가 8 일 가능성이 높습니다.

접두사 "00..1"에는 특별한 의미가 없습니다. 대부분의 프로세서에서 이진수로 가장 중요한 비트를 쉽게 찾을 수 있기 때문입니다.

물론 하나의 정수만 관찰하면이 값이 잘못 될 가능성이 높습니다. 이것이 알고리즘이 스트림을 "m"독립 서브 스트림으로 나누고 각 서브 스트림의 보이는 "00 ... 1"접두사의 최대 길이를 유지하는 이유입니다. 그런 다음 각 서브 스트림의 평균값을 취하여 최종 값을 추정합니다.

이것이이 알고리즘의 주요 아이디어입니다. 누락 된 세부 사항 (예 : 낮은 추정값에 대한 수정)이 있지만 모두 논문에 잘 기록되어 있습니다. 끔찍한 영어 죄송합니다.

---

HyperLogLog는 확률 적 데이터 구조 입니다. 목록에서 고유 한 요소 수를 계산합니다. 그러나 (세트를하고 요소를 세트에 추가하는) 간단한 방법과 비교하면 대략적인 방식 으로이 작업을 수행합니다.

HyperLogLog 알고리즘이이를 수행하는 방법을 살펴보기 전에 왜 필요한지 이해해야합니다. 간단한 방법의 문제점 O(distinct elements)은 공간을 소비한다는 것 입니다. 왜 별개의 요소가 아닌 큰 O 표기법이 있습니까? 요소의 크기가 다를 수 있기 때문입니다. 한 요소는 1다른 요소 일 수 있습니다 "is this big string". 따라서 거대한 목록 (또는 거대한 요소 스트림)이 있으면 많은 메모리가 필요합니다.

---

확률 계산

여러 가지 독특한 요소를 어떻게 합리적으로 추정 할 수 있습니까? 동일한 확률 m로 구성된 길이의 문자열이 있다고 가정하십시오 {0, 1}. 0으로 시작하고 2 0으로 시작하고 k 0으로 시작될 확률은 얼마입니까? 그것은1/2 , 1/4하고 1/2^k. 이것은 k0 의 문자열을 발견하면 대략 2^k요소를 살펴본 것을 의미합니다 . 이것이 좋은 출발점입니다. 균등하게 분배되는 요소의 목록을 갖는 0및 2^k - 12 진 표현 제로의 가장 큰 접두사의 최대 수를 셀 수 이것은 당신에게 합리적인 견적을 제공 할 것입니다.

문제는 0t 에서 균등하게 분포 된 숫자를 가정한다는 2^k-1것이 너무 어렵다는 것입니다 (우리가 직면 한 데이터는 대부분 숫자가 아니며 거의 균등하게 분포되지 않으며 모든 값 사이에있을 수 있지만 좋은 해싱 함수 를 사용하면 출력 비트는 균일하게 분포 될 것이고, 가장 해싱 함수 사이 출력해야 0하고2^k - 1 ( SHA1을 사용하면 사이의 값 수득 0하고 2^160지금까지 달성 우리의 최대 카디널리티 독특한 요소 수 추정 수 있다는 것을). 따라서 k만 저장하여 비트 하나의 크기 log(k)비트의 단점 단점은 추정치에 큰 차이가 있다는 것입니다.1984 년의 확률 론적 계산 지 (추정은 조금 더 똑똑하지만 여전히 가깝습니다).

LogLog

더 나아 가기 전에 우리는 왜 첫 번째 추정치가 그렇게 크지 않은지를 이해해야합니다. 그 이유는 고주파 0 접두사 요소가 한 번 무작위로 발생하여 모든 것을 망칠 수 있기 때문입니다. 그것을 향상시키는 한 가지 방법은 많은 해시 함수를 사용하는 것입니다. 각 해시 함수마다 최대 수를 계산하고 결국 평균을 계산합니다. 이것은 훌륭한 아이디어로 추정치를 향상시킬 수 있지만 LogLog 용지 는 약간 다른 접근법을 사용했습니다 (아마 해싱이 비싸기 때문에).

They used one hash but divided it into two parts. One is called a bucket (total number of buckets is 2^x) and another - is basically the same as our hash. It was hard for me to get what was going on, so I will give an example. Assume you have two elements and your hash function which gives values form 0 to 2^10 produced 2 values: 344 and 387. You decided to have 16 buckets. So you have:

0101 011000  bucket 5 will store 1
0110 000011  bucket 6 will store 4

By having more buckets you decrease the variance (you use slightly more space, but it is still tiny). Using math skills they were able to quantify the error (which is 1.3/sqrt(number of buckets)).

HyperLogLog

HyperLogLog does not introduce any new ideas, but mostly uses a lot of math to improve the previous estimate. Researchers have found that if you remove 30% of the biggest numbers from the buckets you significantly improve the estimate. They also used another algorithm for averaging numbers. The paper is math-heavy.

---

And I want to finish with a recent paper, which shows an improved version of hyperLogLog algorithm (up until now I didn't have time to fully understand it, but maybe later I will improve this answer).

---

The intuition is if your input is a large set of random number (e.g. hashed values), they should distribute evenly over a range. Let's say the range is up to 10 bit to represent value up to 1024. Then observed the minimum value. Let's say it is 10. Then the cardinality will estimated to be about 100 (10 × 100 ≈ 1024).

Read the paper for the real logic of course.

Another good explanation with sample code can be found here:
Damn Cool Algorithms: Cardinality Estimation - Nick's Blog

참고URL : https://stackoverflow.com/questions/12327004/how-does-the-hyperloglog-algorithm-work