| 1 |
1
복수의 정점(vertex)들 중 어느 하나의 소스 정점(source vetex)을 인식하는 단계;상기 정점들 사이에서 생성하고자 하는 간선(edge)들의 전체 타겟 간선 수 중에서, 상기 소스 정점으로부터 생성하고자 하는 적어도 하나의 간선의 타겟 간선 수를 획득하는 단계;상기 소스 정점에 대해 간선의 존재 여부의 확인이 요구되는 스코프(scope) 내에서, 적어도 하나의 간선을 생성하는데 반복적으로 이용되는 재귀 벡터(recursive vector)를 획득하는 단계; 및상기 타겟 간선 수 및 상기 재귀 벡터에 기초하여, 상기 소스 정점 및 적어도 하나의 목적지 정점(destination vertex) 사이의 적어도 하나의 간선을 생성하는 단계를 포함하고,상기 스코프는 상기 정점들의 정점 수에 기초하여 결정되고,상기 단계들은 적어도 하나의 프로세서에 의해서 수행되는그래프 생성 방법
|
| 2 |
2
제1항에 있어서,상기 타겟 간선 수를 획득하는 단계는미리 정의된 확률 파라미터들에 기초하여, 상기 소스 정점으로부터 연결되는 간선이 생길 확률을 생성하는 단계; 및상기 확률 및 상기 전체 타겟 간선 수에 따르는 통계적 분포에 기초하여, 상기 소스 정점으로부터 생성하고자 하는 적어도 하나의 간선의 타겟 간선 수를 생성하는 단계를 포함하는,그래프 생성 방법
|
| 3 |
3
제2항에 있어서,상기 확률은 총합이 1인 확률 파라미터들과 상기 소스 정점에 대응하는 이진 스트링의 1의 비트 수에 기초하여 생성되는,그래프 생성 방법
|
| 4 |
4
제2항에 있어서,상기 확률을 생성하는 단계는를 이용하여 상기 소스 정점으로부터 연결되는 간선이 생길 확률을 계산하는 단계를 포함하고,상기 는 상기 확률이고, 상기 u는 상기 소스 정점에 대응하는 이진 스트링이고, 상기 ~는 비트 NOT 연산자(bitwise NOT operator)이고, Bits(x)는 논리적 비트 연산자(logical bit operator)로서 이진 스트링 x에서 1의 비트 수를 반환하며, 상기 는 총합이 1인 확률 파라미터들인,그래프 생성 방법
|
| 5 |
5
제2항에 있어서,상기 타겟 간선 수를 생성하는 단계는정규 분포 N(np, np(1-p))를 따르는 랜덤 변수를 생성하는 단계를 포함하고,상기 n은 상기 전체 타겟 간선 수이고, 상기 p는 상기 확률인,그래프 생성 방법
|
| 6 |
6
제1항에 있어서,상기 재귀 벡터를 획득하는 단계는미리 정의된 확률 파라미터들에 기초하여, 상기 소스 정점으로부터 연결되는 간선이 생길 확률을 생성하는 단계; 및상기 확률, 상기 확률 파라미터들 및 상기 정점들의 정점 수에 기초하여, 인덱스들에 각각 대응하는 요소들의 값들을 갖는 재귀 벡터를 생성하는 단계를 포함하는,그래프 생성 방법
|
| 7 |
7
제6항에 있어서,상기 재귀 벡터를 생성하는 단계는를 이용하여, 미리 정의된 조건을 만족하는 인덱스들 별로 재귀 벡터의 요소들의 값들을 생성하는 단계를 포함하고,상기 는 인덱스이고, 상기 는 상기 에 대응하는 상기 재귀 벡터의 요소의 값이고, 상기 는 총합이 1인 확률 파라미터들이고, 상기 은 상기 정점 수이고, 상기 ≫는 논리적 오른쪽 시프트(logical right shift) 연산자이고, 상기 는 논리적 비트 연산자(logical bit operator)로서 이진 스트링 에서 1의 비트 수를 반환하며, 상기 는 상기 확률인,그래프 생성 방법
|
| 8 |
8
제7항에 있어서,상기 미리 정의된 조건은 인,그래프 생성 방법
|
| 9 |
9
제1항에 있어서,상기 재귀 벡터의 길이는 이고, 상기 은 상기 정점 수인,그래프 생성 방법
|
| 10 |
10
제1항에 있어서,상기 재귀 벡터는 CPU(Central Processing Unit) 캐시(cache)에 저장되는,그래프 생성 방법
|
| 11 |
11
삭제
|
| 12 |
12
제1항에 있어서,상기 간선을 생성하는 단계는상기 타겟 간선 수만큼 간선이 생성될 때까지, 상기 재귀 벡터에 대한 이진 탐색을 반복적으로 수행하여 적어도 하나의 목적지 정점을 결정하고, 상기 결정된 목적지 정점에 대응하는 적어도 하나의 간선을 생성하는 단계를 포함하는,그래프 생성 방법
|
| 13 |
13
제1항에 있어서,상기 간선을 생성하는 단계는상기 재귀 벡터 및 상기 정점들의 정점 수에 기초하여 랜덤 변수(random value)를 생성하는 단계;상기 재귀 벡터를 이용하여 상기 랜덤 변수에 대응하는 목적지 정점을 결정하는 단계; 및상기 소스 정점 및 상기 목적지 정점 사이의 간선을 생성하는 단계를 포함하는,그래프 생성 방법
|
| 14 |
14
제13항에 있어서,상기 간선을 생성하는 단계는기 생성된 적어도 하나의 간선의 수와 상기 타겟 간선 수를 비교하는 단계; 및상기 비교 결과에 기초하여, 상기 소스 정점 및 제2 목적지 정점 사이의 제2 간선을 생성하는 단계를 더 포함하는,그래프 생성 방법
|
| 15 |
15
제13항에 있어서,상기 랜덤 변수를 생성하는 단계는상기 정점 수에 대응하는 상기 재귀 벡터의 요소(element)의 값에 기초하여, 랜덤 변수를 생성하는 단계를 포함하는,그래프 생성 방법
|
| 16 |
16
제15항에 있어서,상기 랜덤 변수는 0과 RecVec[log|V|] 사이의 값이고,상기 은 상기 정점 수이고, 상기 RecVec[log|V|]는 상기 log|V|에 대응하는 상기 재귀 벡터의 요소의 값인,그래프 생성 방법
|
| 17 |
17
제13항에 있어서,상기 목적지 정점을 결정하는 단계는상기 랜덤 변수 및 상기 재귀 벡터에 따른 미리 정의된 조건을 만족하는 적어도 하나의 인덱스를 결정하는 단계; 및상기 결정된 적어도 하나의 인덱스에 기초하여 목적지 정점을 결정하는 단계를 포함하는,그래프 생성 방법
|
| 18 |
18
제13항에 있어서,상기 목적지 정점을 결정하는 단계는상기 랜덤 변수 및 상기 재귀 벡터에 따른 미리 정의된 조건을 만족하는 제1 인덱스를 결정하는 단계;상기 제1 인덱스 및 상기 재귀 벡터에 기초하여, 상기 제1 인덱스에 대응하는 대칭 비율을 생성하는 단계;상기 랜덤 변수, 상기 재귀 벡터 및 상기 대칭 비율에 기초하여, 제2 랜덤 변수를 생성하는 단계;상기 제2 랜덤 변수 및 상기 재귀 벡터에 따른 미리 정의된 조건을 만족하는 제2 인덱스를 결정하는 단계; 및제3 랜덤 변수 및 상기 재귀 벡터에 따른 미리 정의된 조건을 만족하는 인덱스가 존재하지 않는 경우, 기 생성된 적어도 하나의 인덱스에 기초하여 목적지 정점을 결정하는 단계를 포함하는,그래프 생성 방법
|
| 19 |
19
제13항에 있어서,상기 목적지 정점을 결정하는 단계는를 만족하는 인덱스 를 결정하는 단계;상기 에 대응하는 대칭 비율 를 생성하는 단계;제2 랜덤 변수 을 생성하는 단계;인 인덱스 를 결정하는 단계; 및제3 랜덤 변수 및 상기 재귀 벡터에 따른 미리 정의된 조건을 만족하는 인덱스가 존재하지 않는 경우, 목적지 정점을 로 결정하는 단계를 포함하고,상기 는 상기 랜덤 변수이고, 상기 는 상기 에 대응하는 상기 재귀 벡터의 요소의 값인,그래프 생성 방법
|
| 20 |
20
복수의 정점들로부터 각각 생성하고자 하는 간선들의 타겟 간선 수들에 기초하여, 복수의 계산노드들이 처리해야 할 정점들을 상기 계산노드들로 할당하는 단계;계산노드에서, 적어도 하나의 간선을 생성하는데 반복적으로 이용되는 재귀 벡터에 기초하여, 상기 정점들 중 어느 하나의 소스 정점의 단위로 그래프를 생성하는 단계;상기 계산노드가 처리해야 할 정점 범위가 존재하는 경우, 상기 계산노드에 의해 제2 소스 정점의 단위로 그래프를 생성하는 단계; 및상기 계산노드가 처리해야 할 정점 범위가 존재하지 않는 경우, 상기 소스 정점의 단위로 생성된 그래프를 저장하는 단계를 포함하고,상기 소스 정점의 단위로 그래프를 생성하는 단계는상기 소스 정점에 대해 간선의 존재 여부의 확인이 요구되는 스코프(scope) 내에서 상기 소스 정점 및 적어도 하나의 목적지 정점 사이의 적어도 하나의 간선을 생성하는 단계를 포함하고,상기 단계들은 적어도 하나의 프로세서에 의해서 수행되는,그래프 생성 방법
|
| 21 |
21
제20항에 있어서,상기 계산노드들이 처리해야 할 정점들을 할당하는 단계는미리 정의된 확률 파라미터들 및 상기 정점들 사이에서 생성하고자 하는 간선들의 전체 타겟 간선 수에 기초하여, 상기 정점들의 타겟 간선 수들을 생성하는 단계;상기 전체 타겟 간선 수 및 상기 계산노드들의 수에 기초하여 상기 정점들을 상기 계산노드들 별로 분할하고, 상기 분할된 정점들을 결합하여 정점 범위들을 생성하는 단계;상기 전체 타겟 간선 수 및 상기 계산노드들의 수에 기초하여, 상기 생성된 정점 범위들을 상기 계산노드들 별로 재분할하는 단계; 및상기 계산노드들 별로 재분할된 정점 범위들에 기초하여, 상기 계산노드들이 처리해야 할 정점들을 상기 계산노드들로 할당하는 단계를 포함하는,그래프 생성 방법
|
| 22 |
22
제20항에 있어서,상기 정점들에 대응하는 그래프들은 상기 할당된 정점들 별로 상기 계산노드들에 의해 병렬적으로 처리되는,그래프 생성 방법
|
| 23 |
23
제20항에 있어서,상기 재귀 벡터는 상기 계산노드의 CPU(Central Processing Unit) 캐시(cache)에 저장되는,그래프 생성 방법
|
| 24 |
24
삭제
|
| 25 |
25
제20항에 있어서,상기 소스 정점의 단위로 생성된 그래프를 상기 계산노드의 버퍼에 임시로 저장하는 단계; 및상기 버퍼에 저장된 데이터의 양에 기초하여, 상기 버퍼에 저장된 그래프를 상기 계산노드의 보조 기억 장치로 비동기적으로 저장하는 단계를 더 포함하는,그래프 생성 방법
|
| 26 |
26
하드웨어와 결합되어 제1항 내지 제10항, 제12항 내지 제23항 및 제25항 중 어느 하나의 항의 방법을 실행시키기 위하여 기록 매체에 저장된 컴퓨터 프로그램
|
| 27 |
27
복수의 정점들 중 어느 하나의 소스 정점을 인식하고,상기 정점들 사이에서 생성하고자 하는 간선들의 전체 타겟 간선 수 중에서, 상기 소스 정점으로부터 생성하고자 하는 적어도 하나의 간선의 타겟 간선 수를 획득하고,상기 소스 정점에 대해 간선의 존재 여부의 확인이 요구되는 스코프 내에서, 적어도 하나의 간선을 생성하는데 반복적으로 이용되는 재귀 벡터를 획득하고,상기 타겟 간선 수 및 상기 재귀 벡터에 기초하여, 상기 소스 정점 및 적어도 하나의 목적지 정점 사이의 적어도 하나의 간선을 생성하는 프로세서를 포함하고,상기 스코프는 상기 정점들의 정점 수에 기초하여 결정되는,그래프 생성 장치
|
| 28 |
28
복수의 정점들로부터 각각 생성하고자 하는 간선들의 타겟 간선 수들에 기초하여, 복수의 계산노드들이 처리해야 할 정점들을 상기 계산노드들로 할당하는 콘트롤러; 및적어도 하나의 간선을 생성하는데 반복적으로 이용되는 재귀 벡터에 기초하여, 상기 정점들 중 어느 하나의 소스 정점의 단위로 그래프를 생성하고,처리해야 할 정점 범위가 존재하는 경우, 제2 소스 정점의 단위로 그래프를 생성하며,처리해야 할 정점 범위가 존재하지 않는 경우, 상기 소스 정점의 단위로 생성된 그래프를 저장하는 계산노드를 포함하고,상기 계산노드는상기 소스 정점에 대해 간선의 존재 여부의 확인이 요구되는 스코프(scope) 내에서 상기 소스 정점 및 적어도 하나의 목적지 정점 사이의 적어도 하나의 간선을 생성하는,그래프 생성 장치
|
