Research On Minimal Unique Induced Subgraph Queries In Graph Data Management

Graph is one of the most important data structure in computer science. Graph not only focuses on the attributes of the data object itself, but also pays attention to the interaction between data objects. Graph can be used to describe complex network structures, such as the Amazon commodity network, FACEBOOK social network, and biological protein networks, and so on. In recent years, graph has been widespread concerned and deeply studied, which has made a large number of research results. With the increasing amount of graph data, the core problem in graph research is how to effectively answer the various queries in graph databases.This paper presents a new graph query requirement. Given a query vertex, return a suitable subgraph which contains the vertices. The subgraph should not be too small to avoid that users can not distinguish differences between neighborhood of the query vertex and that of other vertices. And the subgraph should not be too large to avoid that users are confused with the returned information. In this demand, this paper presents a mininal unique induced subgraph(abbreviated as MUIS) query. MUIS query refers to find out a unique induced subgraph with a minimum number of vertices which contain the given query vertex. MUIS queries provide a new data access and using method for graph data management. MUIS queries can not only tap the special structure of the vertex neighborhood, but also can be used to visualization and explore the property of vertices.This article gives the formal definition of MUIS, explores the property of MUIS and gives MUIS coding methods. A filter-validation framework for solving the MUIS query problems is proposed in this paper. At the filtering stage, MUIS candidate set is produced by search and pruning in the induced subgraph space. At the validation stage, subgraph isomorphism is used to test whether the induced subgraph in MUIS candidate set is unique. This paper proposes a bread-first layered search strategy based on the query vertex to find out an unique induced subgraph with the minimum number of vertices as soon as possible. In a single graph, a pruning strategy based on matched vertices has been proposed to reduce the number of subgraph isomorphism test times. In a graph collection, a pruning strategy to utilize graph test order is also joined to further improve the efficiency in addition to the pruning strategy based on matched vertices. All the algorithms adopt an improved VF2 algorithm based on the query vertex for subgraph isomorphism testing. The improved VF2 algorithm not only optimizes the matching order of vertices, but also optimizes the data structure, thus improving the efficiency of the isomorphic test.At the experimental stage, the effectiveness of the basic algorithm and the improved algorithm for MUIS query in a single graph and graph collection is verified and their performance are compared. This paper presents two performance evaluation criteria, the average isomorphic time and the number of calling recursive function times. Both real data sets and simulated data sets are used. In a single graph, two real datasets YEAST and HPRD are adopted. In a graph collection, two real datasets AIDS and NASA are used. All the proposed algorithms can complete MUIS query tasks. The query efficiency of improved algorithms has been greatly improved, and the advantage of improved algorithms is more apparent when it takes longer time to complete query tasks. In addition, the experiments also explore the factors affecting MUIS query efficiency. Typically, with the increasing of the number of edges and graphs, the query efficiency decreases. With the increasing of the number of vertex and edge labels, the query efficiency increases.