| 요약 |
본 발명은 단일머신 상의 대규모 그래프에서 서브그래프를 병렬적으로 열거하는 방법에 관한 것으로, 본 발명은 a) 대칭-파괴 알고리즘을 이용하여 질의 그래프로부터 부분 순서들(partial orders)의 세트(PO)를 검출하는 단계와, b) 상기 부분순서들의 세트(PO)를 이용하여 RBI(Red, Black, Ivory) 질의 그래프(qRBI)및 적색 질의 그래프(qR)를 생성하는 단계와, c) 상기 RBI 질의 그래프를 이용하여 모든 v-그룹 시퀀스들을 검출하고, 모든 v-그룹 시퀀스들을 고려하여 글로벌 매칭 순서를 검출하는 단계와, d) 상기 글로벌 매칭 순서를 이용하여 각 v-그룹 시퀀스에 대한 v-그룹 포리스트(forest)를 구축하는 단계와, e) v-그룹 포리스트의 모든 루트 노드에 대한 후보 정점/페이지 시퀀스들을 초기화하는 단계와, f) 레벨 1에서 병합된 정점 윈도우(mvw1)와 페이지 윈도우(mpw1)를 획득하는 단계와, g) 상기 페이지 윈도우(mpw1)의 각 페이지마다, 페이지를 비동기 판독하는 단계와, h) 상기 병합된 정점 윈도우로부터 연결된 모든 외부 서브그래프를 찾도록 재귀 함수 DelegateExternalSubgraphEnumeration(·)를 인보크(invoke)하고, 메인 스레드는 외부 서브그래프를 나머지 스레드들에 위임한 후, 메인 스레드는 내부 영역에 로딩된 페이지들을 이용하여 내부 서브그래프 열거를 실행하는 단계를 포함한다.
|
