사용자는 최소 지원 임계값, σ 및 ε으로 표시된 이전에 바인딩된 오류를 포함하는 두 가지 입력 매개변수를 지원합니다. 들어오는 스트림은 이론적으로 w =[1/ε] 너비의 버킷으로 나뉩니다.
N을 현재 스트림 길이, 즉 지금까지 본 항목 수라고 합니다. 알고리즘은 빈도가 0보다 높은 모든 요소에 대한 빈도 목록 데이터 구조가 필요합니다. 모든 항목에 대해 목록은 대략적인 빈도 수인 f와 f의 가능한 최대 오류인 ∆를 지원합니다.
다음과 같이 항목의 알고리즘 절차 버킷. 새 버킷이 도착하면 버킷의 항목이 빈도 목록에 삽입됩니다. 주어진 항목이 목록에 존재하면 단순히 빈도 수 f를 늘릴 수 있습니다. 그렇지 않으면 빈도 카운트가 1인 목록에 추가할 수 있습니다. 새 항목이 b번째 버킷에서 나온 경우 항목의 빈도 카운트에서 가능한 최대 버그인 ∆를 b−1로 설정할 수 있습니다.
버킷 경계가 획득될 때마다(즉, N이 w, 2w, 3w 등을 포함하여 너비 w의 배수에 도달함) 빈도 목록이 결정됩니다. b를 현재 버킷 번호라고 하자. 항목 항목에 대해 f + ∆ ≤ b인 경우 항목 항목이 제거됩니다. 이 접근 방식에서 알고리즘 목표는 주파수 목록을 작게 유지하여 기본 메모리에 맞을 수 있도록 합니다. 각 항목에 대해 저장된 빈도 수는 항목의 실제 빈도 또는 최소화됩니다.
근사 알고리즘의 필수 요소는 근사 비율(또는 오차 범위)입니다. 아이템이 제거된 경우를 살펴보겠습니다. 항목에 대해 f +∆ ≤ b일 때 나타납니다. 여기서 b는 현재 버킷 번호입니다.
b ≤ N/w, 즉 b ≤ εN임을 이해할 수 있습니다. 항목의 실제 빈도는 최대 f+∆입니다. 따라서 최소화할 수 있는 항목은 εN입니다. 이 항목의 실제 지원이 σ(빈번하게 처리되는 최소 지원 또는 하한)인 경우 실제 빈도는 σN이고 빈도 목록의 빈도 f는 최소(σN −εN ).
따라서 f 값이 최소(σN - εN)인 빈도 목록의 모든 항목을 출력하면 일부 빈도 항목이 출력됩니다. 또한, 일부 빈도가 낮은 항목(실제 빈도는 최소 σN −εN이지만 σN 미만)이 출력됩니다.