| 1 |
1
질의 그래프 및 데이터 그래프 간의 연속적 부분 그래프 매칭 방법에 있어서,질의 그래프로부터 루트가 있는 DAG(Directed Acyclic Graph)를 획득하는 단계;데이터 그래프 및 상기 DAG에 기반하여 상기 질의 그래프와 상기 데이터 그래프 간의 연속적 부분 그래프 매칭을 위한 동적 후보 공간(Dynamic Candidate Space; DCS)을 획득하는 단계; 및상기 데이터 그래프의 갱신 작업에 따라 상기 동적 후보 공간을 이용하여 상기 연속적 부분 그래프 매칭을 탐색하는 단계를 포함하고,상기 동적 후보 공간은,상기 질의 그래프의 정점에 대한 상기 데이터 그래프의 후보 정점의 집합;상기 후보 정점에서, 상기 질의 그래프의 정점에 대응하는 상기 DAG의 정점을 루트로 하는 역방향 부분 DAG의 임베딩과 연계된 제 1 임베딩 정보; 및상기 후보 정점에서, 상기 질의 그래프의 정점에 대응하는 상기 DAG의 정점을 루트로 하는 부분 DAG의 임베딩과 연계된 제 2 임베딩 정보를 포함하는,연속적 부분 그래프 매칭 방법
|
| 2 |
2
제 1 항에 있어서,상기 DAG를 획득하는 단계는,너비 우선 탐색으로 상기 질의 그래프를 탐색하면서 먼저 방문한 정점에서 다음 방문한 정점으로 간선의 방향을 설정하는 단계; 및가장 높은 높이의 DAG를 만드는 정점을 상기 DAG의 루트로 결정하는 단계를 포함하는,연속적 부분 그래프 매칭 방법
|
| 3 |
3
제 1 항에 있어서,상기 갱신 작업이 간선 삽입인 경우, 상기 연속적 부분 그래프 매칭을 탐색하는 단계는,상기 간선 삽입에 따라 상기 데이터 그래프를 갱신하는 단계;갱신된 상기 데이터 그래프에 기반하여 상기 동적 후보 공간을 갱신하는 단계; 및상기 데이터 그래프에 새로 생기는 상기 질의 그래프의 임베딩을 탐색하는 단계를 포함하는,연속적 부분 그래프 매칭 방법
|
| 4 |
4
제 1 항에 있어서,상기 갱신 작업이 간선 삭제인 경우, 상기 연속적 부분 그래프 매칭 관계를 탐색하는 단계는,상기 데이터 그래프에서 삭제되는 상기 질의 그래프의 임베딩을 탐색하는 단계;상기 간선 삭제에 따라 상기 데이터 그래프를 갱신하는 단계; 및갱신된 상기 데이터 그래프에 기반하여 상기 동적 후보 공간을 갱신하는 단계를 포함하는,연속적 부분 그래프 매칭 방법
|
| 5 |
5
제 1 항에 있어서,상기 후보 정점의 집합은 상기 질의 그래프의 정점의 레이블과 동일한 레이블을 갖는 상기 데이터 그래프의 정점의 집합인,연속적 부분 그래프 매칭 방법
|
| 6 |
6
질의 그래프 및 데이터 그래프 간의 연속적 부분 그래프 매칭 장치에 있어서,적어도 하나의 명령어를 저장하는 메모리; 및프로세서를 포함하고, 상기 적어도 하나의 명령어는 상기 프로세서에 의해 실행될 때 상기 프로세서로 하여금,질의 그래프로부터 루트가 있는 DAG(Directed Acyclic Graph)를 획득하고,데이터 그래프 및 상기 DAG에 기반하여 상기 질의 그래프와 상기 데이터 그래프 간의 연속적 부분 그래프 매칭을 위한 동적 후보 공간(Dynamic Candidate Space; DCS)을 획득하고,상기 데이터 그래프의 갱신 작업에 따라 상기 동적 후보 공간을 이용하여 상기 연속적 부분 그래프 매칭을 탐색하도록 구성되고,상기 동적 후보 공간은,상기 질의 그래프의 정점에 대한 상기 데이터 그래프의 후보 정점의 집합;상기 후보 정점에서, 상기 질의 그래프의 정점에 대응하는 상기 DAG의 정점을 루트로 하는 역방향 부분 DAG의 임베딩과 연계된 제 1 임베딩 정보; 및상기 후보 정점에서, 상기 질의 그래프의 정점에 대응하는 상기 DAG의 정점을 루트로 하는 부분 DAG의 임베딩과 연계된 제 2 임베딩 정보를 포함하는,연속적 부분 그래프 매칭 장치
|
| 7 |
7
제 6 항에 있어서,상기 적어도 하나의 명령어는 상기 프로세서에 의해 실행될 때 상기 프로세서로 하여금, 상기 DAG를 획득하기 위하여,너비 우선 탐색으로 상기 질의 그래프를 탐색하면서 먼저 방문한 정점에서 다음 방문한 정점으로 간선의 방향을 설정하고,가장 높은 높이의 DAG를 만드는 정점을 상기 DAG의 루트로 결정하도록 구성되는,연속적 부분 그래프 매칭 장치
|
| 8 |
8
제 6 항에 있어서,상기 적어도 하나의 명령어는 상기 프로세서에 의해 실행될 때 상기 프로세서로 하여금, 상기 갱신 작업이 간선 삽입인 경우, 상기 연속적 부분 그래프 매칭을 탐색하기 위하여,상기 간선 삽입에 따라 상기 데이터 그래프를 갱신하고,갱신된 상기 데이터 그래프에 기반하여 상기 동적 후보 공간을 갱신하고,상기 데이터 그래프에 새로 생기는 상기 질의 그래프의 임베딩을 탐색하도록 구성되는,연속적 부분 그래프 매칭 장치
|
| 9 |
9
제 6 항에 있어서,상기 적어도 하나의 명령어는 상기 프로세서에 의해 실행될 때 상기 프로세서로 하여금, 상기 갱신 작업이 간선 삭제인 경우, 상기 연속적 부분 그래프 매칭 관계를 탐색하기 위하여,상기 데이터 그래프에서 삭제되는 상기 질의 그래프의 임베딩을 탐색하고,상기 간선 삭제에 따라 상기 데이터 그래프를 갱신하고,갱신된 상기 데이터 그래프에 기반하여 상기 동적 후보 공간을 갱신하도록 구성되는,연속적 부분 그래프 매칭 장치
|
| 10 |
10
제 6 항에 있어서,상기 후보 정점의 집합은 상기 질의 그래프의 정점의 레이블과 동일한 레이블을 갖는 상기 데이터 그래프의 정점의 집합인,연속적 부분 그래프 매칭 장치
|
| 11 |
11
프로세서에 의해 제 1 항 내지 제 5 항 중 어느 한 항에 따른 연속적 부분 그래프 매칭 방법을 실행하기 위한 적어도 하나의 명령어를 포함하는 컴퓨터 프로그램을 저장한 컴퓨터 판독가능한 비 일시적 기록 매체
|
