손실 카운트 알고리즘

손실 카운트 알고리즘은 주파수 카운트가 사용자가 지정한 임계값을 초과하는 데이터 스트림 내의 요소를 식별하는 알고리즘입니다.이 알고리즘은 빈번한 항목의 경우처럼 데이터 스트림을 '버킷'으로 분할하여 작동하지만 한 번 메인 메모리에 가능한 한 많은 버킷을 채웁니다.이 알고리즘에 의해 계산된 빈도는 항상 정확한 것은 아니지만 사용자가 지정할 수 있는 오류 임계값이 있습니다.알고리즘에 필요한 실행 시간 공간은 지정된 오류 임계값에 반비례하므로 오류가 클수록 설치 공간이 작습니다.

그것은 저명한 컴퓨터 과학자 Rajeev Motwani와 Gurmeet Singh Manku에 의해 만들어졌습니다.이 알고리즘은 네트워크 트래픽 측정, 웹 서버 로그, 클릭 스트림 등 데이터가 한정된 데이터 세트가 아닌 연속 데이터 스트림의 형태를 취하는 계산에서 큰 응용 프로그램을 찾습니다.

알고리즘.

일반적인 알고리즘의 개요는^[1] 다음과 같습니다.

• 스텝 1: 착신 데이터 스트림을 $폭{\displaystyle }$ 1${\displaystyle =}$ ${\displaystyle 1}$ /$${\ { $displaystyle$ w =$1$/ \ $ipsilon$ $\}$의 버킷으로 분할합니다.여기서 $사용자$는$$"\ $displaystyle$\ $ipsilon$}을$$(최소 지원 $임계값{\displaystyle }$ = $"\$ $displaystyle$\ ipsilon $}$과 함께) 에러 바인딩으로 언급합니다.
• 2단계: 새 버킷 값에 따라 각 항목의 주파수 카운트를 증가시킵니다.각 버킷 후에 모든 카운터를 1씩 줄입니다.
• 스텝 3: 반복: 카운터를 갱신하고 각 버킷 후에 모든 카운터를 1씩 줄입니다.

레퍼런스

이 컴퓨터 과학 기사는 촌스럽다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.

• v
• t