| 1 |
1
워크로드 규모 분석에 따른 적응형 그래프 탐색 방법에 있어서,(a) 탐색 대상 그래프의 정점 정보 및 간선 정보를 이용하여 상기 탐색 대상 그래프의 그래프 특성 정보를 추출하는 단계;(b) 상기 그래프 특성 정보를 이용하여 상기 탐색 대상 그래프와 연계된 워크로드 규모를 분류하는 단계; 및(c) 상기 워크로드 규모에 기초하여 상기 탐색 대상 그래프에 대하여 적용될 탐색 알고리즘을 결정하고, 상기 결정된 탐색 알고리즘을 실행하는 단계,를 포함하되,상기 (b) 단계는,상기 워크로드 규모를 미리 설정된 하한값 미만 범위에 대응하는 제1레벨, 미리 설정된 상한값 이상 범위에 대응하는 제3레벨 및 상기 하한값 이상이고 상기 상한값 미만인 범위에 대응하는 제2레벨 중 어느 하나로 판단하는 것이고,상기 (c) 단계는,상기 워크로드 규모가 상기 제1레벨 또는 상기 제2레벨이면, 푸시(Push) 기반의 너비 우선 탐색 알고리즘을 상기 탐색 알고리즘으로 결정하고, 상기 워크로드 규모가 상기 제3레벨이면, 풀(Pull) 기반의 너비 우선 탐색 알고리즘을 상기 탐색 알고리즘으로 결정하는 것이고,상기 (c) 단계에서 상기 제1레벨에 따른 상기 탐색 알고리즘과 상기 제2레벨에 따른 상기 탐색 알고리즘은 상기 탐색 대상 그래프에서 활성 정점을 식별하기 위한 확인 알고리즘의 원자 조작(Atomic Operation)의 수행 횟수가 상이한 것이되,상기 (c) 단계는,상기 워크로드 규모가 상기 제1레벨이면, 상기 확인 알고리즘으로 원자 조작(Atomic Operation)의 수행 횟수가 2회로 설계된 활성 정점 큐 생성 기법을 적용하고, 상기 워크로드 규모가 상기 제2레벨이면, 상기 확인 알고리즘으로 원자 조작(Atomic Operation)의 수행 횟수가 1회로 설계된 활성 정점 큐 생성 기법을 적용하고, 상기 워크로드 규모가 상기 제3레벨이면, 상기 확인 알고리즘으로 상태 배열 확인 기법을 적용하는 것을 특징으로 하는, 탐색 방법
|
| 2 |
2
삭제
|
| 3 |
3
삭제
|
| 4 |
4
삭제
|
| 5 |
5
삭제
|
| 6 |
6
제1항에 있어서,상기 (a) 단계는,상기 탐색 대상 그래프에 포함된 각각의 정점에 연결된 간선의 개수의 평균에 대한 제1기준 정보 및 상기 각각의 정점이 중심 정점에 해당할 확률에 대한 제2기준 정보를 포함하는 상기 그래프 특성 정보를 도출하는 것인, 탐색 방법
|
| 7 |
7
제6항에 있어서,상기 (b) 단계는,(b1) 상기 제1기준 정보 및 상기 제2기준 정보에 기초하여 상기 탐색 대상 그래프에서 상기 중심 정점을 탐색하기 위한 제1반복 횟수와 상기 탐색 대상 그래프에서 상기 중심 정점 외의 정점을 탐색하기 위한 제2반복 횟수를 연산하는 단계;(b2) 상기 제1기준 정보, 상기 제2기준 정보, 상기 제1반복 횟수 및 상기 제2반복 횟수 중 적어도 하나에 기초하여 탐색 방식 선택 매개변수를 연산하는 단계; 및(b3) 상기 연산된 탐색 방식 선택 매개변수에 기초하여 상기 워크로드 규모를 상기 제1레벨 내지 상기 제3레벨 중 어느 하나로 판단하는 단계,를 포함하는, 탐색 방법
|
| 8 |
8
제1항에 있어서,상기 (c) 단계는,상기 탐색 대상 그래프에서 활성 정점을 식별하기 위한 확인 알고리즘의 유형을 상기 워크로드 규모에 기초하여 결정하는 것인, 탐색 방법
|
| 9 |
9
제1항에 있어서,상기 (a) 단계 내지 상기 (c) 단계는,이전 반복 회차에서 탐색된 상기 정점 정보 및 상기 간선 정보를 이용하여 상기 탐색 대상 그래프를 갱신하면서 입력된 그래프 데이터에 포함된 전체 정점 각각의 연결 관계가 식별되도록 반복 수행되는 것인, 탐색 방법
|
| 10 |
10
워크로드 규모 분석에 따른 적응형 그래프 탐색 장치에 있어서,탐색 대상 그래프의 정점 정보 및 간선 정보를 이용하여 상기 탐색 대상 그래프의 그래프 특성 정보를 추출하는 그래프 분석부;상기 그래프 특성 정보를 이용하여 상기 탐색 대상 그래프와 연계된 워크로드 규모를 분류하는 워크로드 분석부; 및상기 워크로드 규모에 기초하여 상기 탐색 대상 그래프에 대하여 적용될 탐색 알고리즘을 결정하고, 상기 결정된 탐색 알고리즘을 실행하는 적응적 탐색 수행부,를 포함하되,상기 워크로드 분석부는,상기 워크로드 규모를 미리 설정된 하한값 미만 범위에 대응하는 제1레벨, 미리 설정된 상한값 이상 범위에 대응하는 제3레벨 및 상기 하한값 이상이고 상기 상한값 미만인 범위에 대응하는 제2레벨 중 어느 하나로 판단하는 것이고,상기 적응적 탐색 수행부는,상기 워크로드 규모가 상기 제1레벨 또는 상기 제2레벨이면, 푸시(Push) 기반의 너비 우선 탐색 알고리즘을 상기 탐색 알고리즘으로 결정하고, 상기 워크로드 규모가 상기 제3레벨이면, 풀(Pull) 기반의 너비 우선 탐색 알고리즘을 상기 탐색 알고리즘으로 결정하여 상기 탐색 알고리즘을 적응적으로 결정하는 것이고,상기 제1레벨에 따른 상기 탐색 알고리즘과 상기 제2레벨에 따른 상기 탐색 알고리즘은 상기 탐색 대상 그래프에서 활성 정점을 식별하기 위한 확인 알고리즘의 원자 조작(Atomic Operation)의 수행 횟수가 상이한 것이되,상기 적응적 탐색 수행부는,상기 워크로드 규모가 상기 제1레벨이면, 상기 확인 알고리즘으로 원자 조작(Atomic Operation)의 수행 횟수가 2회로 설계된 활성 정점 큐 생성 기법을 적용하고, 상기 워크로드 규모가 상기 제2레벨이면, 상기 확인 알고리즘으로 원자 조작(Atomic Operation)의 수행 횟수가 1회로 설계된 활성 정점 큐 생성 기법을 적용하고, 상기 워크로드 규모가 상기 제3레벨이면, 상기 확인 알고리즘으로 상태 배열 확인 기법을 적용하는 것을 특징으로 하는, 탐색 장치
|
| 11 |
11
삭제
|
| 12 |
12
삭제
|
| 13 |
13
삭제
|
| 14 |
14
제10항에 있어서,상기 그래프 분석부는,상기 탐색 대상 그래프에 포함된 각각의 정점에 연결된 간선의 개수의 평균에 대한 제1기준 정보 및 상기 각각의 정점이 중심 정점에 해당할 확률에 대한 제2기준 정보를 포함하는 상기 그래프 특성 정보를 도출하는 것인, 탐색 장치
|
| 15 |
15
제14항에 있어서,상기 워크로드 분석부는,상기 제1기준 정보 및 상기 제2기준 정보에 기초하여 상기 탐색 대상 그래프에서 상기 중심 정점을 탐색하기 위한 제1반복 횟수와 상기 탐색 대상 그래프에서 상기 중심 정점 외의 정점을 탐색하기 위한 제2반복 횟수를 연산하고, 상기 제1기준 정보, 상기 제2기준 정보, 상기 제1반복 횟수 및 상기 제2반복 횟수 중 적어도 하나에 기초하여 탐색 방식 선택 매개변수를 연산하고, 상기 연산된 탐색 방식 선택 매개변수에 기초하여 상기 워크로드 규모를 상기 제1레벨 내지 상기 제3레벨 중 어느 하나로 판단하는 것인, 탐색 장치
|
