| 1 |
1
대용량 그래프 데이터베이스에서 순환 그래프를 검색하는 방법에 있어서,상기 대용량 그래프 데이터베이스는 다수개의 그래프 그룹으로 분리되어 분산되어 있으며,각 상기 그래프 그룹을 구성하는 버텍스 중 기준 버텍스에 직접 연결되어 있는 모든 이웃 버텍스로부터 순차적 순환 경로상의 버텍스 식별자를 구비하는 이웃 식별 메시지를 수신하는 단계;상기 이웃 식별 메시지에 기준 버텍스의 식별자가 포함되어 있는지 여부에 기초하여 상기 기준 버텍스에서 시작하여 상기 기준 버텍스로 종료하는 순환 그래프를 검색하는 단계;상기 기준 버텍스로 종료하는 순환 그래프가 검색되지 않는 경우, 상기 기준 버텍스의 식별자를 상기 이웃 버텍스의 식별자에 순차적으로 추가하여 기준 식별 메시지를 생성하는 단계; 및상기 기준 식별 메시지를 상기 기준 버텍스에 직접 연결되어 있는 이웃 버텍스로 송신하는 단계를 포함하는 것을 특징으로 하는 순환 그래프의 분산 검색 방법
|
| 2 |
2
삭제
|
| 3 |
3
제 1 항에 있어서, 상기 순환 그래프를 검색하는 단계는상기 이웃 식별 메시지의 순차적 순환 경로에서 기준 버텍스가 시작 버텍스인지 판단하는 단계;상기 기준 버텍스가 시작 버텍스인 경우 상기 기준 버텍스로 시작하여 상기 기준 버텍스로 종료하는 순차적 순환 경로 상의 버텍스로 이루어진 버텍스 조합을 생성하는 단계; 및상기 생성한 버텍스 조합을 순환 그래프로 검색하는 단계를 포함하는 것을 특징으로 하는 순환 그래프의 분산 검색 방법
|
| 4 |
4
제 3 항에 있어서, 상기 순환 그래프를 검색하는 단계는검색한 순환 그래프의 버텍스 조합을 구성하는 버텍스 식별자에 기초하여 상기 검색한 순환 그래프의 버텍스 조합의 동일 여부로 상기 검색한 순환 그래프가 중복 순환 그래프인지 판단하는 단계를 더 포함하는 것을 특징으로 하는 순환 그래프의 분산 검색 방법
|
| 5 |
5
제 4 항에 있어서, 상기 중복 순환 그래프에서 시작 버텍스가 가장 작은 값을 가지는 정규 순환 그래프만을 선택하고, 나머지 중복 순환 그래프를 제거하는 단계를 더 포함하는 것을 특징으로 하는 순환 그래프의 분산 검색 방법
|
| 6 |
6
제 1 항, 제 3 항 내지 제 5 항 중 어느 한 항에 있어서,상기 그래프 그룹에서 다른 그래프 그룹과의 경계에 위치하는 경계 버텍스는 다른 그래프 그룹에서 상기 경계 버텍스에 연결되어 있는 주변 버텍스의 식별자 정보를 가지고 있는 것을 특징으로 하는 순환 그래프의 분산 검색 방법
|
| 7 |
7
대용량 그래프 데이터베이스에서 순환 그래프를 검색하는 장치에 있어서,다수개의 그래프 그룹으로 분리되어 있는 상기 대용량 그래프 데이터베이스 중 1개의 그래프 그룹이 분산 저장되어 있는 그래프 데이터베이스; 및상기 그래프 그룹을 구성하는 각 버텍스에서 인접하는 버텍스로부터 순차적 순환 경로상의 식별 메시지를 수신하여 상기 그래프 그룹에 존재하는 순환 그래프를 검색하는 검색 모듈을 포함하는 것을 특징으로 하는 순환 그래프의 분산 검색 장치
|
| 8 |
8
제 7 항에 있어서, 상기 검색 모듈은상기 그래프 그룹을 구성하는 버텍스 중 기준 버텍스에 직접 연결되어 있는 모든 이웃 버텍스로부터 수신한, 순차적 순환 경로상의 버텍스 식별자를 구비하는 이웃 식별 메시지에 상기 기준 버텍스의 식별자가 포함되어 있는지 여부에 기초하여 상기 기준 버텍스에서 시작하여 상기 기준 버텍스로 종료하는 순환 그래프를 검색하는 검색부; 및상기 기준 버텍스로 종료하는 순환 그래프가 검색되지 않는 경우, 상기 기준 버텍스의 식별자를 상기 이웃 버텍스의 식별자에 추가하여 기준 식별 메시지를 생성하고, 상기 기준 식별 메시지를 상기 기준 버텍스에 직접 연결되어 있는 이웃 버텍스로 송신하는 기준 식별 메시지 생성부를 포함하는 것을 특징으로 하는 순환 그래프의 분산 검색 장치
|
| 9 |
9
삭제
|
| 10 |
10
제 8 항에 있어서, 상기 검색부는상기 이웃 식별 메시지의 순차적 순환 경로에서 기준 버텍스가 시작 버텍스인지 판단하는 시작 버텍스 판단부;상기 기준 버텍스가 시작 버텍스인 경우 상기 기준 버텍스로 시작하여 상기 기준 버텍스로 종료하는 순차적 순환 경로 상의 버텍스로 이루어진 버텍스 조합을 생성하는 버텍스 조합 생성부; 및상기 생성한 버텍스 조합으로 이루어진 그래프를 순환 그래프로 검색하는 순환 그래프 검색부를 포함하는 것을 특징으로 하는 순환 그래프의 분산 검색 장치
|
| 11 |
11
제 10 항에 있어서, 상기 순환 그래프의 분산 검색 장치는검색한 순환 그래프의 버텍스 조합을 구성하는 버텍스 식별자에 기초하여 상기 검색한 순환 그래프의 버텍스 조합의 동일 여부로 상기 검색한 순환 그래프가 중복 순환 그래프인지 판단하는 중복 판단부를 더 포함하는 것을 특징으로 하는 순환 그래프의 분산 검색 장치
|
| 12 |
12
제 11 항에 있어서, 상기 중복 판단부는상기 중복 순환 그래프에서 시작 버텍스가 가장 작은 값을 가지는 정규 순환 그래프만을 선택하고, 나머지 중복 순환 그래프를 제거하는 것을 특징으로 하는 순환 그래프의 분산 검색 장치
|
| 13 |
13
제 7 항, 제 8 항, 제 10 항 내지 제 12 항 중 어느 한 항에 있어서, 상기 데이터베이스는상기 그래프 그룹에서 다른 그래프 그룹과의 경계에 위치하는 경계 버텍스에 연결되어 있는 주변 버텍스의 식별자 정보를 가지고 있는 것을 특징으로 하는 순환 그래프의 분산 검색 장치
|
