728x90 반응형 hash2 [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. [CS246] Finding Similar Items (2) - Shingling Shinglings$k$-Shinglingsdocument를 길이가 $k$인 문자열 집합으로 표현한다.예를 들어 "abcdabd"에 대해 $k=2$인 2-shingling 집합은 {ab, bc, cd, da, ab, bd} 이다.공백과 관련하여 몇까지 옵션이 가능하다. (blank, tab, newline 등)일반적으로 $k=9,\ 9,\ 10$ 정도로 한다. textually similar한 문서들은 많은 수의 shingling이 겹칠 것이다. 단순히 한단어를 바꾸는 것으로는 $k-1$ 거리만큼만 바뀐다. 예를 들어 "The dog which chased the cat" 과 "The dog that chased the cat"을 비교해보자.두 문장의 차이점은 오직 "g_which_c"에서만 발생한다.. 2023. 9. 19. 이전 1 다음 728x90 반응형
