| 1 |
1
서버가 에지 프루닝을 이용하여 대용량 그래프를 희소화하는 방법에 있어서,대용량 그래프에 포함된 적어도 하나의 노드를 식별하고, 상기 노드를 이용하여 인접 노드 리스트를 생성하는 a 단계;상기 인접 노드 리스트를 기반으로 상기 대용량 그래프에 포함된 임의의 제1 노드 및 제2 노드를 시작 노드로 하는 임의의 경로를 식별하고, 이를 기반으로 제1 노드 및 제2 노드 사이의 최단 경로를 식별하여 그에 대응하는 제1 가중치를 연산하는 b 단계;상기 제1 가중치와 상기 제1 노드 및 제2 노드의 에지에 대응하는 제2 가중치를 비교하여 상기 에지의 메트릭 정보를 설정하는 c 단계; 및상기 메트릭 정보에 따라 상기 에지를 프루닝하여 상기 대용량 그래프를 희소화하는 d 단계를 포함하는 대용량 그래프 희소화 방법
|
| 2 |
2
제1항에 있어서,상기 b 단계는,상기 제1 노드를 시작 노드로 하는 적어도 하나의 제1 임시 경로를 식별하는 단계;상기 제2 노드를 시작 노드로 하는 적어도 하나의 제2 임시 경로를 식별하는 단계;상기 제1 및 제2 임시 경로를 기반으로 제1 및 제2 노드 간의 제3 임시 경로를 적어도 하나 설정하는 단계;상기 제3 임시 경로에 대응하는 가중치 중 가장 작은 값을 갖는 것을 최단 경로로 설정하는 단계를 포함하되,상기 제1 및 제2 임시 경로를 식별하는 단계를 동시에 수행하는 것을 특징으로 하는 대용량 그래프 희소화 방법
|
| 3 |
3
제2항에 있어서,상기 제3 임시 경로를 설정하는 단계는,상기 제1 및 제2 임시 경로에 중복되는 제3 노드를 식별하고, 상기 제3 노드에서 상기 제1 및 제2 임시 경로가 교차하는 상기 제3 임시 경로를 설정하는 것을 특징으로 하는 대용량 그래프 희소화 방법
|
| 4 |
4
제1항에 있어서,상기 메트릭 정보는 메트릭 에지 및 세미 메트릭 에지를 포함하여,상기 c 단계는,상기 제1 가중치가 상기 제2 가중치보다 값이 크면 상기 에지를 메트릭 에지로 설정하고, 그렇지 않으면 세미 메트릭 에지로 설정하는 것을 특징으로 하는 대용량 그래프 희소화 방법
|
| 5 |
5
제4항에 있어서,상기 d 단계는,상기 에지가 세미 메트릭 에지이면, 상기 에지를 프루닝하는 것을 특징으로 하는 대용량 그래프 희소화 방법
|
| 6 |
6
에지 프루닝을 이용하여 대용량 그래프를 희소화하는 장치에 있어서,대용량 그래프에 포함된 적어도 하나의 노드를 식별하고, 상기 노드를 이용하여 인접 노드 리스트를 생성하는 리스트 생성부;상기 인접 노드 리스트를 기반으로 상기 대용량 그래프에 포함된 임의의 제1 노드 및 제2 노드 사이의 최단 경로를 식별하고, 그에 대응하는 제1 가중치를 연산하며, 상기 제1 가중치와 상기 제1 노드 및 제2 노드의 에지에 대응하는 제2 가중치를 비교하여 상기 에지의 메트릭 정보를 설정하는 메트릭 관리부; 및상기 메트릭 정보에 따라 상기 에지를 프루닝하여 상기 대용량 그래프를 희소화하는 프루닝부를 포함하는 대용량 그래프 희소화 장치
|
| 7 |
7
제6항에 있어서,상기 메트릭 제어부는,상기 제1 및 제2 노드를 시작 노드로 하는 적어도 하나의 제1 및 제2 임시 경로를 각각 식별하고, 상기 제1 및 제2 임시 경로에서 중복되는 제3 노드를 식별하여, 상기 제3 노드에서 상기 제1 및 제2 임시 경로가 교차하는 적어도 하나의 제3 임시 경로를 설정하며, 상기 제3 임시 경로에 대응하는 가중치 중 가장 작은 값을 갖는 것을 최단 경로로 설정하는 것을 특징으로 하는 대용량 그래프 희소화 장치
|
| 8 |
8
제6항에 있어서,상기 메트릭 정보는 메트릭 에지 및 세미 메트릭 에지를 포함하여,상기 메트릭 관리부는,상기 제1 가중치가 상기 제2 가중치보다 값이 크면 상기 에지를 메트릭 에지로 설정하고, 그렇지 않으면 세미 메트릭 에지로 설정하는 것을 특징으로 하는 대용량 그래프 희소화 장치
|
| 9 |
9
제8항에 있어서,상기 프루닝부는,상기 에지가 세미 메트릭 에지이면, 상기 에지를 프루닝하는 것을 특징으로 하는 대용량 그래프 희소화 장치
|
