Computing the maximum independent set (MIS) in a graph is a fundamental NP-hard problem, which is widely adopted in many real-world applications. Extensive works have been done on computing an approximate MIS. While the highly dynamic property of real-world graphs calls for efficient MIS maintenance solutions, existing works for dynamic MIS computation in the literature mainly focus on the single-machine scenario. The assumption that a single machine can access the whole graph makes them difficult to be straightforwardly applied for large-scale graphs in distributed environment. Motivated by this, in this paper, we study the problem of maintaining approximate MIS over large-scale dynamic graphs in distributed environments. We propose a new vertex centric algorithm OIMIS. Compared with existing solutions, OIMIS avoids the strong order dependency in distributed computation, which makes it easy to handle dynamic graph updates. OIMIS computes and maintains MIS with high effectiveness and efficiency. In terms of high effectiveness, OIMIS maintains consistent MIS results with the state-of-the-art distributed algorithm to compute MIS in static graphs. In terms of high efficiency, each vertex in OIMIS only updates MIS status according to its neighbor attributes. Novel optimization techniques are also designed to reduce communication and computation cost. We conduct extensive experiments to prove the effectiveness and efficiency of our distributed algorithms.

Designing distributed graph systems has drawn a lot of research interests due to the strong expressiveness of the graph model and rapidly increasing graph volume. Most of them require the graph data and all intermediate messages to reside in main memory, which may sacrifice the scalability. Even though several disk-based systems have been studied to remedy such issue, several challenges still exist in achieving both high computational efficiency and low network communication under the limitation of memory usage. In this paper, we design a novel disk-based distributed graph system, called ScaleG. The system provides a series of user-friendly programming interfaces. Unlike previous systems, the programmer in ScaleG does not need to concern any logic regarding the communication between vertices like sending messages and combining messages. In addition to a simple and clear programming model, we propose several techniques to reduce both disk I/Os in each machine and message I/Os via the network. We manage all messages in memory and bound all messages by the number of vertices. We also carefully design the data structure to support partial computation and automatic vertex activation. We conduct extensive experiments on six big graphs to show the high efficiency of our system.

Designing disk-based distributed graph systems has drawn a lot of research due to the strong expressiveness of the graph model and rapidly increasing graph volume. However, several challenges still exist in achieving both high computational efficiency and low network communication under the limitation of memory. In this paper, we design a novel distributed disk-based graph processing system, ScaleG, with a series of user-friendly programming interfaces. We propose several techniques to reduce both disk I/Os in each machine and message I/Os via the network. We manage all messages in memory and bound the volume of all messages by the number of vertices. We also carefully design the data structure to support partial computation and automatic vertex activation. We conduct extensive experiments on real-world big graphs to show the high efficiency of our system.

Depth-first search (DFS) is a fundamental and important algorithm in graph analysis. It is the basis of many graph algorithms such as computing strongly connected components, testing planarity, and detecting biconnected components. The result of a DFS is normally shown as a DFS-Tree. Given the frequent updates in many real-world graphs (e.g., social networks and communication networks), we study the problem of DFS-Tree maintenance in dynamic directed graphs. In the literature, most works focus on the DFS-Tree maintenance problem in undirected graphs and directed acyclic graphs. However, their methods cannot easily be applied in the case of general directed graphs. Motivated by this, we propose a framework and corresponding algorithms for both edge insertion and deletion in general directed graphs. We further give several optimizations to speed up the algorithms. We conduct extensive experiments on 12 real-world datasets to show the efficiency of our proposed algorithms.

Exact set similarity join, which finds all the similar set pairs from two collections of sets, is a fundamental problem with a wide range of applications. The existing solutions for set similarity join follow a filtering-verification framework, which generates a list of candidate pairs through scanning indexes in the filtering phase, and reports those similar pairs in the verification phase. Though much research has been conducted on this problem, set relations, which we find out is quite effective on improving the algorithm efficiency through computational cost sharing, have never been studied. Therefore, in this paper, instead of considering each set individually, we explore the set relations in different levels to reduce the overall computational costs. First, it has been shown that most of the computational time is spent on the filtering phase, which can be quadratic to the number of sets in the worst case for the existing solutions. Thus we explore index-level set relations to reduce the filtering cost to be linear to the size of the input while keeping the same filtering power. We achieve this by grouping related sets into blocks in the index and skipping useless index probes in joins. Second, we explore answer-level set relations to further improve the algorithm based on the intuition that if two sets are similar, their answers may have a large overlap. We derive an algorithm which incrementally generates the answer of one set from an already computed answer of another similar set rather than compute the answer from scratch to reduce the computational cost. Finally, we conduct extensive performance studies using 21 real datasets with various data properties from a wide range of domains. The experimental results demonstrate that our algorithm outperforms all the existing algorithms across all datasets and can achieve more than an order of magnitude speedup against the state- of-the-art algorithms.