Search

Large-scale graphs are widely used to model the entities and their complex relations. Uncertain graphs are adopted when the relations between entities contain some uncertainty. However, the inherent uncertainties, which are embedded underlying the data and structure of the graphs derived from various sources introduce difficulties on data analysis. To understand the underlying characteristics of large graphs, graph aggregation techniques are critical. However, the existing graph aggregation techniques are designed for deterministic graphs therefore are not applicable on uncertain graphs. In this paper, we provide the first attempt on addressing the aggregation problem on uncertain graphs. To deal with the computation complexity of the aggregation problem, we propose a heuristic-based aggregation algorithm for uncertain graphs and some optimization methods to improve its efficiency in real world implementation. Besides the optimization, to further speed up the process, we design a parallel aggregation implementation approach. The intensive evaluations on the two datasets, DBLP and Flickr, demonstrate that our proposed algorithms are able to produce high quality aggregation results within reasonable operation time and the parallel implementation accelerates the aggregation by up to 82 times compared with the baseline algorithm.

Temporal graphs are graphs whose edges are associated with timestamps. Subgraph matching on temporal graphs retrieves temporal subgraphs whose edge timestamps satisfy user-specified temporal orders. In this paper, a temporal query pattern is composed of a query graph with an arbitrary structure and a partial order on the edge set of the query graph. Moreover, the time span between the minimum and the maximum edge timestamps in a matching is required to be less than or equal to a specified threshold. This paper proposes a temporal subgraph matching algorithm based on two key techniques. First, a memory-efficient index structure called TO-tree is designed to compactly store all necessary information required for finding all temporal subgraph matchings. The TO-tree constructed for a temporal query pattern is much smaller than the temporal graph because unnecessary information is mostly excluded from the TO-tree by three powerful filters. The second technique is a temporal subgraph matching enumeration method that runs on the TO-tree instead of on the temporal graph. This enumeration method expands temporal subgraph matchings in an edge-by-edge manner. Since the TO-tree can fit into the main memory, the enumeration method runs very fast on the TO-tree. An extensive experimental evaluation has been carried out. The experimental results show that the TO-tree index structure is memory-efficient, which in turn enables a fast temporal subgraph matching enumeration. Overall, our algorithm is at least 3X faster than the baseline algorithm adapted from the state-of-the-art non-temporal subgraph matching algorithm CECI and is at least 4X faster than the temporal subgraph matching algorithm HASSE .

Masses of large-scale knowledge graphs on various domains have sprung up in recent years. They are no longer able to be managed on a single machine. The distributed RDF systems intervene in the scalability issue using partitioning techniques. However, most of these systems are unaware of query workload and employ static partitioning. As diverse and dynamic workloads keep emerging in the knowledge graph applications, they cannot consistently provide good performance. To address the problem, we propose a workload-aware partitioning framework WISE, which could be deployed on any initial partitioning. It encodes the incoming SPARQL queries in a novel structure called query span and periodically examines the query span to identify the frequent query patterns. The triples of a frequent query pattern are moved to the same partition, aiming at improving the response time in the future. Our experiments on various RDF datasets and workloads indicate that WISE achieves dramatic communication reduction and considerable performance improvement over the baseline method. The migration overhead only accounts for a small portion of the total runtime.