기술명: 중첩 오버래핑 기반의 서브 그래프 리스팅

기술분류: 정보통신

출원인: 포항공과대학교 산학협력단

키워드: 중첩 오버래핑,서브 그래프,피벗 구역,

특허출원번호: 10-2016-60129170

기술개요

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

출처: NTB