关键词: 大规模动态标签图, 子图查询, 层次拓扑序列, 图索引

Abstract: Labeled graphs are often used for modeling in emerging fields such as smart transportation and bioinformatics. Subgraph query as the key problem of data analysis has attracted extensive attention of researchers. The research of existing subgraph query algorithms show that with the increasing size and frequent updating of graphs, traditional algorithms have many problems such as low query efficiency, large storage overhead and ignoring vertex label information. Therefore, a dynamic hierarchical sequence index for subgraph query on large scale dynamic labeled graph is proposed, which is named DHS. The index extracts the hierarchical topological sequence with the id of vertexes from the graph to realize subgraph query. With the changes of graph, an updating vertex topology extended index maintenance strategy is proposed, which can update from local changing vertices or edges incrementally, greatly reducing the huge overhead caused by the reconstruction index. And a subgraph query method which based on DHS index is proposed that only by matching the hierarchical sequences of query graph and data graph to obtain the candidate set, then the relational matching strategy is used to obtain final query results. Experimental results show that the proposed method improves the query efficiency and reduces the creation and maintenance cost of index.

Key words: large-scale dynamic labeled graph, subgraph query, topological hierarchical sequence, graph index