Search

The existing literatures of the query processing on knowledge graphs focus on an exhaustive enumeration of all matches, which is time-consuming. Users are often interested in diversified top-k matches, rather than the entire match set. Motivated by these, this paper formalizes the diversified top-k querying (DTQ) problem in the context of RDF/SPARQL and proposes a diversification function to balance importance and diversity. We first prove that the decision problem of DTQ is NP-complete, and give a baseline algorithm with an approximation ratio of 2. Secondly, an index-based algorithm with the early termination property is proposed. The index is adept in parallel diversified top-k selection in multicore architectures. Using real-world and synthetic data, we experimentally verify that our algorithms are efficient and effective in computing meaningful diversified top-k matches.

Structural holes in social networks are vertices that serve as gateways for information exchange between communities. Although many algorithms have been proposed to detect structural holes, they are not scalable to big graphs. This paper proposes a structural hole detection algorithm ESH based on distributed parallel graph processing frameworks. Instead of using substructures in social networks, the algorithm exploits a factor diffusion process in structural hole detection. The algorithm naturally fits the vertex-centric programming models and can be easily implemented on the graph-parallel processing frameworks. Extensive experiments show that ESH can handle social networks with billions of links and produce structural holes of higher quality than the existing algorithms.

Making massive graph data easily understandable by people is a demanding task in a variety of real applications. Graph compression is an effective approach to reducing the size of graph data as well as its complexity in structures. This paper proposes a simple yet effective graph compression method called the star-based graph compression. This method compresses a graph by shrinking a collection of disjoint subgraphs called stars. Compressing a graph into the optimal star-based compressed graph with the highest compression ratio is shown to be NP-complete. We propose a greedy compression algorithm called StarZip. We experimentally verify that StarZip achieves compression ratios of 3.8–45.7 and 2.9–241.6 in terms of vertex count and edge count, respectively. Besides, we study the shortest path queries on compressed graphs. On the real graphs, the StarSSSP algorithm for processing shortest path queries on compressed graphs is 4X–20X faster than Dijkstra’s algorithm running on original graphs. The average absolute error between the query results of StarSSSP and the exact shortest distances is about 1. On the synthetic graphs, StarSSSP is up to 313X faster than Dijkstra’s algorithm, and the average absolute error is also about 1.

As similar queries keep springing up in real query logs, few RDF systems address this problem. In this paper, we propose Leon, a distributed RDF system, which can also deal with multi-query problem. First, we apply a characteristic-set-based partitioning scheme. This scheme (i) supports the fully parallel processing of join within characteristic sets; (ii) minimizes data communication by applying direct transmission of intermediate results instead of broadcasting. Then, Leon revisits the classical problem of multi-query optimization in the context of RDF/SPARQL. In light of the NP-hardness of the multi-query optimization for SPARQL, we propose a heuristic algorithm that partitions the input batch of queries into groups, and discover the common sub-query of multiple SPARQL queries. Our MQO algorithm incorporates with a subtle cost model to generate execution plans.

The emerging non-volatile memory (NVM) technologies have attracted much attention due to its advantages over the existing DRAM technology such as non-volatility, byte-addressability and high storage density. These promising features make NVM a promising replacement of DRAM. Although the reading cost of NVM is close to that of DRAM, the writing cost is significantly higher than that of DRAM. Existing algorithms designed on DRAM treat read and write equally and thus are not applicable to NVM. In this paper, we investigate efficient algorithms for subgraph matching, a fundamental problem in graph databases, on NVM. We first give a detailed evaluation on several existing subgraph matching algorithms by experiments and theoretical analysis. Then, we propose our write-limited subgraph matching algorithm based on the analysis. We also extend our algorithm to answer subgraph matching on dynamic graphs. Experiments on an NVM simulator demonstrate a significant improvement in efficiency against the existing algorithms.

In recent years, lots of data in various domain can be represented and described by uncertain graph model, such as protein interaction networks, social networks, wireless sensor networks, etc. This paper investigates the most reliable minimum spanning tree problem, which aims to find the minimum spanning tree MST with largest probability among all possible MSTs on uncertain graphs. In fact, the most reliable MST is an optimal choice between stability and cost. Therefore it has wide applications in practice, for example, it can serve as the basic constructs in a telecommunication network, the link of which can be unreliable and may fail with certain probability. A brute-force method needs to enumerate all possible MSTs and the time consumption grows exponentially with edge size. Hence we put forward an approximate algorithm in $$Od^{2}|V|^{2}$$Od2|V|2, where d is the largest vertex degree and |V| is vertex size. We point out that the algorithm can achieve exact solution with expected probability at least $$1-\frac{1}{2}^{d+1/2}^{|V|-1}$$1-12d+1/2|V|-1 and the expected approximation ratio is at least $$\frac{1}{2}^{d|V|}$$12d|V| when edge probability is uniformly distributed. Our extensive experimental results show that our proposed algorithm is both efficient and effective.

