728x90 반응형 data stream4 [CS246] Counting Frequent Elements in a stream Exponentially Decaying Window: Finding Frequent Recent Items from StreamMotivation이번 포스팅에서는 2가지 문제에 관심을 갖는다.(1) Finding most common elements(2) Finding most common recent elements Example최근 영화 중에서 가장 많이 예매된 것은?(Amazon과 같은) 전자상거래의 stream data 중에서 최근 판매된 인기 상품은?(Twitter, 이제는 X) SNS에서 최근 가장 활발한 유저는? Sliding Window: What is "recent"?어떤 기준으로 최근(recent) 정보를 반영할 수 있을까?가장 기본적으로 떠오르는 생각은 sliding window이다.. 2023. 12. 28. [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] Filtering Data Streams Filtering with Hash Table, Bloom FilterApplicationEmail spam filtering (이번 포스팅에서 자주 사용될 예시이다)100만명의 user에 대하여 각 user마다 1000개의 good(trusted) 주소가 있다고 하자.good(trusted) mail은 NOT spam이다.Publish-subscribe systemsnews 기사 데이터를 모으고 있다고 하자. (포털 사이트)어떤 keyword에 대하여 관심이 있는 기사를 맞춰 제공할 수 있다.Content filtering보고싶은/보고싶지않은 컨텐츠를 필터링할 수 있다광고시스템, 추천시스템 등 Bloom Filter: Algorithm우리가 필터링하고 싶은 key의 집합을 $S$라 하자.길이가 $n$인.. 2023. 12. 19. [CS246] Sampling from a Data Stream Fixed-proportion, Fixed-size, Reservoir SamplingIntroductiondata stream은 전체 데이터를 저장할 수 없기 때문에, 샘플링을 이용한다.크게 2가지 방법이 있는데, fixed proportion 방법과 random sample of fixed size이다. Sampling a Fixed Proportiondata stream의 일정 비율(예를 들어 10% 등)만큼 샘플링하는 것이다. stream이 커질수록 sample 역시 커진다. Problem with Naive Approachstream data가 (user, query, time)이라는 tuple의 형태로 들어온다고 할 때, unique query의 비율을 추정해보자. 이때 당연히 중복되는 que.. 2023. 12. 4. 이전 1 다음 728x90 반응형
