Research On Key Techniques Of Query Processing And Mining Analysis Over Large Graph Data

Information system and information management is an important scientific field that takes information as the core resource and information technology as the core capability to solve practical economic and management problems at macro and micro levels,and has three important dimensions of “information,technology and management”.With the rapid development of information technology,the scale of data has grown rapidly,and complex interactive relationships between data have emerged increasingly.Mining the rich value of data and its associations can provide a lot of effective information for people’s daily life.Graph,as a general data structure in computer science,is a good way to describe the relationships among entities.Graphs have been widely used in many real applications,such as biological networks,social networks,and knowledge graphs,etc.Graph analysis can query and mine the hidden information in these associations,and thus is widely used in many service scenarios.Although researches have made great contributions on techniques of graph queries and graph mining,when graphs are applied in different applications,they evolves into many forms,such as dynamic graph,temporal graph,etc.As a result,the query and mining problems on the graph are more diversified.In order to deal with different requests in different environments,query and mining over graph data need to be modeled more reasonably.On the other hand,as graphs inherently have complex topologic information,the computational complexity of graph query or graph mining is usually very high,and more efficient algorithms need to be designed.Through analyzing real applications’ request,this thesis utilizes the knowledge of computational complexity theory and algorithmic technology,sets up more reasonable models,and proposes specific query and mining algorithms over large-scale graph data.The research results are of great value to the analysis of graph data,and also have implications for research work in related fields.The thesis carries out research in the following five main areas.(1)We study the problem of SPARQL query over dynamic knowledge graph.We model this problem as continuous subgraph pattern matching over dynamic graph and propose to construct a query-centric auxiliary data structure to record some intermediate query results,which can help to avoid re-computing matches of the query and speed up subsequent query answering process.Then,we propose an incremental maintenance strategy,to efficiently maintain the intermediate results when updates occur.We further propose an incremental subgraph matching to answer the query.Extensive experiments using benchmarks for streaming RDF engines show that our proposed algorithm outperforms its competitors.(2)We study the problem of dynamic SPARQL query over knowledge graph.We model this problem as continuous matching of evolving graph patterns over graph data and propose to revise the auxiliary data structure proposed in the first part to meet the requirement of dynamic SPARQL queries.We also propose an incremental maintenance strategy to efficiently maintain the intermediate results.What’s more,we define matchingfree queries,in which subgraph matching calculations can be replaced by a cheaper pruning strategy for some special shapes of BGP queries;for other queries,we conceive an effective cost model for estimating step-wise cost of pattern matching.Comprehensive empirical study verifies the efficiency of the proposed algorithm and techniques.(3)We study the problem of mining seasonal bursting subgraphs in a temporal network,which is essential to understanding groups of individuals who interact with each other in specific time instances.We propose a novel model,called maximal(ω,θ)-dense subgraph,that represents a seasonal bursting community in temporal networks,and model the mining problem as a mixed integer programming problem,which consists of finding the densest subgraph and finding the maximum burstiness segment.Then we give corresponding solutions for each subproblem,respectively.We further conceive two optimization strategies by exploiting key-core and dynamic programming algorithm to boost the performance.We also perform extensive evaluation on five real-life datasets to demonstrate the efficiency,scalability,and effectiveness of our algorithms.(4)We study the problem of mining top-k fastest frequency change pattern in a temporal network,which is a subgraph that accumulates its frequency at the fastest rate during a time interval.We first follow the explore-decide paradigm in existing frequent pattern mining work to design a baseline.Through analyzing its limitations,we devise a new bounding framework to achieve a tighter pruning bound in the mining process.Based on the new framework,we further explore two optimization strategies by exploiting incremental subgraph matching and Evolutionary Game Theory techniques to improve the performance.Comprehensive experiments demonstrate that our algorithm achieves both high effectiveness and efficiency.The experiments also show that our model is indeed able to identify many interesting patterns.(5)We study the problem of mining frequency burst pattern in a dynamic,which is a subgraph consists of a sudden increase and a sudden decrease in terms of arrival frequency.We first extend the traditional frequent pattern mining solution over dynamic to solve our problem and analysis its limitations.Then,we propose an auxiliary data structure for counting the frequency of a pattern without storing any sampled subgraph,which is fast,memory efficient,and accurate.We further design a new graph invariant that map each subgraph to its sequence space and explore an optimization strategies by using edge sampling to speed up the pattern mining process.Experimental results show that our algorithms can achieve high accuracy and efficiency with limited memory usage.