关键词: 查询优化算法, 时序图, 动态子图, 索引优化

Abstract: Finding specific patterns in the time-evolving graph can help people effectively get hidden information in the data, so the dynamic subgraph query and index optimization have become a hotspot in the research of the evolving graph. This paper selects dynamic subgraph query as a research point, and discusses index optimization emphatically. This paper firstly gives the definition of the query model and the basic query algorithm. Then, this paper provides two different indexing methods, waveform index and binary tree index. To test the applicability of the index, this paper designs the corresponding experiments and uses randomly generated datasets to test experiments, while analyzing the efficiency from time consumption and space utilization. The experiments show that waveform index has the advantage of simple storage structure, which is suitable for the situation of long edge length but small edge number. Binary tree index has good performance in query speed, which is suitable for the situation of short edge length and large edge number.

Key words: querying optimization algorithm, time-evolving graph, dynamic subgraph, index optimization