关键词: 大规模动态图, 标签约束, 聚合划分, Top-K查询

Abstract:

As an important technology of graph search, Top-K subgraph query is widely used in some emerging fields such as social network, biological information networks and so on, because of its pointedly returning query  results to users. With the increasing of the scale and dynamic evolution of the graph, users often hope to obtain the query results quickly and accurately by adding constraints. In view of the above query requirement, this paper proposes a method called frequent subgraph Top-K query method under label value constrained (LVC-FS Top-K). This method establishes the two level index with the frequent structure mapping and label value aggregation (FSM-LVA), which will lock the query graph structure quickly and accurately, and prune and filter according to the constraint limit so that it can narrow the search range and improve the query efficiency. It uses FSM-LVA index to find isomorphic query structure, and combines with the constraint conditions and K to filter frequent subgraphs that can narrow the space and speed up the query efficiency. Experiments have proven that the method can quickly and accurately perform the frequent subgraph Top-K query with constraint limit on large-scale dynamic graphs.

Key words: large-scale dynamic graph, label constraint, aggregation partition, Top-K query