다중 스트림에서 효율적인 상관관계 그래프 마이닝 = Efficient Correlated Graph Mining from Multiple Streams

다국어 초록 (Multilingual Abstract)

Correlated patterns from graph streams can be utilized informative knowledges in various applications. Recently, various approaches for mining correlated graphs from single graph streams are proposed. However, these approaches require long running time in multiple stream environments because inefficient processes such as a large number of subgraph isomorphism tests must be iteratively performed for each graph stream. In this paper, we propose an efficient correlated graph mining approach from multiple streams. The proposed approach perform subgraph isomorphism by using the searching tree of frequent pattern mining which is performed by correlated pattern mining. Moreover, we also propose the tree merging technique for optimizing space usage. In experiment, we show that the proposed approach can reduce execution time by up to 10~20% compared with the existing single stream based correlated graph mining method.

국문 초록 (Abstract)

그래프 스트림에서 상관관계 패턴은 다양한 분야에서 유용한 지식으로 활용될 수 있다. 최근, 단일 그래프 스트림 환경에서 상관관계 패턴을 효율적으로 찾기 위한 다양한 기법들이 제안되었다. 그러나 기존의 기법들은 다중 그래프 스트림 환경에서는 매우 많은 수의 부분그래프 동형 검사와 같은 비효율적인 프로세스들을 각 스트림마다 반복적으로 수행해야 하므로 오랜 수행 시간을 요구한다. 본 논문에서는 다중 스트림 환경에서 효율적인 상관관계 그래프 마이닝 기법을 제안한다. 제안하는 기법은 각 스트림에서 수행한 빈발 부분그래프 마이닝의 탐색트리를 이용하여 효율적으로 부분그래프 동형 검사를 수행한다. 또한, 공간 사용량을 개선하기 위한 탐색트리 병합 기법도 제안한다. 실험을 통해 제안하는 기법이 기존의 단일 스트림 기반 기법보다 수행시간이 약 10~20%향상됨을 보인다.

참고문헌 (Reference)

1 Yan, Xifeng, "gspan: Graph-based substructure pattern mining" 2002

2 Lei Zou, "Top-K Correlation Sub-graph Search in Graph Databases" 5463 : 168-185, 2009

3 Reynolds, Henry T, "The analysis of cross-classifications" Free Press 1977

4 "PubChem"

5 G. Udny Yule, "On the Methods of Measuring Association Between Two Attributes" 75 (75): 579-652, 1912

6 M. Ersue, "Management of Networks with Constrained Devices: Use Cases" 2014

7 Danh Le-Phuoc, "Enabling Live Exploration on The Graph of Things" 2014

8 Huan Jun, "Efficient mining of frequent subgraphs in the presence of isomorphism" 2003

9 Yiping Ke, "Efficient Correlation Search from Graph Databases" 20 (20): 1601-1604, 2008

10 KE, Yiping, "Correlation search in graph databases" 2012

11 Kisung Park, "Correlated Subgraph Search for Multiple Query Graphs in Graph Streams" (49) : 2015

12 Shirui Pan, "CGStream: continuous correlated graph query for data streams" 2012

13 Alkar, A.Z, "An Internet based wireless home automation system for multifunctional devices" 51 (51): 1169-1174, 2005