hashmap + Heap
가장 간단한 형태로 구현할 수 있음. hashamp으로 key별로 frequency를 저장하고, Heap으로 top K 만 관리. space가 그다지 크지 않을때
top K in data stream
distribute 환경에서 stream으로 데이터가 들어온다고 하면 어떤 방법을 사용할 수 있을까
multi hashmap + heap
앞서 봤던 hashmap + Heap을 N개의 노드에 나누어서 각 노드에서 top K를 계산하고 있다가, 전체 top K를 계산할때는 각 노드의 K를 받아와서 머지를 한 후 최종 top K를 계산한다.
approximate algorithm
앞서 살펴본 것들은 모든 데이터의 frequency를 저장하고 있어야 하기 때문에 저장 공간의 낭비가 심하다. 그래서 근사 알고리즘들이 좀 나왔는데
count min sketch + heap
N개의 hash function을 만들어, data가 들어올때마다 N개의 해쉬펑션의 hash_vale의 frequency를 증가시켜줌.이것을 T[hash_func][hash_value] 라 함.
실제 val를 얻을때는 모든 T를 hash_func만큼 돌면서 얻은 값의 최소값을 반환함.
data의 존재여부를 판단하는 bloom filter와 아주 유사한데 그것에 count가 더해진 형태이다.
lossy counting
데이터 스트림을 특정 기간의 타임 윈도우로 분할을 해서, 그 윈도우에서 얻은 frequency -1를 해준다. -1을 해줌으로서 마이너한 데이터를 제거할 수 있게 된다.
그렇게 해서 전체 space를 줄일 수 있다.