| 1 |
1
분산 시스템의 빈발 패턴 마이닝 방법에 있어서,빈발 k-항목 집합을 이용하여 후보 (k+1)-항목 집합을 결정하는 단계;상기 분산 시스템에 분산 저장된 비트맵 청크들을 이용하여 상기 후보 (k+1)-항목 집합의 부분 지지도들을 계산하는 단계;상기 후보 (k+1)-항목 집합의 부분 지지도들을 합산하는 단계; 및상기 부분 지지도들의 합산 결과에 기초하여 빈발 (k+1)-항목 집합을 결정하는 단계를 포함하고,상기 빈발 (k+1)-항목 집합을 결정하는 단계는상기 후보 (k+1)-항목 집합에 포함된 복수의 후보 (k+1)-항목들 중 부분 지지도를 합산한 지지도가 미리 정해진 최소 지지도 이상인 후보 (k+1)-항목을 상기 빈발 (k+1)-항목 집합에 포함시키는 단계를 포함하는분산 시스템의 빈발 패턴 마이닝 방법
|
| 2 |
2
제1항에 있어서,상기 빈발 (k+1)-항목 집합을 상기 분산 시스템에 브로드캐스트(broadcast) 하는 단계를 더 포함하는 분산 시스템의 빈발 패턴 마이닝 방법
|
| 3 |
3
제1항에 있어서,상기 분산 시스템은 상기 비트맵 청크들에 대응하는 복수의 매퍼들을 포함하고,상기 후보 (k+1)-항목 집합의 부분 지지도들을 계산하는 단계는상기 비트맵 청크들 각각을 해당하는 매퍼로 로드(load)하는 단계;상기 복수의 매퍼들 각각에서, 해당하는 비트맵 청크에 포함된 비트 벡터들의 AND 연산을 통해 상기 후보 (k+1)-항목 집합에 포함된 후보 (k+1)-항목들의 비트 벡터들을 계산하는 단계; 및상기 복수의 매퍼들 각각에서, 해당하는 비트 벡터들에 기초하여 상기 후보 (k+1)-항목 집합의 부분 지지도를 계산하는 단계;를 포함하는 분산 시스템의 빈발 패턴 마이닝 방법
|
| 4 |
4
삭제
|
| 5 |
5
제1항에 있어서,상기 후보 (k+1)-항목 집합이 존재하지 않을 경우, 상기 빈발 패턴 마이닝을 종료하는 단계를 더 포함하는 분산 시스템의 빈발 패턴 마이닝 방법
|
| 6 |
6
분산 시스템의 빈발 패턴 마이닝 방법에 있어서,빈발 k-항목 집합을 이용하여 후보 (k+1)-항목 집합을 결정하는 단계;상기 분산 시스템에 분산 저장된 비트맵 청크들을 이용하여 상기 후보 (k+1)-항목 집합의 부분 지지도들을 계산하는 단계;상기 후보 (k+1)-항목 집합의 부분 지지도들을 합산하는 단계; 및상기 부분 지지도들의 합산 결과에 기초하여 빈발 (k+1)-항목 집합을 결정하는 단계를 포함하고,상기 부분 지지도들을 합산하는 단계는상기 후보 (k+1)-항목 집합에 포함된 복수의 후보 (k+1)-항목들 중 동일한 후보 (k+1)-항목에 해당하는 부분 지지도 값들이 동일한 리듀서로 전달되도록, 상기 부분 지지도들을 셔플(shuffle)하는 단계를 포함하는 분산 시스템의 빈발 패턴 마이닝 방법
|
| 7 |
7
제1항에 있어서,상기 후보 (k+1)-항목 집합을 결정하는 단계는상기 분산 시스템에 브로드캐스트 된 상기 빈발 k-항목 집합을 수신하는 단계; 및상기 빈발 k-항목 집합에 포함된 복수의 빈발 k-항목들을 조합함으로써, 후보 (k+1)-항목들을 결정하는 단계를 포함하는, 분산 시스템의 빈발 패턴 마이닝 방법
|
| 8 |
8
분산 시스템의 빈발 패턴 마이닝 방법에 있어서,빈발 k-항목 집합을 이용하여 후보 (k+1)-항목 집합을 결정하는 단계;상기 분산 시스템에 분산 저장된 비트맵 청크들을 이용하여 상기 후보 (k+1)-항목 집합의 부분 지지도들을 계산하는 단계;상기 후보 (k+1)-항목 집합의 부분 지지도들을 합산하는 단계;상기 부분 지지도들의 합산 결과에 기초하여 빈발 (k+1)-항목 집합을 결정하는 단계;상기 분산 시스템에 분산 저장된 데이터들에 포함된 복수의 항목들을 미리 정해진 방식으로 분할하는 단계;상기 분할된 항목들에 기반한 패턴들을 결정하는 단계; 및상기 분산 저장된 데이터들 각각에 대응하는 매퍼를 이용하여, 해당하는 데이터에 포함된 상기 패턴들을 나타내는 비트 벡터들을 결정함으로써 해당하는 매퍼를 위한 비트맵 청크를 생성하는 단계를 포함하는, 분산 시스템의 빈발 패턴 마이닝 방법
|
| 9 |
9
제8항에 있어서,상기 비트맵 청크는 키-값(key-value) 구조를 갖고, 상기 키(key)는 상기 패턴들에 대응되는 항목 집합이고, 상기 값(value)는 상기 비트 벡터들을 포함하는 분산 시스템의 빈발 패턴 마이닝 방법
|
| 10 |
10
제8항에 있어서,상기 비트맵 청크들은 서로 동일한 키를 갖는 분산 시스템의 빈발 패턴 마이닝 방법
|
| 11 |
11
제 8항에 있어서,상기 항목들은 빈발 1-항목 집합(FREQUENT 1-ITEM SET)에 해당하는, 분산 시스템의 빈발 패턴 마이닝 방법
|
| 12 |
12
제11항에 있어서,상기 비트맵 청크를 생성하는 단계는상기 분산 저장되어 있는 데이터를 입력으로 하여, 상기 분할된 빈발 1-항목 집합의 조합에 대응하는 비트 벡터들을 결정하는 단계를 포함하는 분산 시스템의 빈발 패턴 마이닝 방법
|
| 13 |
13
제8항에 있어서,상기 비트맵 청크를 생성하는 단계는상기 해당하는 데이터를 라인별로 나누어 수신하는 단계; 및상기 라인의 수에 대응되는 비트 수로 구성되고, 상기 라인에 상기 데이터가 존재할 경우 제1 논리 값을, 존재하지 않을 경우 제2 논리 값을 갖도록 상기 비트 벡터를 결정하는 단계를 포함하는 분산 시스템의 빈발 패턴 마이닝 방법
|
| 14 |
14
하드웨어와 결합되어 제1항 내지 제 3항 및 제 5항 내지 제13항 중 어느 하나의 항의 방법을 실행시키기 위하여 매체에 저장된 컴퓨터 프로그램
|
| 15 |
15
빈발 패턴 마이닝을 위한 분산 시스템에 있어서,빈발 k-항목 집합을 이용하여 후보 (k+1)-항목 집합을 결정하고, 상기 분산 시스템에 분산 저장된 비트맵 청크들을 이용하여 상기 후보 (k+1)-항목 집합의 부분 지지도들을 계산하는 매퍼 모듈; 및상기 후보 (k+1)-항목 집합의 부분 지지도들을 합산하여, 빈발 (k+1)-항목 집합을 결정하는 리듀서 모듈을 포함하고,상기 리듀서 모듈은상기 후보 (k+1)-항목 집합에 포함된 복수의 후보 (k+1)-항목들 중 부분 지지도를 합산한 지지도가 미리 정해진 최소 지지도 이상인 후보 (k+1)-항목을 상기 빈발 (k+1)-항목 집합에 포함시키는, 분산 시스템
|
| 16 |
16
제15항에 있어서,상기 리듀서 모듈은상기 빈발 (k+1)-항목 집합을 상기 분산 시스템에 브로드캐스트(broadcast) 하는, 분산 시스템
|
| 17 |
17
제15항에 있어서,상기 매퍼 모듈에 포함된 매퍼들 각각은해당하는 비트맵 청크를 로드(load)하고, 해당하는 비트맵 청크에 포함된 비트 벡터들의 AND 연산을 통해 상기 후보 (k+1)-항목 집합에 포함된 후보 (k+1)-항목들의 비트 벡터들을 계산하며, 해당하는 비트 벡터들에 기초하여 상기 후보 (k+1)-항목 집합의 부분 지지도를 계산하는, 분산 시스템
|
| 18 |
18
삭제
|
| 19 |
19
빈발 패턴 마이닝을 위한 분산 시스템에 있어서,빈발 k-항목 집합을 이용하여 후보 (k+1)-항목 집합을 결정하고, 상기 분산 시스템에 분산 저장된 비트맵 청크들을 이용하여 상기 후보 (k+1)-항목 집합의 부분 지지도들을 계산하는 매퍼 모듈; 및상기 후보 (k+1)-항목 집합의 부분 지지도들을 합산하여, 빈발 (k+1)-항목 집합을 결정하는 리듀서 모듈을 포함하고,상기 리듀서 모듈은상기 후보 (k+1)-항목 집합에 포함된 복수의 후보 (k+1)-항목들 중 부분 지지도를 합산한 지지도가 미리 정해진 최소 지지도 이상인 후보 (k+1)-항목을 상기 빈발 (k+1)-항목 집합에 포함시키고,상기 후보 (k+1)-항목 집합에 포함된 복수의 후보 (k+1)-항목들 중 동일한 후보 (k+1)-항목에 해당하는 부분 지지도 값들은 상기 리듀서 모듈 내 동일한 리듀서로 전달되는,분산 시스템
|
| 20 |
20
제12항에 있어서,상기 비트 벡터들을 결정하는 단계는가용 가능한 분산저장시스템의 용량을 고려하여 상기 빈발 1-항목 집합의 조합에 대응하는 x-항목 집합을 구하는 단계상기 x-항목 집합에 대응되는 상기 비트 벡터를 결정하는 단계를 포함하는, 분산 시스템의 빈발 패턴 마이닝 방법
|
| 21 |
21
제17항에 있어서,상기 매퍼 모듈에 포함된 매퍼들 각각은상기 AND 연산의 수를 최소화할 수 있는 항목 집합을 추출하고,상기 추출된 항목 집합에 대응하는 상기 비트 벡터들에 기초하여 상기 후보 (k+1)-항목 집합의 부분 지지도를 계산하는, 분산 시스템
|
