| 摘要 |
위와 같은 과제를 해결하기 위한 본 발명의 일 측면에 따르면, 디스크에 저장된 데이터 그래프에 대하여 질의 그래프에 대한 서브 그래프 리스팅 방법에 있어서, 상기 디스크로부터 메모리의 내부 구역에 상기 데이터 그래프의 일부를 로드 하는 단계; 내부 메인 스레드가 상기 메모리에 로드 된 정점에 대하여 내부 서브 그래프 리스팅을 수행하는 단계; 외부 메인 스레드가 메모리의 피벗 구역 및 외부 구역에 데이터 정점의 로드를 추가적으로 요청하고 추가 스레드가 메모리에 로드 된 정점에 대하여 외부 서브 그래프 리스팅을 수행하는 단계;를 포함하되, 상기 내부 메인 스레드와 상기 외부 메인 스레드 및 상기 추가 스레드의 수행이 일정 기간 이상 오버랩 되어 동시에 수행되는 것을 특징으로 하는 서브 그래프 리스팅 방법이 제공된다. 본 발명의 서브 그래프 리스팅 방법에 의하면 데이터 그래프가 큰 경우라도, 디스크 접근 횟수를 최소화하여 데이터 그래프의 질의 그래프에 대한 서브 그래프 리스팅을 효율적으로 수행할 수 있다. 본 발명의 서브 그래프 리스팅 방법에 의하면, 질의 그래프를 R B I 그래프로 변환하고 후보 트리를 사용함으로써, 대규모의 데이터 그래프에 대하여 디스크의 I/O 횟수를 대폭 감소 시킬 수 있다. 본 발명의 서브 그래프 리스팅 방법은 메모리 버퍼를 내부, 피벗 및 외부 서브 구역으로 구별하고, 내부 서브 그래프 리스팅 및 피벗 구역과 외부 구역의 서브 그래프 리스팅을 멀티 스레드로 오버 래핑하여 독립적으로 수행할 수 있어 수행 속도를 크게 개선할 수 있다. 특히, 본 발명의 서브 그래프 리스팅 방법은 메인 스레드에 의한 디스크 I/O 시간 동안 추가 스레드로 외부 서브 그래프 리스팅을 오버래핑으로 동시에 수행할 수 있어 수행 속도를 개선하게 된다. 또한, 본 발명의 서브 그래프 리스팅 방법은 깊이 우선 탐색을 기반으로 한 R B I 매핑 방식을 이용하여 R B I 매핑 중간 결과를 저장하지 않아 저장 공간의 오버헤드 없이 효과적으로 R B I 매핑을 수행할 수 있다. 이와 같이, 본 발명의 서브 그래프 리스팅 방법은 멀티 스레드를 지원하여 스레드 증가에 따라 수행 속도가 비례하여 증가하게 된다. |
