| 1 |
1
질의 그래프(q)로부터 시작 질의의 정점(us)을 선택하는 단계;상기 질의 그래프(q)로부터 너비 우선 탐색(BFS) 트리(q')를 획득하는 단계;상기 선택된 각 시작 정점에 대하여 상기 BFS 트리(q')의 루트 정점(u's)으로부터 데이터 그래프(g)를 순회하면서 후보 지역을 탐색하는 단계;상기 탐색된 임의의 후보 지역에 대하여 매칭 순서를 결정하는 단계;상기 BFS 트리(q')의 상기 시작 정점(us')을 그 후보 지역의 시작 정점(vs)에 매핑하는 단계; 및 각 후보 영역에 대한 모든 가능한 사상을 생성하는 단계를 포함하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 2 |
2
제 1 항에 있어서, 상기 선택하는 단계는, 상기 모든 질의의 정점(u)의 순위를 빈도 및 차수에 따라 정의하는 단계;상기 순위 중 상위 k개의 질의 정점을 선택하는 단계;상기 상위 k개의 질의 정점(u)에 대한 후보 지역의 개수를 예측하는 단계; 및상기 후보 지역의 개수가 가장 작은 정점을 상기 시작 질의의 정점으로 선택하는 단계를 포함하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 3 |
3
제 2 항에 있어서, 상기 정의하는 단계는 상기 빈도가 작을수록 또는 상기 차수가 높을수록 우선 순위를 부여하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 4 |
4
제 2 항에 있어서, 상기 예측하는 단계는 상기 질의 정점(u)의 차수가 상기 후보 지역에 속하는 각 정점(v)의 차수보다 작거나 같은지를 검사하고, 상기 질의 정점(u)에 인접한 정점들 중 레이블이 l인 정점의 개수가 상기 후보 지역에 속하는 정점(v)에 인접한 정점들 중 레이블이 l인 정점의 개수보다 작거나 같은지를 검사하여, 상기 두 조건을 모두 만족하는 후보 지역들의 개수를 예측하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 5 |
5
제 1 항에 있어서, 상기 획득하는 단계는 상기 BFS 트리(q')에 매칭하는 후보 지역의 크기가 작게 되도록 상기 BFS 트리(q')를 생성하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 6 |
6
제 1 항에 있어서, 상기 탐색하는 단계는, 상기 BFS 트리(q')의 상기 질의 정점(u')에 대한 후보 데이터 정점들(VM)에 방문되지 않은 데이터 정점(v')에 대하여 식별 조건을 만족하는지를 판단하는 단계;상기 식별 조건을 만족하는 데이터 정점(v')을 방문한 것으로 마크하고, 상기 질의 정점(u')의 자식 질의 정점(u'c)들을 데이터 정점(v')에 인접하고 레이블이 같은 정점들의 개수에 따라 정렬하는 단계;상기 데이터 정점(v')의 부분 트리들이 상기 질의 정점(u')의 부분 트리들과 매치하는지를 판단하는 단계;상기 부분 트리들이 매치하면, 상기 데이터 정점(v')의 마크의 상태를 리셋하고 후보 부분 지역(CR(u',v))에 추가하는 단계; 및 데이터 정점(v')을 모두 방문한 경우, 후보 부분 지역(CR(u',v)에 속하는 데이터 정점의 개수가 1 미만이면, 후보 지역 모두를 삭제하는 단계;를 포함하는, 지역 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 7 |
7
제 6 항에 있어서, 상기 식별 조건을 판단하는 단계는 상기 질의 정점(u')의 차수가 상기 데이터 정점(v')의 차수보다 작거나 같은지와, 상기 질의 정점(u')에 인접한 정점들 중 레이블이 l인 정점의 개수가 상기 후보 지역에 속하는 정점(v')에 인접한 정점들 중 레이블이 l인 정점의 개수보다 작거나 같은지를 검사하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 8 |
8
제 6 항에 있어서, 상기 식별 조건을 만족하지 않는 데이터 정점(v')의 부분 트리를 순회하지 않고 제거하는 단계를 추가로 포함하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 9 |
9
제 6 항에 있어서,상기 부분 트리들이 매치하지 않으면, 상기 데이터 정점(v')의 부분 트리에서 방문된 모든 정점들에 대한 후보 지역을 삭제하는 단계를 더 포함하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 10 |
10
제 2 항에 있어서,상기 결정하는 단계는,선택되지 않은 후보 정점들의 수가 최소인 경로를 선택하는 단계; 및 후보 정점의 개수에 대한 예측값이 가장 작은 질의 정점을 포함하는 질의 경로에 대응하는 데이터 그래프(g) 상의 경로로부터 부분 그래프 동형 매칭을 수행하는 단계를 포함하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 11 |
11
제 1 항에 있어서,상기 생성하는 단계는, 임의의 BFS 트리(q')의 정점(u')에 대하여, 후보 부분 지역들을 획득하는 단계;상기 후보 부분 지역에 속하는 임의의 데이터 정점(v')이 이미 매치되었으면 이 조합을 안전하게 제거하는 단계;상기 BFS 트리(q')의 정점(u')에 대하여, 상기 정점(u')과 상기 질의 그래프(q)의 이미 매치된 질의 정점들 사이의 간선들이 이미 매치된 데이터 정점(v')들 사이의 대응하는 간선들을 갖는지를 검사하는 단계;상기 간선 조건을 만족하면, 해당 데이터 정점(v')을 대응하는 질의 정점(u)에 매핑하고, 상태 정보를 갱신하는 단계; 단말 질의 정점을 방문중이면, 매치되는 사상 개수를 증가시키는 단계; 및모든 사상을 찾았으면, 결과를 출력하는 단계를 포함하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 12 |
12
제 11 항에 있어서,상기 모든 사상을 찾지 않았으면, 변경되었던 상태 정보를 복원하고, 상기 안전하게 제거하는 단계로 복귀하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 13 |
13
제 6 항에 있어서,상기 추가하는 단계 이후에, 상기 BFS 트리(q')의 각 단말에 대하여, 상기 후보 지역 탐색에서 획득한 정점들의 개수가 k를 초과하는지를 판단하는 단계; 및 상기 정점들의 개수가 k개를 초과하면, 더 이상 탐색하지 않고, 찾은 후보 정점들에 대하여 부분 그래프 동형 검사를 수행하는 단계를 더 포함하고, 적정 부분 그래프 동형이 검색될 때까지 다른 후보 정점들에 대하여 상기 후보 지역을 탐색하는 단계, 상기 초과하는지를 판단하는 단계 및 상기 검사를 수행하는 단계를 반복적으로 수행하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 방법
|
| 14 |
14
질의 그래프(q)로부터 시작 질의의 정점(us)을 선택하고, 상기 질의 그래프(q)로부터 너비 우선 탐색(BFS) 트리(q')를 획득하는 질의 재작성부;상기 선택된 각 시작 정점에 대하여 상기 BFS 트리(q')의 루트 정점(us')으로부터 데이터 그래프(g)를 순회하면서 후보 지역을 탐색하는 후보 지역 탐색부;상기 탐색된 임의의 후보 지역에 대하여 매칭 순서를 결정하고, 상기 BFS 트리(q')의 상기 시작 정점(us')을 그 후보 지역의 시작 정점(vs)에 매핑하며, 각 후보 영역에 대한 모든 가능한 사상을 생성하는 부분 그래프 동형 매칭부; 및 상기 데이터 그래프(g)가 저장되는 데이터베이스를 포함하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 시스템
|
| 15 |
15
제 14 항에 있어서, 상기 질의 재작성부는 상기 모든 질의의 정점(u)의 순위를 빈도 및 차수에 따라 정의하여 상위 k개의 질의 정점을 선택하고, 상기 각 질의의 정점(u)에 대한 후보 지역의 개수를 예측하여 상기 후보 지역의 개수가 가장 작은 정점을 상기 시작 질의의 정점으로 선택하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 시스템
|
| 16 |
16
제 14 항에 있어서,상기 후보 지역 탐색부는 입력 질의 트리에 의해 유도된 임의의 후보 지역을 그 지역의 시작 정점으로부터 깊이 우선 탐색하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 시스템
|
| 17 |
17
제 14 항에 있어서, 상기 부분 그래프 동형 매칭부는 상기 BFS 트리(q')의 각 단말에 대하여, 상기 후보 지역 탐색에서 획득한 정점들의 개수가 k를 초과하는지를 판단하여 k개를 초과하면, 더 이상 탐색하지 않고, 찾은 후보 정점들에 대하여 부분 그래프 동형 검사를 수행하고, k개를 초과하지 않으면 다른 후보 정점들에 대한 후보 지역을 탐색하는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 시스템
|
| 18 |
18
제 14 항에 있어서,상기 데이터 그래프는 정점 레이블로 정렬된 ID 리스트를 접근하기 위한 역 정점 레이블 리스트, 및 자신의 인접 정보를 저장하고 있는 각 정정별 인접 리스트롤 포함하는 구조를 갖는, 후보 영역 탐색 기법을 활용한 부분 그래프 동형 검색 시스템
|
