1 |
1
정점(vertex)과 간선(edge)을 포함하는 위상 데이터로 구성된 원본 그래프 데이터를 주 기억 장치에 저장하는 단계;해시 함수(hash function) 및 상기 원본 그래프 데이터를 이용하여 부모 간선(edge)을 결정하는 단계;상기 부모 간선에 기초하여 새로운 간선을 생성하는 단계; 및상기 새로운 간선의 아이디에 기초하여 현재 규모 계수를 결정하는 단계를 포함하고,상기 부모 간선을 결정하는 단계는상기 부모 간선의 방향을 결정하는 단계;상기 새로운 간선의 아이디에 대한 해시 함수값을 결정하는 단계; 및상기 해시 함수값, 상기 현재 규모 계수, 및 상기 원본 그래프의 간선의 수에 기초하여 상기 부모 간선의 아이디를 결정하는 단계를 포함하고,상기 단계들은 적어도 하나의 프로세서에 의해서 수행되는 그래프 증폭 방법
|
2 |
2
제1항에 있어서,상기 부모 간선을 결정하는 단계는상기 새로운 간선을 위한 제1 부모 간선이 상기 원본 그래프 데이터에 포함되는지 판단하는 단계;상기 제1 부모 간선이 상기 원본 그래프 데이터에 포함되지 않는다는 판단에 따라 재귀적 연산을 수행함으로써, 상기 제1 부모 간선을 위한 제2 부모 간선을 결정하는 단계; 및상기 제2 부모 간선에 기초하여 상기 제1 부모 간선을 결정하는 단계를 포함하는 그래프 증폭 방법
|
3 |
3
제1항에 있어서,상기 새로운 간선의 아이디에 기초하여 현재 규모 계수(scale factor)를 결정하는 단계를 더 포함하고,상기 부모 간선은 상기 현재 규모 계수에 더 기초하여 결정되는, 그래프 증폭 방법
|
4 |
4
삭제
|
5 |
5
삭제
|
6 |
6
제1항에 있어서,상기 부모 간선의 방향을 결정하는 단계는상기 새로운 간선의 아이디에 대한 해시 함수값을 결정하는 단계; 및상기 해시 함수값에 기초하여 상기 부모 간선의 방향을 결정하는 단계를 포함하는 그래프 증폭 방법
|
7 |
7
제1항에 있어서,상기 새로운 간선을 생성하는 단계는상기 부모 간선의 두 정점들 중 어느 하나의 정점을 기초로, 참조 정점을 결정하는 단계; 및상기 두 정점들 중 나머지 하나의 정점과 상기 참조 정점을 기초로, 상기 새로운 간선을 결정하는 단계를 포함하는 그래프 증폭 방법
|
8 |
8
제7항에 있어서,상기 새로운 간선을 결정하는 단계는상기 부모 간선의 방향이 제1 논리값인 경우, 상기 새로운 간선의 타겟 정점을 상기 참조 정점으로 결정하는 단계; 및상기 부모 간선의 방향이 제2 논리값인 경우, 상기 새로운 간선의 소스 정점을 상기 참조 정점으로 결정하는 단계를 포함하는 그래프 증폭 방법
|
9 |
9
제7항에 있어서,상기 참조 정점의 아이디는상기 부모 간선의 두 정점들 중 어느 하나의 정점의 아이디, 상기 원본 그래프의 정점의 수, 및 현재 규모 계수에 기초하여 결정되는 그래프 증폭 방법
|
10 |
10
제1항에 있어서,상기 새로운 간선을 상기 주 기억 장치의 버퍼에 임시 저장하는 단계를 더 포함하는 그래프 증폭 방법
|
11 |
11
제10항에 있어서,상기 버퍼에 저장된 데이터의 양에 기초하여, 상기 버퍼에 저장된 그래프를 보조 기억 장치로 비동기적으로 저장하는 단계를 더 포함하는 그래프 증폭 방법
|
12 |
12
정점(vertex)과 간선(edge)을 포함하는 위상 데이터로 구성된 원본 그래프 데이터를 주 기억 장치에 저장하는 단계;중앙 처리 장치에 포함된 코어들의 개수에 기초하여, 생성할 간선들의 아이디를 상기 코어들로 할당하는 단계; 및상기 코어들 각각에서, 해시 함수와 상기 원본 그래프 데이터를 이용하여 상기 할당된 아이디에 따라 상기 원본 그래프 데이터의 간선의 수와 최종 규모 계수의 곱에 대응하는 수를 충족할 때까지 새로운 간선들을 생성하는 단계를 포함하고,상기 단계들은 적어도 하나의 프로세서에 의해서 수행되는 그래프 증폭 방법
|
13 |
13
삭제
|
14 |
14
삭제
|
15 |
15
제12항에 있어서,상기 코어들은 동일한 상기 해시 함수를 사용하는 그래프 증폭 방법
|
16 |
16
제12항에 있어서,상기 새로운 간선들을 상기 주 기억 장치의 버퍼에 임시 저장하는 단계; 및상기 버퍼에 저장된 데이터의 양에 기초하여, 상기 버퍼에 저장된 그래프를 보조 기억 장치로 비동기적으로 저장하는 단계를 더 포함하는 그래프 증폭 방법
|
17 |
17
제12항에 있어서,상기 새로운 간선들은 상기 코어들에 의해 병렬적으로 생성되는 그래프 증폭 방법
|
18 |
18
하드웨어와 결합되어 제1항 내지 제3항, 제6항 내지 제12항, 및 제15항 내지 제17항 중 어느 하나의 항의 방법을 실행시키기 위하여 기록 매체에 저장된 컴퓨터 프로그램
|
19 |
19
정점(vertex)과 간선(edge)을 포함하는 위상 데이터로 구성된 원본 그래프 데이터를 주 기억 장치에 저장하고, 해시 함수 및 상기 원본 그래프 데이터를 이용하여 부모 간선(edge)을 결정하며, 상기 부모 간선에 기초하여 새로운 간선을 생성하고, 상기 새로운 간선의 아이디에 기초하여 현재 규모 계수를 결정하고, 상기 부모 간선의 방향을 결정하고, 상기 새로운 간선의 아이디에 대한 해시 함수값을 결정하고, 상기 해시 함수값, 상기 현재 규모 계수, 및 상기 원본 그래프의 간선의 수에 기초하여 상기 부모 간선의 아이디를 결정하는 프로세서를 포함하는 그래프 증폭 장치
|
20 |
20
복수의 코어들을 포함하는 중앙 처리 장치; 및정점(vertex)과 간선(edge)을 포함하는 위상 데이터로 구성된 원본 그래프 데이터를 주 기억 장치에 저장하고, 상기 코어들의 개수에 기초하여, 생성할 간선들의 아이디를 상기 코어들로 할당하는 컨트롤러를 포함하고,상기 코어들 각각은 해시 함수와 상기 원본 그래프 데이터를 이용하여 상기 할당된 아이디에 따라 상기 원본 그래프 데이터의 간선의 수와 최종 규모 계수의 곱에 대응하는 수를 충족할 때까지 새로운 간선들을 생성하는, 그래프 증폭 장치
|