1 |
1
(a) 최소 빈발 부분그래프 추출부에 의해 그래프 데이터베이스에서 최소 지지도 이상으로 발생하는 빈발 부분그래프 중 최소 깊이 우선 탐색 코드(depth first search code, 이하 DFS 코드)를 가지는 1에지 최소 빈발 부분그래프를 추출하는 단계;(b) 확장부에 의해 상기 1에지 최소 빈발 부분그래프에 에지를 확장하는 에지 확장 방식과 상기 1에지 최소 빈발 부분그래프에 신규 부분그래프를 추가하는 그래프 확장 방식으로 상기 1에지 최소 빈발 부분그래프를 확장하는 단계;(c) 최소 DFS 코드 판단부에 의해 상기 에지 확장 방식으로 확장된 에지 확장 부분그래프 또는 상기 그래프 확장 방식으로 확장된 그래프 확장 부분그래프가 각각 최소 DFS 코드인지와 동시 빈발 최소 DFS 코드인지 판단하는 단계; (d) 최소 지지도 판단부에 의해 상기 에지 확장 부분그래프와 상기 그래프 확장 부분그래프가 최소 지지도를 만족하는지 판단하는 단계; 및(e) 확장 판단부에 의해 상기 에지 확장 부분그래프와 상기 그래프 확장 부분그래프가 각각 최소 DFS 코드와 동시 빈발 최소 DFS 코드인지 여부와 상기 에지 확장 부분그래프와 상기 그래프 확장 부분그래프가 각각 최소 지지도를 만족하는지 여부로 상기 에지 확장 부분그래프 또는 상기 그래프 확장 부분그래프의 다음 확장 여부를 결정하는 단계를 포함하는 동시 빈발 부분그래프의 마이닝 방법
|
2 |
2
제 1 항에 있어서, 상기 그래프 확장 방식으로 상기 1에지 최소 빈발 부분그래프에 추가되는 신규 부분그래프는 상기 1에지 최소 빈발 부분그래프와 비연결되어 있는 것을 특징으로 하는 동시 빈발 부분그래프의 마이닝 방법
|
3 |
3
제 2 항에 있어서, 상기 신규 부분그래프와 상기 1에지 최소 빈발 부분그래프의 비연결 여부는 상기 신규 부분그래프와 상기 1에지 빈발 부분그래프의 에지 정보에 기초하여 공통된 노드를 포함하는지 여부로 판단하는 것을 특징으로 하는 동시 빈발 부분그래프의 마이닝 방법
|
4 |
4
제 3 항에 있어서, 상기 에지 정보는상기 에지를 구성하는 각 노드의 버텍스 식별자 및 버텍스 레이블을 구비하는 것을 특징으로 하는 동시 빈발 부분그래프의 마이닝 방법
|
5 |
5
제 3 항에 있어서, 상기 동시 빈발 부분그래프의 마이닝 방법은상기 에지 확장 부분그래프와 상기 그래프 확장 부분그래프가 각각 최소 DFS 코드 또는 동시 빈발 최소 DFS 코드이거나 상기 에지 확장 부분그래프 또는 상기 그래프 확장 부분그래프가 각각 최소 지지도를 만족하는 경우, 상기 에지 확장 부분 그래프 또는 상기 그래프 확장 부분그래프를 에지 확장 방식 또는 그래프 확장 방식으로 상기 에지 확장 부분그래프 또는 상기 그래프 확장 부분그래프를 확장하는 것을 특징으로 하는 동시 빈발 부분그래프의 마이닝 방법
|
6 |
6
제 5 항에 있어서, 상기 (a) 단계는상기 그래프 데이터베이스에서 최소 지지도 이상으로 발생하는 1에지 빈발 부분그래프를 추출하는 단계; 및상기 추출한 1에지 빈발 부분그래프에서 최소 DFS 코드를 가지는 1에지 최소 빈발 부분그래프를 판단하는 단계를 포함하는 것을 특징으로 하는 동시 빈발 부분그래프의 마이닝 방법
|
7 |
7
제 5 항에 있어서, 상기 동시 빈발 최소 DFS 코드의 판단은상기 1에지 최소 빈발 부분그래프와 상기 신규 부분그래프의 노드 수가 동일한 경우, 상기 1에지 최소 빈발 부분그래프의 DFS 코드가 상기 신규 부분그래프의 DFS 코드보다 작은 값을 가지는 경우 동시 빈발 최소 DFS 코드로 판단하며,상기 1에지 최소 빈발 부분그래프와 상기 신규 부분그래프의 노드 수가 서로 상이한 경우, 상기 1에지 최소 빈발 부분그래프의 노드 수가 상기 신규 부분그래프의 노드 수보다 작은 값을 가지는 경우 동시 빈발 최소 DFS 코드로 판단하는 것을 특징으로 하는 동시 빈발 부분그래프의 마이닝 방법
|
8 |
8
(a) 확장부에 의해 그래프 데이터베이스에서 최소 지지도 이상으로 발생하는 빈발 부분그래프 중 최소 깊이 우선 탐색 코드(depth first search code, 이하 DFS 코드)를 가지는 최소 빈발 부분그래프에 에지를 확장하는 에지 확장 방식과 상기 최소 빈발 부분그래프에 신규 부분그래프를 추가하는 그래프 확장 방식으로 상기 최소 빈발 부분그래프를 확장하는 단계;(b) 최소 DFS 코드 판단부에 의해 상기 에지 확장 방식으로 확장된 에지 확장 부분그래프 또는 상기 그래프 확장 방식으로 확장된 그래프 확장 부분그래프가 각각 최소 DFS 코드인지와 동시 빈발 최소 DFS 코드인지 판단하는 단계;(d) 최소 지지도 판단부에 의해 상기 에지 확장 부분그래프와 상기 그래프 확장 부분그래프가 최소 지지도를 만족하는지 판단하는 단계; 및(e) 확장 판단부에 의해 상기 에지 확장 부분그래프 또는 상기 그래프 확장 부분그래프가 각각 최소 DFS 코드와 동시 빈발 최소 DFS 코드인지 여부와 상기 에지 확장 부분그래프또는 상기 그래프 확장 부분그래프가 각각 최소 지지도를 만족하는지 여부로 상기 에지 확장 부분그래프 또는 상기 그래프 확장 부분그래프의 다음 확장 여부를 결정하는 단계를 포함하는 동시 빈발 부분그래프의 마이닝 방법
|
9 |
9
제 8 항에 있어서, 상기 그래프 확장 방식으로 상기 최소 빈발 부분그래프에 추가되는 신규 부분그래프는 상기 최소 빈발 부분그래프와 비연결되어 있는 것을 특징으로 하는 동시 빈발 부분그래프의 마이닝 방법
|
10 |
10
제 9 항에 있어서, 상기 신규 부분그래프와 상기 최소 빈발 부분그래프의 비연결 여부는 상기 신규 부분그래프와 상기 빈발 부분그래프의 에지 정보에 기초하여 공통된 노드를 포함하는지 여부로 판단하는 것을 특징으로 하는 동시 빈발 부분그래프의 마이닝 방법
|
11 |
11
제 10 항에 있어서, 상기 에지 정보는상기 에지를 구성하는 각 노드의 버텍스 식별자 및 버텍스 레이블을 구비하는 것을 특징으로 하는 동시 빈발 부분그래프의 마이닝 방법
|
12 |
12
제 10 항에 있어서, 상기 동시 빈발 부분그래프의 마이닝 방법은상기 에지 확장 부분그래프와 상기 그래프 확장 부분그래프가 각각 최소 DFS 코드 또는 동시 빈발 최소 DFS 코드이거나 상기 에지 확장 부분그래프 또는 상기 그래프 확장 부분그래프가 각각 최소 지지도를 만족하는 경우, 상기 에지 확장 부분 그래프 또는 상기 그래프 확장 부분그래프를 에지 확장 방식 또는 그래프 확장 방식으로 상기 에지 확장 부분그래프 또는 상기 그래프 확장 부분그래프를 확장하는 것을 특징으로 하는 동시 빈발 부분그래프의 마이닝 방법
|
13 |
13
그래프 데이터베이스에서 최소 지지도 이상으로 발생하는 빈발 부분그래프 중 최소 깊이 우선 탐색 코드(depth first search code, 이하 DFS 코드)를 가지는 최소 빈발 부분그래프를 추출하는 최소 빈발 부분그래프 추출부;상기 최소 빈발 부분그래프에 에지를 확장하는 에지 확장 방식과 상기 최소 빈발 부분그래프에 신규 부분그래프를 추가하는 그래프 확장 방식으로 상기 최소 빈발 부분그래프를 확장하는 확장부;상기 에지 확장 방식으로 확장된 에지 확장 부분그래프 또는 상기 그래프 확장 방식으로 확장된 그래프 확장 부분그래프가 각각 최소 DFS 코드인지와 동시 빈발 최소 DFS 코드인지 판단하는 최소 DFS 코드 판단부;상기 에지 확장 부분그래프와 상기 그래프 확장 부분그래프가 최소 지지도를 만족하는지 판단하는 최소 지지도 판단부; 및상기 에지 확장 부분그래프 또는 상기 그래프 확장 부분그래프가 각각 최소 DFS 코드와 동시 빈발 최소 DFS 코드인지 여부와 상기 에지 확장 부분그래프또는 상기 그래프 확장 부분그래프가 각각 최소 지지도를 만족하는지 여부로 상기 에지 확장 부분그래프 또는 상기 그래프 확장 부분그래프의 다음 확장 여부를 결정하는 확장 판단부를 포함하는 것을 특징으로 하는 동시 빈발 부분그래프 마이닝 장치
|