| 1 |
1
프로세서가 포함된 장치에서, 그래프 데이터베이스에 저장되어 있는 다수의 유향 그래프에 대한 유향 동시발생 부분그래프를 생성하는 방법에 있어서, 상기 다수의 유향 그래프를 대상으로 복수의 빈발 부분그래프를 생성하는 단계; 상기 다수의 유향 그래프 각각의 부분시퀀스의 트리(다수의 부분시퀀스 트리)를 생성하는 단계 - 상기 부분시퀀스는 유향 그래프에 포함되는 복수의 버텍스가 순차적으로 에지로 연결되어 있는 데이터 시퀀스이고, 상기 부분시퀀스 트리는 상기 유향 그래프에 존재하는 부분시퀀스 간의 순서를 나타내는 데이터 트리임 - ; 및상기 다수의 부분시퀀스 트리를 이용하여 상기 복수의 빈발 부분그래프 간의 순서관계를 찾고, 상기 순서관계를 이용하여 상기 유향 동시발생 부분그래프를 생성하는 단계;를 포함하는 것을 특징으로 하는 유향 동시발생 부분그래프 생성 방법
|
| 2 |
2
제1항에 있어서, 상기 부분시퀀스 트리를 구성하는 노드 각각은 하나의 부분시퀀스와 대응되고, 상기 부분시퀀스 트리를 생성하는 단계는, 루트노드를 기준으로 하여 순차적으로 노드를 생성해 가면서 상기 부분시퀀스 트리를 생성하되, 상기 노드와 대응되는 부분시퀀스에 포함되는 버텍스를 갱신함으로써 상기 부분시퀀스 트리를 생성하는 것을 특징으로 하는 유향 동시발생 부분그래프 생성 방법
|
| 3 |
3
제2항에 있어서, 상기 부분시퀀스 트리를 생성하는 단계는, 상기 노드 중 제1 노드와 대응되는 부분시퀀스의 마지막 버텍스의 외향 에지의 개수가 0인 경우, 상기 제1 노드와 대응되는 부분시퀀스에 포함되는 버텍스를 갱신하지 않고 확정하며, 새로운 노드를 생성하지 않고, 상기 제1 노드와 대응되는 부분시퀀스의 마지막 버텍스의 외향 에지의 개수가 1인 경우, 상기 마지막 버텍스의 외향 에지를 수신하는 하나의 버텍스를 상기 제1 노드와 대응되는 부분시퀀스에 추가하여 갱신하고, 상기 제1 노드와 대응되는 부분시퀀스의 마지막 버텍스의 외향 에지의 개수가 2인 경우, 상기 마지막 버텍스의 외향 에지를 수신하는 2개의 버텍스를 검색하고, 상기 2개의 버텍스 중 하나의 버텍스를 상기 제1 노드의 자식노드인 제2 노드와 대응되는 부분시퀀스에 추가하여 갱신하고, 상기 2개의 버텍스 중 다른 버텍스를 상기 제1 노드의 또 다른 자식노드인 제3 노드와 대응되는 부분시퀀스에 추가하여 갱신하는 것을 특징으로 하는 유향 동시발생 부분그래프 생성 방법
|
| 4 |
4
제3항에 있어서, 상기 부분시퀀스의 트리를 생성하는 단계는,상기 유향 그래프의 버텍스들 중 내향 에지가 0인 버텍스를 검색하고, 상기 내향 에지가 0인 버텍스를 상기 부분시퀀스 트리의 루트노드의 자식노드의 첫번째 버텍스로 추가하는 것을 특징으로 하는 유향 동시발생 부분그래프 생성 방법
|
| 5 |
5
제1항에 있어서, 상기 유향 동시발생 부분그래프를 생성하는 단계는, 상기 복수의 빈발 부분그래프에 대해, 빈발 부분그래프 A와 빈발 부분그래프 B로 구성된 빈발 부분그래프 쌍들을 생성하고, 상기 빈발 부분그래프 쌍들 각각을 대상으로 하여, 빈발 부분그래프 쌍과 상기 다수의 부분시퀀스 트리 각각을 비교하여, 빈발 부분그래프 A와 빈발 부분그래프 B의 순서관계가 만족되는 부분그래프가 최소 지지도 이상 출현하는 경우 상기 빈발 부분그래프 쌍을 상기 유향 동시발생 부분그래프로 판단함으로써 상기 유향 동시발생 부분그래프를 생성하는 것을 특징으로 하는 유향 동시발생 부분그래프 생성 방법
|
| 6 |
6
제1항 내지 제5항 중 어느 한 항의 방법을 수행하는 프로그램을 기록한 컴퓨터 판독 가능 기록 매체
|
| 7 |
7
그래프 데이터베이스에 저장되어 있는 다수의 유향 그래프에 대한 유향 동시발생 부분그래프를 생성하는 장치에 있어서, 상기 다수의 유향 그래프를 대상으로 복수의 빈발 부분그래프를 생성하는 빈발 부분그래프 마이닝부;상기 다수의 유향 그래프 각각의 부분시퀀스의 트리(다수의 부분시퀀스 트리)를 생성하는 부분시퀀스 트리 생성부 - 상기 부분시퀀스는 유향 그래프에 포함되는 복수의 버텍스가 순차적으로 에지로 연결되어 있는 데이터 시퀀스이고, 상기 부분시퀀스 트리는 상기 유향 그래프에 존재하는 부분시퀀스 간의 순서를 나타내는 데이터 트리임 -; 및 상기 다수의 부분시퀀스 트리를 이용하여 상기 복수의 빈발 부분그래프 간의 순서관계를 찾고, 상기 순서관계를 이용하여 상기 유향 동시발생 부분그래프를 생성하는 유향 동시발생 부분그래프 생성부;를 포함하는 것을 특징으로 하는 유향 동시발생 부분그래프 생성 장치
|
| 8 |
8
제7항에 있어서, 상기 부분시퀀스 트리를 구성하는 노드 각각은 하나의 부분시퀀스와 대응되고, 상기 부분시퀀스 트리 생성부는 루트노드를 기준으로 하여 순차적으로 노드를 생성해 가면서 상기 부분시퀀스 트리를 생성하되, 상기 노드와 대응되는 부분시퀀스에 포함되는 버텍스를 갱신함으로써 상기 부분시퀀스 트리를 생성하는 것을 특징으로 하는 유향 동시발생 부분그래프 생성 장치
|
| 9 |
9
제8항에 있어서, 상기 부분시퀀스 트리 생성부는, 상기 노드 중 제1 노드와 대응되는 부분시퀀스의 마지막 버텍스의 외향 에지의 개수가 0인 경우, 상기 제1 노드와 대응되는 부분시퀀스에 포함되는 버텍스를 갱신하지 않고 확정하며, 새로운 노드를 생성하지 않고, 상기 제1 노드와 대응되는 부분시퀀스의 마지막 버텍스의 외향 에지의 개수가 1인 경우, 상기 마지막 버텍스의 외향 에지를 수신하는 하나의 버텍스를 상기 제1 노드와 대응되는 부분시퀀스에 추가하여 갱신하고, 상기 제1 노드와 대응되는 부분시퀀스의 마지막 버텍스의 외향 에지의 개수가 2인 경우, 상기 마지막 버텍스의 외향 에지를 수신하는 2개의 버텍스를 검색하고, 상기 2개의 버텍스 중 하나의 버텍스를 상기 제1 노드의 자식노드인 제2 노드와 대응되는 부분시퀀스에 추가하여 갱신하고, 상기 2개의 버텍스 중 다른 버텍스를 상기 제1 노드의 또 다른 자식노드인 제3 노드와 대응되는 부분시퀀스에 추가하여 갱신하는 것을 특징으로 하는 유향 동시발생 부분그래프 생성 장치
|
| 10 |
10
제7항에 있어서, 상기 유향 동시발생 부분그래프 생성부는, 상기 복수의 빈발 부분그래프에 대해, 빈발 부분그래프 A와 빈발 부분그래프 B로 구성된 빈발 부분그래프 쌍들을 생성하고, 상기 빈발 부분그래프 쌍들 각각을 대상으로 하여, 빈발 부분그래프 쌍과 상기 다수의 부분시퀀스 트리 각각을 비교하여, 빈발 부분그래프 A와 빈발 부분그래프 B의 순서관계가 만족되는 부분그래프가 최소 지지도 이상 출현하는 경우 상기 빈발 부분그래프 쌍을 상기 유향 동시발생 부분그래프로 판단함으로써 상기 유향 동시발생 부분그래프를 생성하는 것을 특징으로 하는 유향 동시발생 부분그래프 생성 장치
|
