| 1 |
1
서버가 하나 이상의 노드를 포함하는 그래프를 요약 및 압축하는 방법에 있어서,상기 노드 중 하나의 노드를 거쳐 연결되는 두 노드를 포함하는 노드 쌍을 추출하여 메모리에 저장하는 a단계;상기 노드 쌍의 압축비용을 연산하여 상기 압축비용이 기 설정된 임계 값 이상인 제1 노드 쌍을 식별하고, 상기 제1 노드 쌍을 병합하여 생성한 제1 슈퍼 노드를 상기 그래프에 추가하는 b단계;상기 메모리에 상기 제1 노드 쌍이 존재하지 않을 때까지 상기 a 내지 b단계를 반복하고, 상기 제1 노드 쌍이 존재하지 않으면 상기 메모리에 저장된 노드 쌍의 이익률을 연산하는 c단계;상기 이익률이 기 설정된 이익 임계 값 이상인 제2 노드 쌍을 식별하고, 상기 제2 노드 쌍을 병합하여 생성한 제2 슈퍼 노드를 상기 메모리에 추가하는 d단계;상기 제2 노드 쌍이 존재하지 않을 때까지 상기 c 내지 d단계를 반복하고, 상기 제2 노드 쌍이 존재하지 않으면, 상기 메모리에 존재하는 노드 쌍의 요약비용을 연산하는 단계;상기 노드 쌍의 상기 압축비용이 상기 요약비용 이상인 제3 노드 쌍을 압축하는 단계를 포함하는 그래프 요약 및 압축 방법
|
| 2 |
2
제1항에 있어서,상기 b단계에서 상기 제1 슈퍼 노드가 생성되면,상기 그래프에서 상기 제1 슈퍼 노드로 병합된 상기 제1 노드 쌍을 제거하는 단계;상기 그래프에 포함된 노드 중 하나의 노드를 거쳐 제1 슈퍼 노드와 연결되는 노드를 포함하는 제4 노드 쌍을 생성하는 단계;상기 메모리에 상기 제4 노드 쌍을 저장하는 단계를 더 포함하는 그래프 요약 및 압축 방법
|
| 3 |
3
제1항에 있어서,상기 d단계에서 상기 제2 슈퍼 노드가 생성되면,상기 그래프에서 상기 제2 슈퍼 노드로 병합된 상기 제2 노드 쌍을 제거하는 단계;상기 그래프에 포함된 노드 중 하나의 노드를 거쳐 제2 슈퍼 노드와 연결되는 노드를 포함하는 제5 노드 쌍을 생성하는 단계;상기 메모리에 상기 제5 노드 쌍을 저장하는 단계를 더 포함하는 그래프 요약 및 압축 방법
|
| 4 |
4
제1항에 있어서,상기 제2 노드 쌍은 상기 이익률이 높은 순으로 병합되는 그래프 요약 및 압축 방법
|
| 5 |
5
제1항에 있어서,상기 이익률은,상기 노드 쌍에 포함된 제5 노드, 제6 노드 및 상기 제5 노드와 상기 제6 노드가 포함된 슈퍼 노드에 대한 연산 비용을 이용하여 생성되고,상기 연산 비용은 각 노드에 대한 요약비용 및 압축비용 중 작은 값을 갖는 것을 의미하는 그래프 요약 및 압축 방법
|
| 6 |
6
제5항에 있어서,상기 이익률은 의 식을 통해 생성되고,u는 상기 제5 노드를, v는 상기 제6 노드를, z는 상기 제5 노드와 상기 제6 노드가 포함된 슈퍼 노드를, 그리고 Cost는 상기 연산 비용을 의미하는 그래프 요약 및 압축 방법
|
| 7 |
7
제1항에 있어서,상기 제3 노드 쌍을 압축하면, 상기 메모리에 남은 노드 쌍 중 상기 요약비용이 상기 압축비용 이상인 노드 쌍을 요약하는 단계를 포함하는 그래프 요약 및 압축 방법
|
| 8 |
8
하나 이상의 노드를 포함하는 그래프를 요약 및 압축하는 시스템에 있어서,상기 노드 중 하나의 노드를 거쳐 연결되는 두 노드를 포함하는 노드 쌍을 추출하여 메모리에 저장하는 저장부;상기 노드 쌍의 압축비용을 연산하여 상기 압축비용이 기 설정된 임계 값 이상인 제1 노드 쌍을 식별하고, 상기 제1 노드 쌍이 존재하지 않을 때까지 상기 제1 노드 쌍을 병합하여 생성한 제1 슈퍼 노드를 상기 그래프에 추가하는 1차 요약부;상기 제1 노드 쌍이 존재하지 않으면 상기 메모리에 저장된 노드 쌍의 이익률을 연산하고, 상기 이익률이 기 설정된 이익 임계 값 이상인 제2 노드 쌍을 식별하고, 상기 제2 노드 쌍이 존재하지 않을 때까지 상기 제2 노드 쌍을 병합하여 생성한 제2 슈퍼 노드를 상기 메모리에 추가하는 2차 요약부;상기 제2 노드 쌍이 존재하지 않으면, 상기 메모리에 존재하는 노드 쌍의 요약비용을 연산하고, 상기 노드 쌍의 압축비용이 상기 요약비용 이상인 제3 노드 쌍을 압축하는 압축부를 포함하는 그래프 요약 및 압축 시스템
|
| 9 |
9
제8항에 있어서,상기 1차 요약부는 상기 제1 슈퍼 노드가 생성되면,상기 그래프에서 상기 제1 슈퍼 노드로 병합된 상기 제1 노드 쌍을 제거하고, 상기 그래프에 포함된 노드 중 하나의 노드를 거쳐 제1 슈퍼 노드와 연결되는 노드를 포함하는 제4 노드 쌍을 생성하고, 상기 메모리에 상기 제4 노드 쌍을 저장하는 그래프 요약 및 압축 시스템
|
| 10 |
10
제8항에 있어서,상기 2차 요약부는 상기 제2 슈퍼 노드가 생성되면,상기 그래프에서 상기 제2 슈퍼 노드로 병합된 상기 제2 노드 쌍을 제거하고, 상기 그래프에 포함된 노드 중 하나의 노드를 거쳐 제2 슈퍼 노드와 연결되는 노드를 포함하는 제5 노드 쌍을 생성하고, 상기 메모리에 상기 제5 노드 쌍을 저장하는 그래프 요약 및 압축 시스템
|
| 11 |
11
제8항에 있어서,상기 제2 노드 쌍은 상기 이익률이 높은 순으로 병합되는 그래프 요약 및 압축 시스템
|
| 12 |
12
제8항에 있어서,상기 이익률은,상기 노드 쌍에 포함된 제5 노드, 제6 노드 및 상기 제5 노드와 상기 제6 노드가 포함된 슈퍼 노드에 대한 연산 비용을 이용하여 생성되고,상기 연산 비용은 각 노드에 대한 요약비용 및 압축비용 중 작은 값을 갖는 것을 의미하는 그래프 요약 및 압축 시스템
|
| 13 |
13
제12항에 있어서,상기 이익률은 의 식을 통해 생성되고,u는 상기 제5 노드를, v는 상기 제6 노드를, z는 상기 제5 노드와 상기 제6 노드가 포함된 슈퍼 노드를, 그리고 Cost는 상기 연산 비용을 의미하는 그래프 요약 및 압축 시스템
|
| 14 |
14
제8항에 있어서,상기 제3 노드 쌍을 압축하면, 상기 메모리에 남은 노드 쌍 중 상기 요약비용이 상기 압축비용 이상인 노드 쌍을 요약하는 3차 요약부를 포함하는 그래프 요약 및 압축 시스템
|