Heterogeneous information networks contain heterogeneous types of nodes and edges, e.g., social networks and knowledge graphs. A meta-path is a path connecting nodes through a sequence of heterogeneous edges, representing different kinds of semantic relations among nodes. Meta-paths are good mechanisms to improve the quality of graph analysis on heterogeneous information networks. This paper presents an iceberg cube framework for heterogeneous information networks based on meta-paths. To the best of our knowledge, there is no such proposal in the past. 1 We use meta-paths to measure the similarities of nodes, and prove the problem is NP-hard. 2 An optimal solution is proposed for the strict case. We develop the variant of slice tree to aggregate networks hierarchically. 3 To improve the scalability, a general approximate algorithm is provided for fast aggregation, where random walk on meta-paths is employed to measure the similarities. 4 Two pruning strategies are designed for reducing search space when the aggregate function is monotonic. 5 Experiments on both real-world and synthetic networks demonstrate the effectiveness and efficiency of the algorithms.

Uncertain graph data has been collected, processed and analyzed in a wide range of applications. Under the possible world model, an uncertain graph represents a probability distribution over all its possible worlds. Each possible world is a deterministic graph in which the uncertain graph may be present in practice. To deal with the hardness of computations on uncertain graphs, Parchas et al. first proposed the concept of a degree-based representative possible world. This approach is distinguished from the sampling approach in that it computes on one representative possible world instead of on a large number of possible worlds sampled at random. However, the degree-based representative possible world only tries to preserve vertex degrees. In this paper, we are motivated by the fact that motif structures such as triangles can affect the structural properties of graphs and propose the concept of a triangle-based representative possible world. We also develop an algorithm for finding the triangle-based representative possible world of an uncertain graph. We conducted extensive experimental evaluations and show that the triangle-based representative possible world outperforms the degree-based representative possible world in preserving the structural characteristics of an uncertain graph in expectation.

In this paper, we propose bitruss, a new notion of a dense subgraph of a bipartite graph. Specifically, the k-bitruss of a bipartite graph is the largest edge-induced subgraph H such that every edge of H is contained in at least k rectangles within H. The bitruss decomposition of a bipartite graph is the set of all nonempty k-bitrusses of the bipartite graph for $$k \ge 0$$ki¾ź0. In this paper, we show that the bitruss decomposition of a bipartite graph have three important properties. First, the bitruss decomposition is unique. Second, the bitruss decomposition is hierarchical, that is, the $$k + 1$$k+1-bitruss is a subgraph of the k-bitruss for all $$k \ge 0$$ki¾ź0. Third, the bitruss decomposition can be computed in polynomial time. These three interesting properties make bitruss a promising notion of dense bipartite subgraphs.

With the advent of heterogeneous information networks that consist of multi-type, interconnected nodes, such as bibliographic networks and knowledge graphs, it is important to study flexible aggregation in such networks. In this paper, we investigate the flexible aggregation problem on heterogeneous information networks, which is defined on multi-type of nodes and relations. We develop an efficient heuristic algorithm for aggregation in two phases: informational aggregation and structural aggregation. Extensive experiments on real world data sets demonstrate the effectiveness and efficiency of the proposed algorithm.

In the era of the Big Data, how to analyze such a vast quantity of data is a challenging problem, and conducting a multi-way theta-join query is one of the most time consuming operations. MapReduce has been mentioned most in the massive data processing area and some join algorithms based on it have been raised in recent years. However, MapReduce paradigm itself may not be suitable to some scenarios and multi-way theta-join seems to be one of them. Many multi- way theta-join algorithms on traditional parallel database have been raised for many years, but no algorithm has been mentioned on the CMD (coordinate modulo distribution) storage method, although some algorithms on equal-join have been proposed. In this paper, we proposed a multi-way theta-join method based on CMD, which takes the advantage of the CMD storage method. Experiments suggest that it’s a valid and efficient method which achieves significant improvement compared to those applied on the MapReduce.