Constraint Top-k Query For Large-scale Dynamic Graph Based On Frequent Subgraph

As a means of effectively describing entities and their relationships of the real world,graph data are used in biomolecule network analysis,social network processing,intelligent traffic and cloud data processing.In recent years,due to the rapid development of information technology,the ever-increasing entities represented by graph result in the larger graph scale,and meanwhile,the varying relationships between these entities result in frequently updated graph data,so it is very important to study processing for large-scale dynamic graphs.The graph top-k query is a key research work in the field of graph data processing.The top-k queries for small and medium scale have been mature,however the existing algorithms mostly have difficulty dealing with the large-scale graph structure matching problem.And related researches for graph data top-k query involving the constraint are less.Therefore,this thesis presents constraint top-k query methods for large-scale dynamic graph based on frequent subgraph(frequent subgraph based constraint top-k query,FSCtop-k).The method deals with constraint semantic top-k graph data query,and firstly the frequent subgraph index and label aggregation index are built on the foundation of the initial data graph;secondly,query methods are given respectively for querying graph is frequent or not;finally,according to the characteristics of large-scale dynamic graph,update strategy for dynamic graph is given,which sovles the dynamic updating problem by means of analyzing common vertex,setting monitoring variables and reserving min and max indices.The method presents the constraint semantic top-k graph data query,greatly controls the range of subgraph candidates,and it has good feasibility and query efficiency.The main content of this thesis can be summarized as follows:(1)Presenting constraint semantics,presenting the concept of graph data constraint top-k query,and adding the constraint conditions on the foundation of ordinary graph data top-k queries;(2)Presenting frequent subgraph index and label aggregation index.Constructing the frequent subgraph index by means of traversing the data graph and mining frequent subgraph in initial data graph;constructing the label aggregation index by means of allocating index for vertices label,mapping the subgraph into the index and distributing flag-bit to subgraphs,also giving the segment density calculation method,therefore guaranteeing the efficiency of graph data constraints top-k query;(3)Giving query methods respectively for querying graph is frequent or not,finding the results of constraints top-k query in small subgraph candidates;(4)Giving update strategy of dynamic graph for the top-k query problems in large-scale dynamic graph.Firstly determining the update policy of updating regularly,secondly solving the structural change in the graph by analyzing common vertex and setting monitoring variables,finally solving index cross-border issues resulted from the vertices label change reserving min and max indices;(5)Experiments on simulated data sets and real data sets showing the efficiency and feasibility of this method dealing with the constraint top-k query for large-scale dynamic graphs.