서브 그래프 매칭 장치에 의해 구현되는 슬라이딩 윈도우 기반 연속 서브 그래프 매칭 방법에 있어서,상기 서브 그래프 매칭 장치의 색인 관리자(Index Manager)에서, 입력되는 질의에 대해, 최대 포함 경로(Max covering Path)에 따라 경로 별 색인하는 단계;상기 색인 관리자에서, 상기 경로 별 색인에 기초하여, 매칭 대상인, 그래프 스트림에 대한 후보 그룹을 선정하는 단계;상기 서브 그래프 매칭 장치의 캐시 관리자(Cache Manager)에서 상기 그래프 스트림과 연관되어 적재된 중간 결과를, 캐시로부터 추출하는 단계; 및상기 서브 그래프 매칭 장치의 질의 처리 관리자(Query Processing Manager)에서, 상기 후보 그룹과 상기 중간 결과에 대해 조인 연산하여 실체화 뷰(Materialized View)를 생성하고, 상기 실체화 뷰를 이용하여 서브 그래프 매칭을 수행하는 단계를 포함하는 슬라이딩 윈도우 기반 연속 서브 그래프 매칭 방법.

제1항에 있어서,상기 색인하는 단계는,상기 최대 포함 경로로 분할된 각 경로에 대해, 간선 정보와 질의 정보를 저장하는 엣지 인덱스(Edge-Index)로 색인하는 단계;상기 최대 포함 경로로 분할된 각 경로에 대해, 경로에 포함되는 간선을 트라이 노드에 저장하는 트라이 인덱스(Trie-Index)로 색인하는 단계; 및상기 최대 포함 경로로 분할된 각 경로의 마지막 위치에 대한 참조를 저장하는 레퍼런스 인덱스(Reference-Index)로 색인하는 단계를 포함하는 슬라이딩 윈도우 기반 연속 서브 그래프 매칭 방법.

제1항에 있어서,상기 캐시로부터 추출하는 단계는,상기 질의와 연관한 처리에서 활용되는 중간 결과를 관리하는 Used Cache와, 차기 질의와 연관한 처리 시 사용될 가능성이 있는 중간 결과를 관리하는 Prefetched Cache로부터, 상기 중간 결과를 추출하는 단계를 포함하는 슬라이딩 윈도우 기반 연속 서브 그래프 매칭 방법.

제1항에 있어서,질의 1에 포함되는 색인 정보에 의해 제1 노드가 후보 그룹으로서 선정되는 경우,상기 서브 그래프 매칭을 수행하는 단계는,상기 제1 노드의 자식 노드인 제2 노드가 Prefetched Cache에 적재 됨에 따라, 상기 조인 연산을 통해, 상기 제1 노드와 상기 제2 노드와의 관계를 실체화 뷰로서 생성하고, 상기 실체화 뷰를 Used Cache에 기록하여 상기 서브 그래프 매칭을 수행하는 단계를 포함하는 슬라이딩 윈도우 기반 연속 서브 그래프 매칭 방법.

제4항에 있어서,상기 질의 1에 이은 질의 2에 포함되는 색인 정보에 의해 제3 노드가 후보 그룹으로서 선정되는 경우,상기 서브 그래프 매칭을 수행하는 단계는,Used Cache로부터 상기 실체화 뷰가 추출 됨에 따라, 상기 조인 연산을 통해, 상기 제3 노드, 및 상기 제1 노드와 상기 제2 노드 간의 관계를 실체화 뷰로서 재생성하고, 상기 재생성된 실체화 뷰를 상기 Used Cache에 업데이트하여 상기 서브 그래프 매칭을 수행하는 단계를 포함하는 슬라이딩 윈도우 기반 연속 서브 그래프 매칭 방법.

제1항에 있어서,상기 서브 그래프 매칭 장치의 통계 관리자(Statistics Manager)에서, 상기 후보 그룹으로 선정된 노드에 관한 통계 정보를 작성하여 캐시에 기록하는 단계; 및상기 통계 관리자에서, 상기 통계 정보가 상기 캐시에 기록 됨에 따라, 상기 캐시에서 규정한 용량이 초과하는 경우, 통계 정보의 일부를 제거하여, 상기 캐시를 교체하는 단계를 더 포함하는 슬라이딩 윈도우 기반 연속 서브 그래프 매칭 방법.

제6항에 있어서,상기 캐시를 교체하는 단계는,상기 통계 정보 내 적중 횟수(H)를, 상주 시간(A)으로 나눈 값이 작은 통계 정보를 교체하는 POP(Popularity), 상기 POP에 조인 비율(J/H)을 곱한 값이 작은 통계 정보과를 교체하는 POU(Popularity and Usage), 상기 POU에 결과의 크기의 상대적 비율(Si/Smax)을 곱한 값이 작은 통계 정보를 교체하는 PUS(Popularity, Usage and Size), 및 상기 PUS에 질의 크기의 상대적 비율(QSi/QSmax)을 곱한 값이 작은 통계 정보를 교체하는 PUSQ(Popularity, Usage, Size and Query Size) 중, 적어도 하나를 이용하여, 제거할 통계 정보를 결정하는 단계를 포함하는 슬라이딩 윈도우 기반 연속 서브 그래프 매칭 방법.

