Article Preview
TopIntroduction
Since the concept of Big Data has been proposed by the paper Big data: How do your data grow? published in Sep 2008 at Nature (Lynch, 2008), Big data have become the focus of both academics and industry. Recently, the rising and popularity of new network applications, such as composite services, social networks, biological networks and internet of things, on the one hand, increase the velocity and scale of the data generation (Li et al., 2016); on the other hand, these lead to a dramatic promotion of the complexity of big data processing and analyzing. The intricate relationship between data makes the processing complexity of big data involving network structures and data connections (named big graph data) become exponential. In addition to the exponential increase of data scale, this leads to a double exponential increase of complexity of big graph data processing and analyzing. However, there is a significant leap between this situation and the current slow increase of big graph data storage and computation. Hence, it is a common basic problem for big graph data computation that how to effectively and efficiently process and analyze big graph data. Sophisticated analysis and intelligent understanding of big graph data have become an important bottleneck for big graph data cognition and value mining.
Big graph, particularly composite service or social network attracts more and more attention from scholars, where one of the most important research areas is graph pattern matching, especially with big graph data. With the help of graph pattern matching, we can design a pattern graph satisfying special personal requirements, and locate the subgraphs which match the required pattern, which can finish the required task with the matched subgraph, such as: social status detection (Cheng et al., 2008), expert finding (Cheng et al., 2013; Tong et al., 2007), travel planning (Tong et al., 2007), research group selection, and etc. Big graph data are different from traditional data with a simple relation, and they usually contain complex relationship. For example, in composite service, vertices represent services, such as selling a product online (i.e., the traditional online service), or a functional component implemented by using Web service technologies, edges represent the relation of services, and together they can function as a whole; in social networks, vertices represent participants, and edges represent social relations which can be friendship or working relationship in real, co-authorship of a paper, or superior-subordinate relationship etc. In addition, vertices or edges can have some attribute information, such as the vertex of a social contextual graph (Henzinger et al., 2002) can have the information about social roles, and its edge can have attribute information about social trust and social intimacy. Generally, this rich metadata information of big graph data enriches the description of the data in a wide range of contextual information, such as source, time, occurrence probability, and other related metadata about the data (Li et al., 2015), which is significant for the subsequent data processing. Taking big graph data related to medical issues as an example, due to difference of medical equipment and software, and personal experience of doctors and other reasons, the data collected by certain medical institutions may be taken as untrustworthiness by others. These data with different attributes can produce intricate correlations and then converge and form a big graph. Then, how to locate a graph pattern with certain attributes in the big graph effectively and efficiently becomes a key problem to analyze and deal with big graph data, especially for a specific domain (Pienta et al., 2014).
The major contribution of the paper can be summarized as follows: