Top-K
Top-K (Top-K)
이번엔 데이터 스트림에서 가장 빈번하게 등장하는 항목을 찾는 자료구조, Top-K를 배워볼게요. 소셜 미디어의 트렌드 해시태그나, 네트워크 이상 탐지 같은 곳에 아주 잘 어울려요. 전부 저장하지 않고도 "상위 K개"를 계속 추적할 수 있죠.
Top-K란?
Top-K는 데이터 스트림에서 가장 빈번한 항목을 찾을 수 있게 해주는 확률적(probabilistic) 데이터 구조예요. Redis Open Source의 Top K는 스트림에서 상위 K개의 고순위(high-rank) 요소를 추정할 때 사용돼요.
여기서 "고순위(highest-rank)"란 "가장 높은 숫자나 점수(score)가 붙은 요소"를 뜻해요. score는 스트림에서 요소가 등장한 횟수(count)가 될 수 있으니, 스트림에서 가장 높은 빈도를 가진 요소를 찾는 데 완벽한 자료구조예요.
아주 흔한 응용 사례는 네트워크 이상 징후와 DDoS 공격 탐지예요. Top K는 이렇게 물어볼 수 있죠. "같은 주소로, 또는 같은 IP로부터 들어오는 요청 흐름(flux)이 갑자기 증가했나?"
사용 사례 (Use case)
트렌드 해시태그 (소셜 미디어 플랫폼, 뉴스 배포 네트워크)
이 응용은 다음 질문에 답해요.
- 지난 X시간 동안 사람들이 가장 많이 언급한 K개의 해시태그는 무엇인가?
- 오늘 조회수/읽기 수가 가장 높은 K개의 뉴스는 무엇인가?
데이터 흐름은 들어오는 소셜 미디어 게시물이고, 여기서 각 해시태그를 파싱해요. TOPK.LIST 명령의 시간 복잡도는 O(K*log(k))예요. 그래서 K가 작다면 별도의 Set이나 Sorted Set을 유지할 필요 없이, Top K 자체에 직접 질의하면 돼요.
예제 (Example)
이 예시는 온라인 쇼핑에서 "bike"와 관련된 키워드("bike store", "bike handlebars" 등)를 추적하는 방법을 보여줄게요.
먼저 Top-K 스케치를 예약(reserve)해요.
import redis
r = redis.Redis(decode_responses=True)
res1 = r.topk().reserve("bikes:keywords", 5, 2000, 7, 0.925)
print(res1) # >>> True
reserve의 인자는 순서대로 topK의 크기(여기서는 5), 각 항목별 width, depth, decay예요. 즉 "상위 5개"를 추적하도록 만든 거죠.
이제 키워드들을 추가해요. 이미 있는 항목을 다시 넣으면 그 항목의 카운트가 올라가요.
res2 = r.topk().add(
"bikes:keywords",
"store", "seat", "handlebars", "handles",
"pedals", "tires", "store", "seat",
)
print(res2) # >>> [None, None, None, None, None, 'handlebars', None, None]
add의 응답에서 None이 아닌 값(여기서는 'handlebars')은 새로 추가되어 어떤 기존 항목을 쫓아낸 항목을 의미해요.
마지막으로 현재 상위 K개를 조회해요.
res3 = r.topk().list("bikes:keywords")
print(res3) # >>> ['store', 'seat', 'pedals', 'tires', 'handles']
Node.js 예시도 비슷해요.
const res2 = await client.topK.add(
'bikes:keywords',
['store', 'seat', 'handlebars', 'handles', 'pedals', 'tires', 'store', 'seat']
);
console.log(res2); // >>> [null, null, null, null, null, 'handlebars', null, null]