1 |
1
연속적으로 입력되는 스트림 데이터의 트랜잭션에 대한 빈발 패턴을 확인하는 방법에 있어서,(a) 입력되는 트랜잭션이 삽입된 슬라이딩 윈도우 내의 모든 아이템에 대한 비트맵을 확인하여 상기 트랜잭션에 포함되어 있는 아이템 집합의 비트맵 지지도를 확인하는 단계;(b) 상기 비트맵 지지도가 사전에 설정된 지지도 이상이면 빈발 패턴으로 판정하고, 이전의 아이템 집합보다 특정 수의 아이템을 더 포함하는 아이템 집합에 대한 빈발 패턴 후보 집합을 조합하는 단계;(c) 조합된 하나 이상의 빈발 패턴 후보 집합의 비트맵을 계산하고, 상기 계산된 비트맵에 대한 비트맵 지지도를 산출하는 단계; 및(d) 상기 빈발 패턴 후보 집합이 존재하지 않을 때까지, 상기 (b) 단계 이후의 과정을 반복하여 수행하는 단계를 포함하는 빈발 패턴 확인 방법
|
2 |
2
제1항에 있어서,상기 단계 (a)는,상기 트랜잭션이 삽입된 슬라이딩 윈도우 내의 모든 아이템에 대한 비트맵을 확인하는 단계; 및상기 비트맵에 포함된 '1' 비트 개수를 확인하여, 상기 비트맵 지지도를 확인하는 단계를 포함하는 빈발 패턴 확인 방법
|
3 |
3
제1항에 있어서,상기 단계 (b)는,상기 비트맵 지지도와 상기 트랜잭션이 삽입된 슬라이딩 윈도우의 크기와 사전에 설정된 최소 지지도―여기서, 상기 최소 지지도는 0과 1 사이의 값임―가 곱해진 값을 비교하여, 빈발 패턴 여부를 판정하는 것을 특징으로 하는 빈발 패턴 확인 방법
|
4 |
4
제1항 또는 제2항에 있어서,상기 단계 (c)는,(c1) 상기 빈발 패턴 후보 집합에 대한 AND 연산을 통해 비트맵을 계산하는 단계; 및(c2) 상기 비트맵에 포함된 '1' 비트 개수를 확인하여, 상기 비트맵 지지도를 확인하는 단계를 포함하는 빈발 패턴 확인 방법
|
5 |
5
제1항에 있어서,상기 단계 (b)는,상기 비트맵 지지도가 사전에 설정된 최소 지지도 이상이면, 이전의 아이템 집합보다 하나의 아이템이 더 포함된 아이템 집합에 대한 빈발 패턴 후보 집합을 조합하는 것을 특징으로 하는 빈발 패턴 확인 방법
|
6 |
6
연속적으로 입력되는 스트림 데이터의 트랜잭션에 대한 비트맵 압축 방법에 있어서,(a) 입력되는 트랜잭션을 슬라이딩 윈도우의 시간 구간에 삽입하는 단계;(b) 상기 트랜잭션에 포함된 아이템이 상기 슬라이딩 윈도우에 존재하는지 여부를 확인하여, 존재가 확인되면 상기 아이템의 비트맵을 사전에 설정된 비트만큼 이동시킨 후 사전에 설정된 비트값을 추가하고, 상기 트랜잭션에 포함된 아이템이 상기 슬라이딩 윈도우에 존재하지 않으면 새로운 비트맵을 할당하여 상기 슬라이딩 윈도우에 추가하는 단계; 및(c) 상기 슬라이딩 윈도우에서 비트맵 지지도가 0인 아이템을 삭제하는 단계를 포함하는 비트맵 압축 방법
|
7 |
7
제6항에 있어서,상기 단계 (a)는 (a1) 상기 트랜잭션의 입력이 확인되면, 상기 트랜잭션을 수용하는 슬라이딩 윈도우의 시간 구간이 모두 채워진 상태인지 여부를 확인하는 단계;(a2) 상기 슬라이딩 윈도우의 시간 구간이 모두 채워진 상태이면 맨 처음 입력된 트랜잭션을 삭제하여 상기 입력된 트랜잭션을 삽입시키는 단계; 및(a3) 상기 슬라이딩 윈도우가 모두 채워진 상태가 아니면, 상기 슬라이딩 윈도우에서 트랜잭션이 채워진 시간 구간의 바로 뒤에 위치한 시간 구간에 상기 입력된 트랜잭션을 삽입하는 단계를 포함하는 비트맵 압축 방법
|
8 |
8
제7항에 있어서, 상기 단계 (a2)는(a21) 상기 슬라이딩 윈도우에서 가장 앞에 위치한 시간 구간에 삽입되어 있는 트랜잭션을 삭제하는 단계;(a22) 상기 슬라이딩 윈도우의 시간 구간에 채워진 트랜잭션을 하나씩 앞쪽으로 이동시키는 단계; 및(a23) 상기 슬라이딩 윈도우에서 가장 뒤에 위치한 시간 구간에 상기 입력된 트랜잭션을 삽입하는 단계를 포함하는 비트맵 압축 방법
|
9 |
9
제6항에 있어서,상기 단계 (b)는,(b1) 상기 트랜잭션에 포함된 아이템이 상기 슬라이딩 윈도우에 존재하는지 여부를 확인하는 단계;(b2) 상기 트랜잭션에 포함된 아이템이 상기 슬라이딩 윈도우에 존재하면, 상기 아이템의 비트맵을 앞쪽으로 1비트씩 이동시킨 후, 상기 비트맵에 '1'의 비트값을 추가하는 단계; 및(b3) 상기 트랜잭션에 포함된 아이템이 상기 슬라이딩 윈도우에 존재하지 않으면, 상기 아이템에 대한 비트맵을 할당하고, 상기 할당된 비트맵에 '1'의 비트값을 추가하는 단계를 포함하는 비트맵 압축 방법
|
10 |
10
제6항에 있어서,상기 단계 (b)와 상기 단계 (c) 사이에,상기 슬라이딩 윈도우에 포함되어 있는 비트맵 중, 상기 트랜잭션에 포함되어 있지 않은 아이템의 비트맵에 대하여, 상기 시간 구간의 크기만큼 앞쪽으로 이동시키는 단계를 추가로 포함하는 비트맵 압축 방법
|