데이터 스트림에서 요소의 수를 찾는 방법 - 꽃

Bloom 필터는 스트림에서 도착하는 객체를 추적 할 수 있지만 몇 개의 객체가 있는지 확인할 수 없습니다. 1로 채워지는 비트 벡터는 (해시 수와 충돌 확률에 따라) 같은 주소에서 해시되는 객체의 실제 수를 숨길 수 있습니다.

개체의 고유 번호를 알면 특정 웹 사이트 페이지를 본 별개 사용자의 수 또는 고유 한 검색 엔진 쿼리의 수를 파악하려는 경우와 같이 다양한 상황에서 유용합니다. 모든 요소를 ​​저장하고 그 중 중복 요소를 찾는 것은 특히 스트림에서 오는 수백만 개의 요소에서 작동하지 않습니다. 스트림에서 고유 한 객체의 수를 알고 싶다면 해시 함수를 사용해야하지만 접근 방법은 숫자 스케치를 사용하는 것입니다.

스케 칭 은 근사값을 취하는 것을 의미합니다. 즉, 정확하지는 않지만 완전히 잘못된 값이 아닙니다. 근사값은 실제 값이 너무 멀지 않으므로 근사값을 사용할 수 있습니다. 이 스마트 알고리즘에서는 확률 및 근사를 기반으로하는 HyperLogLog 를 사용하면 스트림에서 생성 된 숫자의 특성을 관찰 할 수 있습니다. HyperLogLog는 컴퓨터 과학자 인 Nigel Martin과 Philippe Flajolet의 연구에서 유래되었습니다. Flajolet는 초기 알고리즘 인 Flajolet-Martin (또는 LogLog 알고리즘)을 다음과 같이 작동하는보다 강력한 HyperLogLog 버전으로 향상 시켰습니다.

1. 해시는 스트림에서받은 모든 요소를 ​​숫자로 변환합니다.
2. 알고리즘은 숫자를 컴퓨터가 사용하는 기본 2 숫자 표준 인 이진수로 변환합니다.
3. 이 알고리즘은 이진수의 처음 0 수와 999 n 999 인 최대 수를 추적합니다. 알고리즘은 n을 사용하여 스트림에서 전달 된 개별 요소의 수를 추정한다. 구별되는 요소의 수는 2 ^ n 입니다.
4. 예를 들어, 문자열의 첫 번째 요소는 라는 단어입니다.

알고리즘은이를 정수 값으로 해시하고 결과를 01101010과 함께 2 진수로 변환합니다. 숫자의 시작 부분에 0이 하나만 나타나므로 알고리즘은이를 최대 후행 0 수로 기록합니다. 알고리즘은 이진 값이 11101011과 01101110 인

앵무새 와 늑대를 보게되며, n은 변경되지 않습니다. 그러나 단어 cat 가 통과하면 출력은 00101110이므로 n은 2가됩니다. 구별되는 요소의 수를 계산하기 위해 알고리즘은 2 ^ n, 즉 2 ^ 2 = 4를 계산합니다. 이 그림은이 과정을 보여줍니다. 앞에 오는 0 만 센다. 알고리즘의 트릭은 해시가 균등하게 분산 된 (블룸 필터 에서처럼) 이진 표현을보고 임의의 결과를 생성하는 경우 일련의 0이 나타날 확률을 계산할 수 있다는 것입니다. 단일 이진수가 0이 될 확률이 두 개 중 하나이기 때문에 0의 시퀀스 확률을 계산할 때는 0의 시퀀스 길이만큼 1/2 확률을 곱하면됩니다. 50 % 00 12로 시작하는 숫자에 대해 0 999 25 퍼센트 (1/2 * 1/2) 확률로 시작하는 숫자의 (1/2) 확률. k 제로로 시작하는 숫자에 대해 000 999 (1/2) ^ k 확률로 시작하는 숫자의 5 % (1/2 * 1/2 * 1/2) 확률 (많은 곱셈의 같은 번호)

HyperLogLog가 보는 숫자가 적을수록 부정확도가 커집니다. 서로 다른 해시 함수를 사용하여 HyperLogLog 계산을 여러 번 사용하고 각 계산의 해답을 평균하면 정확도가 높아 지지만 여러 번 해싱하는 데 시간이 오래 걸리며 스트림이 빠릅니다. 또는 동일한 해시를 사용할 수도 있지만 스트림을 그룹으로 나누는 방법 (예: 도착 순서에 따라 도착할 때 요소를 그룹으로 분리하는 방법)을 사용할 수 있으며 각 그룹에 대해 최대 후행 0 수를 추적 할 수 있습니다. 결국, 각 그룹에 대해 별개 요소 추정을 계산하고 모든 추정치의 산술 평균을 계산합니다. 이 접근법은 전체 스트림에 알고리즘을 적용하는 것보다 확률 적 평균이며 정확한 추정을 제공합니다.