손실 계산(Lossy Counting) 알고리즘이란?
손실 계산 알고리즘은 끝없이 흘러 들어오는 데이터 스트림에서 빈발 항목(frequent items)을 근사적으로 찾아내는 대표적인 기법입니다. 전체 데이터를 저장하지 않고도 제한된 메모리 안에서 높은 정확도를 유지할 수 있다는 점이 가장 큰 특징입니다.
입력 매개변수와 버킷 분할
알고리즘은 두 가지 입력 매개변수를 받습니다. 하나는 최소 지지도 임계값(minimum support threshold) σ이고, 다른 하나는 오차 한계(error bound) ε입니다. 들어오는 스트림은 이론상 너비 w = ⌈1/ε⌉를 갖는 버킷(bucket) 단위로 나누어 처리합니다.
빈도 리스트 데이터 구조
N을 현재까지 처리한 스트림 길이, 즉 지금까지 관찰한 항목의 총 개수라고 합시다. 알고리즘은 빈도가 0보다 큰 모든 원소를 추적하기 위해 빈도 리스트(frequency-list)라는 데이터 구조를 유지합니다. 리스트의 각 항목에는 두 가지 값이 함께 저장됩니다.
- f: 해당 항목의 근사 빈도 카운트(approximate frequency count)
- Δ: f가 가질 수 있는 최대 가능 오차(maximum possible error)
알고리즘 동작 절차
1. 새 버킷 도착 시 항목 삽입
새로운 버킷이 도착하면 그 안의 항목들을 빈도 리스트에 반영합니다. 해당 항목이 이미 리스트에 존재한다면 단순히 빈도 카운트 f를 1만큼 증가시키면 됩니다. 존재하지 않는다면 빈도 카운트 1로 새 항목을 추가합니다. 이때 새 항목이 b번째 버킷에서 온 것이라면, 그 항목의 빈도 카운트에 대한 최대 가능 오차 Δ를 b − 1로 설정합니다.
2. 버킷 경계에서의 가지치기(pruning)
버킷 경계에 도달할 때마다, 즉 N이 w, 2w, 3w처럼 w의 배수가 될 때마다 빈도 리스트를 점검합니다. 현재 버킷 번호를 b라고 할 때, 어떤 항목에 대해 f + Δ ≤ b가 성립하면 그 항목은 리스트에서 삭제합니다. 이러한 방식으로 알고리즘은 빈도 리스트의 크기를 작게 유지하여 주 메모리(primary memory)에 담을 수 있도록 합니다. 각 항목에 저장된 빈도 카운트는 실제 빈도와 같거나, 그보다 약간 작은 값(과소평가)입니다.
근사 비율(오차 한계) 분석
근사 알고리즘에서 가장 중요한 요소는 근사 비율(approximation ratio), 다시 말해 오차 한계입니다. 항목이 제거되는 상황을 살펴보겠습니다. 제거는 어떤 항목에 대해 f + Δ ≤ b(b는 현재 버킷 번호)가 성립할 때 일어납니다.
여기서 b ≤ N/w, 즉 b ≤ εN임을 알 수 있습니다. 한 항목의 실제 빈도는 최대 f + Δ이므로, 어떤 항목도 최대 εN만큼 과소평가될 수 있습니다. 만약 이 항목의 실제 지지도가 σ(빈발로 인정받기 위한 최소 지지도, 즉 하한)라면 실제 빈도는 σN이 되고, 빈도 리스트에 기록된 빈도 f는 최소한 σN − εN 이상이어야 합니다.
출력 결과의 보장
따라서 빈도 리스트에서 f ≥ σN − εN을 만족하는 모든 항목을 출력하면, 진짜 빈발 항목은 빠짐없이 출력에 포함됩니다. 다만 실제 빈도가 σN − εN 이상이면서 σN 미만인 준빈발(subfrequent) 항목 일부도 함께 출력될 수 있습니다. 이것이 바로 손실 계산 알고리즘이 거짓 음성(false negative)은 없지만 거짓 양성(false positive)은 일부 허용하는 근사 방식으로 불리는 이유입니다.