chapter 3. Filtering Patterns 서울시립대학교 전기전자컴퓨터공학과 G201449015 이가희 Data mining Lab. 병렬소프트웨어설계

0. Contents filtering bloom filtering top 10 distinct Filtering Patterns 0. Contents filtering bloom filtering top 10 distinct

1. Filtering : Pattern Description Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Description 관심 없는 레코드들은 필터링 단계에서 버림 큰 데이터를 쪼갠 데이터에서 관심 있는 것만 후속 분석을 하고 싶을 때 수행 레코드 단위 파싱, 높은 분류 성능 필터링 결과 : 선택 기준들을 통과한 레코드들의 subset closer view of data / distributed Grep / data cleansing / simple random sampling f true false an evaluation function 레코드 유지 레코드 버림 관심 있는 레코드만 취함

1. Filtering : Pattern Description Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Description no “reducer” map-only 잡이기 때문에 효율적이다. 데이터가 맵과 리듀스 단계 간에 전송될 필요가 없다. 또한 정렬 단계와 리듀스 단계가 제외된다.

1. Filtering : Pattern Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples Distributed Grep 입력 파일로 주어진 파일 내에 존재하는 특정한 문자열 패턴을 추출 입력 파일 : hotlist.txt regex ? .

1. Filtering : Pattern Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples Distributed Grep : mapper null 입력 : <, hotlist.txt record> 출력 : <null, record> map에서 필요한 변수 선언 map에서 필요한 resource 할당 (파일 검색 방법으로 정규식 설정) context : job과의 통신 및 입출력 담당 특정 패턴에 매칭되는 라인 리턴 (key, record)

1. Filtering : Pattern Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples Distributed Grep : driver

1. Filtering : Pattern Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples <regex> <input> <output> h.* .

1. Filtering : Pattern Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples Simple Random Sampling (SRS) 각각의 파일에서 일정 비율만큼 랜덤 추출 0~100 % ? .

1. Filtering : Pattern Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples Simple Random Sampling (SRS) : mapper 입력 : <, hotlist.txt record> 출력 : <null, record> map에서 필요한 resource 할당 (파일 검색 방법으로 비율(%) 설정) 조건에 맞는 라인 리턴 (key, record)

1. Filtering : Pattern Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples Simple Random Sampling (SRS) : driver 입력한 수 호출 (0~100)

1. Filtering : Pattern Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples <percentage> <input> <output> 100 records 20 records .

2. Bloom Filtering : Pattern Description Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Pattern Description Bloom filter : 원소가 집합에 속하는지 효율적으로 테스트 할 수 있는 자료구조 이 집합에 A가 있는가? 없는가? ‘h의 해시 값이 빈 곳을 가리키고 있기 때문에 bloom filter에는 h가 없어!’ 집합에 원소를 추가하는 것은 가능하나, 집합에서 원소를 삭제하는 것은 불가능하다. 집합 내 운소의 숫자가 증가할수록 긍정 오류 발생 확률도 증가한다. False Positive 존재 bloom filter (m=50, k=3) http://www.jasondavies.com/bloomfilter/

2. Bloom Filtering : Pattern Description Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Pattern Description a는 꼭 남아 있어야 해! f는 필요없어 버려! hot value! a,b,c,d,e 어떤 값들을 미리 멤버로 정의한 레코드들을 유지하고 싶을 때 : hot value 집합에 해당 data가 들어있는 유무를 판단하는 기준으로 bloom filter를 이용 데이터는 레코드들로 분리될 수 있다. (filtering) hot value를 각각의 레코드에서 추출할 수 있다. (특징 추출) hot value를 위한 item set을 미리 결정해둘 수 있다. False Negative는 절대 일어날 수 없다.

2. Bloom Filtering : Pattern Description Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Pattern Description structure : training + actual filtering bloom filter에 원소 추가 bloom filter 원소 유무 확인 새로운 data에 대한 해시 값 계산 후 비트 값 읽기 data가 bloom filter에 존재하는지 검사

2. Bloom Filtering : Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples 주어진 사용자 코멘트 목록에 대해 특정 키워드를 갖고 있지 않은 코멘트를 걸러내라 train data : a Bloom filter is trained with a hot list of keywords (100 terms) test data : inputComments.txt (Id, PostId, Score, Text, CreationDate, UserId) .

2. Bloom Filtering : Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples Bloom filter training inputFile (.gz) numMembers (training data 개수) falsePosRate (False Positive rate) bfFile (최종 bloom filter) bloom filter의 m, k 설정 bloom filter 생성

