| 1 |
1
컴퓨터에서 그래프 데이터베이스에 저장되어 있는 그래프로부터 빈발 부분그래프를 마이닝하는 방법에 있어서,(a) 상기 그래프 데이터베이스로부터 최소 지지도 이상으로 출현하는 빈발 부분그래프를 추출하는 단계;(b) 상기 빈발 부분그래프의 각 에지의 확장 순서로 상기 각 에지의 깊이 우선 탐색 코드(depth first search code, 이하 DFS 코드)를 생성하는 단계; 및(c) 상기 각 에지의 DFS 코드와 정규 그래프 탐색 트리의 정규 코드를 비교하여 상기 빈발 부분그래프가 최소 DFS 코드를 가지는 정규 그래프인지 판단하는 단계를 포함하는 빈발 부분그래프의 마이닝 방법
|
| 2 |
2
제 1 항에 있어서, 상기 정규 그래프인지 판단하는 단계는상기 각 에지의 DFS 코드가 상기 정규 그래프 탐색 트리에 존재하는지 판단하는 단계;상기 판단 결과에 따라 상기 빈발 부분그래프의 각 에지의 확장 순서와, 상기 정규 그래프 탐색 트리에서 상기 각 에지의 DFS 코드와 동일한 정규 코드의 저장 레벨 순서가 일치하는지 판단하는 단계; 및상기 빈발 부분그래프의 각 에지의 확장 순서와, 상기 각 에지의 DFS 코드와 동일한 정규 코드의 저장 레벨 순서가 일치하는 경우 상기 추출한 빈발 부분그래프를 정규 그래프로 판단하는 단계를 포함하는 것을 특징으로 하는 빈발 부분그래프 마이닝 방법
|
| 3 |
3
제 2 항에 있어서, 상기 빈발 부분 그래프가 최소 DFS 코드를 가지는 정규 그래프가 아닌 경우, 상기 빈발 부분 그래프를 삭제하는 것을 특징으로 하는 빈발 부분그래프의 마이닝 방법
|
| 4 |
4
제 1 항 또는 제 2 항에 있어서, 상기 빈발 부분그래프의 마이닝 방법은(d) 상기 빈발 부분그래프가 정규 그래프인 경우, 상기 빈발 부분그래프를 에지 확장하여 추가 빈발 부분그래프를 추출하는 단계를 더 포함하며,상기 추가 빈발 부분그래프에 대해 상기 (b) 단계 및 (c)단계를 반복하여 수행하는 것을 특징으로 하는 것을 특징으로 하는 빈발 부분그래프의 마이닝 방법
|
| 5 |
5
제 4 항에 있어서, 상기 빈발 부분그래프의 DFS 코드는상기 빈발 부분 그래프에서 확장 순서로 확장된, 상기 빈발 부분그래프를 구성하는 부모 에지와 자식 에지의 DFS 코드를 구비하며,상기 부모 에지 또는 상기 자식 에지의 DFS 코드는 상기 부모 에지 및 자식 에지를 구성하는 2개의 버텍스, 상기 2개의 버텍스에 대한 레이블 및 상기 2개의 버텍스를 연결하는 에지 레이블를 구비하는 것을 특징으로 하는 빈발 부분그래프의 마이닝 방법
|
| 6 |
6
제 4 항에 있어서, 상기 정규 그래프 탐색 트리는상기 정규그래프를 구성하는 부모 에지와 자식 에지의 DFS 코드 및 상기 부모 에지로부터 상기 자식 에지로의 확장 포인터를 구비하는 것을 특징으로 하는 빈발 부분그래프 마이닝 방법
|
| 7 |
7
제 6 항에 있어서, 상기 정규 그래프 탐색 트리에서 상기 부모 에지의 DFS 코드 또는 자식 에지의 DFS 코드는 에지의 버텍스 레이블과 에지 레이블로 구성되는 에지 코드의 발생 빈도에 서로 다른 데이터로 표현되어 있는 것을 특징으로 하는 빈발 부분그래프 마이닝 방법
|
| 8 |
8
제 7 항에 있어서, 상기 에지 코드는 호프만 코드로 부호화되어 상기 정규 그래프 탐색 트리에 저장되어 있는 것을 특징으로 하는 빈발 부분그래프 마이닝 방법
|
| 9 |
9
컴퓨터에서 그래프 데이터베이스에 저장되어 있는 그래프로부터 도약 탐색 기반으로 빈발 부분그래프를 마이닝 방법에 있어서,(a) 그래프 데이터베이스로부터 최소 지지도를 만족하는 빈발 부분그래프를 추출하는 단계;(b) 상기 빈발 부분그래프의 각 에지의 확장 순서로 상기 각 에지의 깊이 우선 탐색 코드(depth first search code, 이하 DFS 코드)를 생성하는 단계;(c) 상기 각 에지의 DFS 코드와 정규 그래프 탐색 트리의 DFS 코드를 비교하여 상기 빈발 부분그래프가 최소 DFS 코드를 가지는 정규 그래프인지 판단하는 단계; 및(d) 상기 빈발 부분그래프가 정규 그래프인 경우 상기 빈발 부분그래프로부터 에지 확장되는지 판단하며, 상기 빈발 부분그래프로부터 에지 확장되는 경우 에지 확장한 상기 빈발 부분그래프에서 상기 최소 지지도를 만족하는 추가 빈발 부분그래프를 추출하는 단계를 포함하는 것을 특징으로 하는 빈발 부분그래프의 마이닝 방법
|
| 10 |
10
제 9 항에 있어서, 상기 빈발 부분그래프의 마이닝 방법은상기 최소 지지도가 변경되는 경우 변경된 최소 지지도로 상기 (a) 단계 내지 (d) 단계를 반복하여 상기 변경된 최소 지지도를 만족하는 빈발 부분그래프를 추출하는 것을 특징으로 하는 빈발 부분그래프의 마이닝 방법
|
| 11 |
11
컴퓨터에서 그래프 데이터베이스에 저장되어 있는 그래프로부터 모델 기반 탐색 트리 방식으로 빈발 부분그래프를 마이닝하는 방법에 있어서,(a) 그래프 데이터베이스로부터 추출한 빈발 부분그래프 중에서 선택한 제1 빈발 부분그래프를 포함하는 소그룹 그래프 데이터베이스를 생성하는 단계; (b) 상기 소그룹 그래프 데이터베이스에서 최소 지지도 이상으로 출현하는 소그룹 빈발 부분그래프를 추출하는 단계;(c) 상기 소그룹 빈발 부분그래프의 각 에지의 확장 순서로 생성한 상기 각 에지의 깊이 우선 탐색 코드(depth first search code, 이하 DFS 코드)와 정규 그래프 탐색 트리의 DFS 코드를 비교하여 상기 소그룹 빈발 부분그래프가 최소 DFS 코드를 가지는 정규 그래프인지 판단하는 단계;(d) 상기 소그룹 빈발 부분그래프가 정규 그래프인 경우 상기 소그룹 빈발 부분그래프로부터 에지 확장되는지 판단하며, 상기 소그룹 빈발 부분그래프로부터 에지 확장되는 경우 상기 소그룹 빈발 부분그래프의 에지를 확장하는 단계; 및(e) 에지 확장한 상기 소그룹 빈발 부분그래프에 대해 상기 (c) 단계 및 상기 (d) 단계를 반복하여 상기 소그룹 그래프 데이터베이스에 존재하는 모든 소그룹 빈발 부분그래프를 추출하는 단계를 포함하는 특징으로 하는 빈발 부분그래프의 마이닝 방법
|
| 12 |
12
제 11 항에 있어서, 상기 빈발 부분그래프의 마이닝 방법은상기 소그룹 그래프 데이터베이스를 구성하는 소그룹 빈발 부분그래프의 수가 임계수를 초과하는지 판단하는 단계; 및상기 소그룹 그래프 데이터베이스를 구성하는 소그룹 빈발 부분그래프의 수가 임계값을 초과하는 경우 상기 소그룹 그래프 데이터베이스에서 선택한 소그룹 빈발 부분그래프를 구비하는 제2 소그룹 그래프 데이터베이스를 생성하는 단계를 포함하며, 상기 제2 소그룹 그래프 데이터베이스에 대해 상기 (b) 단계 내지 (e) 단계를 수행하는 것을 특징으로 하는 빈발 부분그래프의 마이닝 방법
|
