| 1 |
1
대용량 그래프 데이터베이스에서 빈발 부분 그래프를 마이닝하는 장치에 있어서,다수개의 그래프 그룹으로 분리되어 있는 상기 대용량 그래프 데이터베이스 중 1개의 그래프 그룹이 분산 저장되어 있는 그래프 데이터베이스; 및상기 그래프 그룹을 구성하는 다수의 그래프에서 그래프 식별자별로 빈발 부분 그래프의 복원 그래프를 생성하여 상기 빈발 부분 그래프로부터 에지 확장 가능한 후보 부분 그래프를 생성하며, 상기 후보 부분 그래프의 수가 최소 지지도를 만족하는지를 판단하여 상기 빈발 부분 그래프로부터 에지 확장한 확장 빈발 부분 그래프를 생성하는 마이닝 모듈을 포함하는 것을 특징으로 하는 그래프 데이터베이스의 마이닝 장치
|
| 2 |
2
제 1 항에 있어서, 상기 마이닝 모듈은상기 그래프 그룹에서 최소 지지도를 만족하는 빈발 부분 그래프로부터 그래프 식별자별로 복원 그래프를 생성하며, 상기 복원 그래프에 기초하여 상기 빈발 부분 그래프로부터 에지 확장 가능한 후보 부분 그래프를 생성하는 에지 확장부; 및각 그래프에서 동일한 정규 코드를 가지는 후보 부분 그래프의 수가 최소 지지도를 만족하는지를 판단하여 상기 빈발 부분 그래프로부터 에지 확장한 확장 빈발 부분 그래프를 생성하는 생성부를 포함하며,상기 에지 확장부와 상기 생성부는 상기 확장 빈발 부분 그래프로부터 신규 확장 빈발 부분 그래프가 생성되지 않을 때까지 상기 확장 빈발 부분 그래프의 에지를 확장하여 상기 그래프 데이터베이스의 빈발 부분 그래프를 생성하는 것을 특징으로 하는 그래프 데이터베이스의 마이닝 장치
|
| 3 |
3
제 2 항에 있어서, 상기 에지 확장부는상기 그래프 그룹에서 최소 지지도를 만족하며 k(k는 자연수)개 에지를 가지는 빈발 부분 그래프가 입력되는 경우, 상기 빈발 부분 그래프와 상기 빈발 부분 그래프가 포함된 그래프 식별자로 출력 데이터를 생성하는 에지 확장 맵퍼; 및상기 출력 데이터의 그래프 식별자별로 구분하여 상기 빈발 부분 그래프의 복원 그래프를 생성하며, 상기 복원 그래프에 기초하여 상기 빈발 부분 그래프로부터 k+1개의 에지로 확장 가능한 후보 부분 그래프를 생성하는 에지 확장 리듀서를 포함하는 것을 특징으로 하는 그래프 데이터베이스의 마이닝 장치
|
| 4 |
4
제 3 항에 있어서, 상기 에지 확장 리듀서는동일한 그래프 식별자를 가지는 상기 빈발 부분 그래프에서 상기 빈발 부분 그래프를 구성하는 버텍스와 에지의 연결 관계에 기초하여 복원 그래프를 생성하는 것을 특징으로 하는 그래프 데이터베이스의 마이닝 장치
|
| 5 |
5
제 3 항에 있어서, 상기 에지 확장 리듀서는상기 복원 그래프와 상기 빈발 부분 그래프의 버텍스 및 에지의 연결 관계를 비교하여, 상기 빈발 부분 그래프의 버텍스로부터 연결된 에지가 존재하는지 여부로 후보 부분 그래프가 존재하는지 판단하는 것을 특징으로 하는 그래프 데이터베이스의 마이닝 장치
|
| 6 |
6
제 3 항에 있어서, 상기 생성부는상기 후보 부분 그래프를 정규화 연산하여 상기 후보 부분 그래프 중 정규 코드를 가지는 정규 후보 부분 그래프를 판단하여 상기 그래프 식별자별 상기 정규 후보 부분 그래프를 판단하는 카운팅 맵퍼; 및각 그래프에 존재하는 동일한 정규 코드를 가지는 정규 후보 부분 그래프의 수가 최소 지지도를 만족하는지를 판단하여 상기 빈발 부분 그래프로부터 에지 확장한 확장 빈발 부분 그래프를 생성하는 카운팅 리듀서를 포함하는 것을 특징으로 하는 데이터베이스 마이닝 장치
|
| 7 |
7
제 6 항에 있어서, 상기 카운팅 리듀서는상기 대용량 그래프 데이터베이스 중 다른 그래프 그룹이 분산 저장되어 있는 주변 데이터베이스 마이닝 장치로부터 상기 다른 그래프 그룹의 그래프 식별자별 정규 후보 부분 그래프를 수신하며, 상기 그래프 그룹과 상기 다른 그래프 그룹에서 동일한 정규 코드를 가지는 정규 후보 부분 그래프의 수가 최소 지지지도를 만족하는 확장 빈발 부분 그래프를 생성하는 것을 특징으로 하는 데이터베이스 마이닝 장치
|
| 8 |
8
대용량 그래프 데이터베이스에서 빈발 부분 그래프를 마이닝하는 방법에 있어서,상기 대용량 그래프 데이터베이스는 다수개의 그래프 그룹으로 분리되어 분산되어 있으며,에지 확장부에서 k(k는 자연수)개의 에지를 가지는 빈발 부분 그래프가 입력되는 경우 상기 그래프 그룹을 구성하는 다수의 그래프에서 그래프 식별자별로 상기 빈발 부분 그래프의 복원 그래프를 생성하여 상기 빈발 부분 그래프로부터 k+1개의 에지로 확장 가능한 후보 부분 그래프를 생성하는 단계; 및생성부에서 상기 후보 부분 그래프의 수가 최소 지지도를 만족하는지를 판단하여 상기 빈발 부분 그래프로부터 k+1개의 에지를 가지는 확장 빈발 부분 그래프를 생성하는 단계를 포함하며, 상기 확장 빈발 부분 그래프가 입력되어 k+2개의 에지를 가지는 신규 확장 빈발 부분 그래프가 생성되지 않을 때까지 상기 확장 빈발 부분 그래프의 에지를 확장하여 상기 그래프 데이터베이스의 빈발 부분 그래프를 반복 생성하는 것을 특징으로 하는 빈발 부분 그래프의 마이닝 방법
|
| 9 |
9
제 8 항에 있어서, 상기 에지 확장부에서 상기 후보 부분 그래프를 생성하는 단계는k개의 에지를 가지는 빈발 부분 그래프가 입력되는 단계;상기 빈발 부분 그래프가 포함된 그래프 식별자를 키 값으로 하여 상기 빈발 부분 그래프를 구비하는 출력 데이터로 생성하는 단계;동일한 그래프 식별자를 가지는 빈발 부분 그래프로부터 그래프 식별자별로 복원 그래프를 생성하는 단계; 및상기 복원 그래프에 기초하여 상기 빈발 부분 그래프로부터 에지 확장 가능한 후보 부분 그래프를 생성하는 단계를 포함하는 것을 특징으로 하는 빈발 부분 그래프의 마이닝 방법
|
| 10 |
10
제 9 항에 있어서, 상기 복원 그래프는 동일한 그래프 식별자를 가지는 상기 빈발 부분 그래프에서 상기 빈발 부분 그래프를 구성하는 버텍스와 에지의 연결 관계에 기초하여 생성되는 것을 특징으로 하는 빈발 부분 그래프의 마이닝 방법
|
| 11 |
11
제 10 항에 있어서, 상기 후보 부분 그래프는 상기 복원 그래프와 상기 빈발 부분 그래프의 버텍스 및 에지의 연결 관계를 비교하여, 상기 빈발 부분 그래프의 버텍스로부터 연결된 에지가 존재하는지 경우 생성되는 것을 특징으로 하는 빈발 부분 그래프의 마이닝 방법
|
| 12 |
12
제 9 항에 있어서, 상기 생성부에서 상기 확장 빈발 부분 그래프를 생성하는 단계는상기 후보 부분 그래프를 정규화 연산하여 상기 후보 부분 그래프의 정규 코드를 계산하는 단계; 상기 후보 부분 그래프 중 정규 코드를 가지는 정규 후보 부분 그래프를 판단하는 단계; 및각 그래프에 존재하는 동일한 정규 코드를 가지는 정규 후보 부분 그래프의 수가 최소 지지도를 만족하는지를 판단하여 상기 빈발 부분 그래프로부터 에지 확장한 확장 빈발 부분 그래프를 생성하는 단계를 포함하는 것을 특징으로 하는 빈발 부분 그래프의 마이닝 방법
|
| 13 |
13
제 12 항에 있어서, 상기 확장 빈발 부분 그래프를 생성하는 단계는상기 대용량 그래프 데이터베이스 중 다른 그래프 그룹이 분산 저장되어 있는 주변 데이터베이스 마이닝 장치로부터 상기 다른 그래프 그룹의 그래프 식별자별 정규 후보 부분 그래프를 수신하는 단계를 더 포함하며, 상기 그래프 그룹과 상기 다른 그래프 그룹에서 각 그래프에 존재하는 동일한 정규 코드를 가지는 정규 후보 부분 그래프의 수가 최소 지지도를 만족하는 확장 빈발 부분 그래프를 생성하는 것을 특징으로 하는 빈발 부분 그래프의 마이닝 방법
|