입력되는 질의에 대해, 최대 포함 경로(Max covering Path)에 따라 경로 별 색인하고, 상기 경로 별 색인에 기초하여, 매칭 대상인, 그래프 스트림에 대한 후보 그룹을 선정하는 색인 관리자(Index Manager);상기 그래프 스트림과 연관되어 적재된 중간 결과를, 캐시로부터 추출하는 캐시 관리자(Cache Manager); 및상기 후보 그룹과 상기 중간 결과에 대해 조인 연산하여 실체화 뷰(Materialized View)를 생성하고, 상기 실체화 뷰를 이용하여 서브 그래프 매칭을 수행하는 질의 처리 관리자(Query Processing Manager)를 포함하는 슬라이딩 윈도우 기반 연속 서브 그래프 매칭 장치.

제8항에 있어서,상기 색인 관리자는,상기 최대 포함 경로로 분할된 각 경로에 대해, 간선 정보와 질의 정보를 저장하는 엣지 인덱스(Edge-Index)로 색인하고,상기 최대 포함 경로로 분할된 각 경로에 대해, 경로에 포함되는 간선을 트라이 노드에 저장하는 트라이 인덱스(Trie-Index)로 색인하며,상기 최대 포함 경로로 분할된 각 경로의 마지막 위치에 대한 참조를 저장하는 레퍼런스 인덱스(Reference-Index)로 색인하는슬라이딩 윈도우 기반 연속 서브 그래프 매칭 장치.

제8항에 있어서,상기 캐시 관리자는,상기 질의와 연관한 처리에서 활용되는 중간 결과를 관리하는 Used Cache와, 차기 질의와 연관한 처리 시 사용될 가능성이 있는 중간 결과를 관리하는 Prefetched Cache로부터, 상기 중간 결과를 추출하는슬라이딩 윈도우 기반 연속 서브 그래프 매칭 장치.

제8항에 있어서,질의 1에 포함되는 색인 정보에 의해 제1 노드가 후보 그룹으로서 선정되는 경우,상기 캐시 관리자는,상기 제1 노드의 자식 노드인 제2 노드를 Prefetched Cache에 적재하고,상기 질의 처리 관리자는,상기 조인 연산을 통해, 상기 제1 노드와 상기 제2 노드와의 관계를 실체화 뷰로서 생성하고, 상기 실체화 뷰를 Used Cache에 기록하여 상기 서브 그래프 매칭을 수행하는슬라이딩 윈도우 기반 연속 서브 그래프 매칭 장치.

제11항에 있어서,상기 질의 1에 이은 질의 2에 포함되는 색인 정보에 의해 제3 노드가 후보 그룹으로서 선정되는 경우,상기 캐시 관리자는,Used Cache로부터 상기 실체화 뷰를 추출하고,상기 질의 처리 관리자는,상기 조인 연산을 통해, 상기 제3 노드, 및 상기 제1 노드와 상기 제2 노드 간의 관계를 실체화 뷰로서 재생성하고, 상기 재생성된 실체화 뷰를 상기 Used Cache에 업데이트하여 상기 서브 그래프 매칭을 수행하는슬라이딩 윈도우 기반 연속 서브 그래프 매칭 장치.

제8항에 있어서,상기 후보 그룹으로 선정된 노드에 관한 통계 정보를 작성하여 캐시에 기록하고, 상기 통계 정보가 상기 캐시에 기록 됨에 따라, 상기 캐시에서 규정한 용량이 초과하는 경우, 통계 정보의 일부를 제거하여, 상기 캐시를 교체하는 통계 관리자(Statistics Manager)를 더 포함하는 슬라이딩 윈도우 기반 연속 서브 그래프 매칭 장치.

제13항에 있어서,상기 통계 관리자는,상기 통계 정보 내 적중 횟수(H)를, 상주 시간(A)으로 나눈 값이 작은 통계 정보를 교체하는 POP(Popularity), 상기 POP에 조인 비율(J/H)을 곱한 값이 작은 통계 정보과를 교체하는 POU(Popularity and Usage), 상기 POU에 결과의 크기의 상대적 비율(Si/Smax)을 곱한 값이 작은 통계 정보를 교체하는 PUS(Popularity, Usage and Size), 및 상기 PUS에 질의 크기의 상대적 비율(QSi/QSmax)을 곱한 값이 작은 통계 정보를 교체하는 PUSQ(Popularity, Usage, Size and Query Size) 중, 적어도 하나를 이용하여, 제거할 통계 정보를 결정하는슬라이딩 윈도우 기반 연속 서브 그래프 매칭 장치.

제1항 내지 제7항 중 어느 한 항의 방법을 실행시키기 위한 프로그램을 기록한 컴퓨터 판독 가능한 기록매체.