2. Bloom Filtering : Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples Bloom filter training training할 file 읽기 (hotlist) bloom filter에 data 추가 (training) bloom filter를 file형태로 내보냄

2. Bloom Filtering : Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples <inputfile> <nummembers> <falseposrate> <bfoutfile> .

2. Bloom Filtering : Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples Bloom filtering 주어진 사용자 코멘트 목록에 대해 특정 키워드를 갖고 있지 않은 코멘트를 걸러내라 inputComments.txt Id, PostId, Score, Text, CreationDate, UserId hotlistwords.bf

2. Bloom Filtering : Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples Bloom filtering : mapper 입력 : <, inputComments record> 출력 : <record, null> 인스턴스 생성 the ≠The

2. Bloom Filtering : Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples Bloom filtering : driver reduce task 사용하지 않음 job에 입력한 파일 위치 정보를 보냄 출력 파일이 저장될 위치 정보를 보냄 분산 캐시에 등록

2. Bloom Filtering : Examples Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples Bloom filtering : <cachefile> <input> <output>

3. Top Ten : Pattern Description Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 3. Top Ten : Pattern Description 데이터들을 순위를 매겨 상위 K개의 레코드들만 검색하고 싶을 때 사용 활용 이상치 분석 가장 관심 있는 레코드 선별 구체적인 기준에 가장 부합하는 레코드 선별

3. Top Ten : Pattern Description Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 3. Top Ten : Pattern Description mapper, reducer 관심 있는 레코드만 취함 find local top ten setup / map / cleanup setup / reduce 리듀서가 너무 많은 데이터를 가지고 있으면 성능이 좋지 않다 1개의 reducer 10*M record -> the final top ten

3. Top Ten : Examples Filtering Patterns 1 filtering 2 bloom filtering 4 distinct 3. Top Ten : Examples 주어진 사용자 정보 목록에서 Reputation을 기준으로 top 10 사용자 정보를 출력하라 input data : inputUser.txt (Id, Reputation, CreationDate, DisplayName, …)

3. Top Ten : Examples Filtering Patterns 1 filtering 2 bloom filtering 4 distinct 3. Top Ten : Examples Top Ten : mapper 입력 : < , inputUsers record> 출력 : <null, local top10 record> treemap 생성 (키를 기준으로 정렬 가능) (내림차순) 10위 이상이면 해당 레코드 버림

3. Top Ten : Examples Filtering Patterns 1 filtering 2 bloom filtering 4 distinct 3. Top Ten : Examples Top Ten : mapper 마무리작업 (최종적으로 남은 레코드를 리듀서로 전송) (null key)

3. Top Ten : Examples Filtering Patterns 1 filtering 2 bloom filtering 4 distinct 3. Top Ten : Examples Top Ten : reducer 입력 : <null, local top10 record > 출력 : <null, final top10 record>

3. Top Ten : Examples Filtering Patterns 1 filtering 2 bloom filtering 4 distinct 3. Top Ten : Examples Top Ten : driver reducer의 수 = 1

3. Top Ten : Examples Filtering Patterns 1 filtering 2 bloom filtering 4 distinct 3. Top Ten : Examples <input> <output> . .

4. Distinct : Pattern Description Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 4. Distinct : Pattern Description 유일한 값들만 모인 집합을 구하고 싶을 때 사용 중복제거 / 내부 조인 급증 방지 무작위 파티셔닝 (순서 유지 불가능) reducer 수는 필요한 만큼 사용 reducer 개수 = reduce 슬롯 수*2 값만 출력 (중복 데이터 처리) 값에 대한 키값 출력

4. Distinct : Pattern Example Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 4. Distinct : Pattern Example 주어진 사용자 코멘트 목록에서 사용자 id를 구별한 집합을 구하라. test data : inputComments.txt (Id, PostId, Score, Text, CreationDate, UserId) mapper : 각각의 입력 레코드에서 UserId를 얻는다. combiner : 중복 키 제거 reducer : 입력 받은 레코드에서 키를 파일 시스템에 출력

4. Distinct : Pattern Example Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 4. Distinct : Pattern Example Distinct : driver

4. Distinct : Pattern Example Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 4. Distinct : Pattern Example Distinct : map 입력 : < , inputComments record> 출력 : <UserId, >

4. Distinct : Pattern Example Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 4. Distinct : Pattern Example Distinct : reducer 입력 : <UserId, > 출력 : <UserId, >

4. Distinct : Pattern Example Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 4. Distinct : Pattern Example <input> <output> .

End