728x90 반응형 Hash Function1 [CS246] Flajolet-Martin (FM) Algorithm: Counting Distinct Elements from Data Stream Flajolet-Martin (FM) Algorithm: Counting Distinct Elements from Data StreamProblem Definitiondata stream은 크기가 $N$인 집합으로 간주할 수 있다.Applicationswebsite에 방문하는 (unique한) 유저 수는 얼마인가?web crawling으로 얻은 website에 존재하는 word의 수는?지난 주에 판매한 상품 품목(distinct products) 개수는?Real ProblemObvious approach: dictionary 자료구조를 이용한다. (key:element, value: counting)그러나 우리는 (data stream의 크기에 비해) 매우 적은 저장공간만 가진다. (limited wor.. 2023. 12. 22. 이전 1 다음 728x90 반응형