데이터 스트림의 개체 계산

스트림에서 개체를 계산하면 가장 빈번한 항목을 찾거나 일반적인 이벤트와 비정상적인 이벤트를 순위를 매길 수 있습니다. 이 알고리즘은 해시 함수와 대략적인 스케치를 활용합니다. 복제 된 오브젝트를 필터링하고 데이터 스트림에 나타난 별개의 요소를 세면 그렇게됩니다.

이 기술을 사용하면 검색 엔진에서 가장 자주 발생하는 검색어, 온라인 판매 업체의 베스트 셀러 상품, 웹 사이트의 인기 페이지 또는 가장 휘발성 인 주식 (주식이 저장된 시간 계산)과 같은 문제를 해결할 수 있습니다. 판매 및 구매).

이 문제에 대한 솔루션을 Count-Min Sketch 데이터 스트림에 적용합니다. 가능한 한 적은 정보만으로 하나의 데이터 전달 및 저장이 필요합니다. 이 알고리즘은 많은 실제 상황 (예: 네트워크 트래픽 분석 또는 분산 데이터 흐름 관리)에 적용됩니다. 이 레시피에서는 그림과 같이 블룸 필터와 비슷한 방식으로 각 비트 벡터와 연관된 해시 함수를 사용해야합니다.

1. 모든 위치에서 모든 비트 벡터를 0으로 초기화합니다.
2. 스트림에서 객체를 수신 할 때 각 비트 벡터에 해시 함수를 적용합니다. 결과 숫자 주소를 사용하여 해당 위치의 값을 증가시킵니다.
3. 객체에 해시 함수를 적용하고 객체의 빈도를 추정하라는 메시지가 표시되면 관련 위치에서 값을 검색합니다. 비트 벡터에서받은 모든 값 중에서 가장 작은 값을 스트림의 빈도로 사용합니다.

카운트 - 분 스케치에서 값이 어떻게 업데이트됩니까? 해시 함수를 사용할 때 항상 충돌이 가능하기 때문에 특히 연관된 비트 벡터에 슬롯이 적다면 여러 개의 비트 벡터를 가지고있어 적어도 하나가 올바른 값을 유지한다는 것을 확신 할 수 있습니다. 선택한 값은 충돌로 인해 잘못된 양수와 혼합되지 않기 때문에 가장 작아야합니다.