图数据流上时间尊重图模式匹配算法研究

Time-respecting graph pattern matching on streaming graph

现有的动态子图匹配研究中忽略了模式图中的时间信息,使用户难以得到想要查询的真实结果。针对这种情况,首先设计一种简洁的中间结果保存形式,将匹配结果直接在数据图中以图进行存储;接着改进边缘转换模型,当数据图有边插入/删除时对其快速增量维护并报告结果;最后根据边转换模型设计了一个时间尊重图模式匹配算法,提高了匹配搜索效率。对真实网络流量数据和综合社交流数据进行实验评估,结果表明算法能够有效减少图模式匹配的执行时间和空间花销。

Existing research on dynamic subgraph matching ignores the time information in the pattern graph,which makes it difficult for users to obtain the real results they want to query.In response to this situation,this paper designed a simple intermediate result storage format,and stored the matching results directly in the data graph as a graph.Then it improved the edge transition model,quickly and incrementally maintained intermediate result when the data graph had edges inserted/deleted and reported the results.Finally,it designed a time-respecting graph pattern matching algorithm by the edge transition model,which improved the efficiency of matching search.Experimental evaluation on real network traffic data and comprehensive social flow data show that the algorithm can effectively reduce the execution time and space cost of graph pattern matching.