Graph partitioning is crucial in distributed graph-parallel computing systems, and it is challenging for graph partitioning to optimize the communication cost and load balancing together. Existing state-of-the-art works, such as Powerlyra and TopoX, optimize the load balancing by randomly distributing the edges of high-degree vertices, which inevitably brings a high communication cost that is unbounded. This paper proposes a graph partition model that can minimize communication cost while maximizing load balancing. More specifically, we model the graph partition as the combinatorial design problem. Our proposed model can provide high-quality partition that guarantees that the computing load can be evenly distributed to each worker and minimizes the communication cost with a near-optimal theoretical boundary.Based on the proposed model, we extend the hybrid-cut partitioning algorithm for the power-law graph and propose HCPD, a hybrid-cut partitioning algorithm based on combinatorial design. HCPD uses the proposed model to optimize the load balancing and communication cost simultaneously for high-degree vertices, and assigns the high-degree vertices and their low-degree neighbors to the same workers by label propagation to reduce the overall communication cost. In this way, we partition the low-degree and high-degree vertices holistically and further improve the partition quality, unlike Powerlyra and TopoX, which deal with the two parts independently. Our experiments show that HCPD outperforms Powerlyra on PageRank task by up to 2× faster on real-world power-law graphs with billions of edges.

Graph partitioning is crucial in distributed graph computing systems, while impacting load balancing and communication between machines. To cope with the soaring scale of graphs, the streaming model has shown promising performance in graph partitioning. Although streaming model can deal with the bottleneck of memory usage for large-scale graphs, existing streaming partitioning algorithms not only lack sufficient quality but also cannot provide theoretical boundaries for graph partitioning. In addition, most streaming partitioning algorithms are sensitive to the order of edge streaming. In this paper, we model the edge partitioning problem as a combinatorial design problem, and provide a tight theoretical boundary. Based on the balanced edge partitioning design, we proposed a mixed-state streaming edge partitioning algorithm, which can generate high-quality graph partitions by mapping matrix and use the historical partition information to further optimize the partition quality and load balance. The experiments show that our proposed algorithm reduces partitioning time by more than half compared to the mainstream HDRF algorithm while maintaining load balance, and improves partitioning quality by about three times.

Finding frequent subgraph patterns in a big graph is an important problem with many applications such as classifying chemical compounds and building indexes to speed up graph queries. Since this problem is NP-hard, some recent parallel systems have been developed to accelerate the mining. However, they often have a huge memory cost, very long running time, suboptimal load balancing, and possibly inaccurate results. In this paper, we propose an efficient system called T-FSM for parallel mining of frequent subgraph patterns in a big graph. T-FSM adopts a novel task-based execution engine design to ensure high concurrency, bounded memory consumption, and effective load balancing. It also supports a new anti-monotonic frequentness measure called Fraction-Score, which is more accurate than the widely used MNI measure. Our experiments show that T-FSM is orders of magnitude faster than SOTA systems for frequent subgraph pattern mining. Our system code has been released at https://github.com/lyuheng/T-FSM.

Given a data matrix \( D \) , a submatrix \( S \) of \( D \) is an order-preserving submatrix (OPSM) if there is a permutation of the columns of \( S \) , under which the entry values of each row in \( S \) are strictly increasing. OPSM mining is widely used in real-life applications such as identifying coexpressed genes and finding customers with similar preference. However, noise is ubiquitous in real data matrices due to variable experimental conditions and measurement errors, which makes conventional OPSM mining algorithms inapplicable. No previous work on OPSM has ever considered uncertain value intervals using the well-established possible world semantics. We establish two different definitions of significant OPSMs based on thepossible world semantics: (1) expected support-based and (2) probabilistic frequentness-based. An optimized dynamic programming approach is proposed to compute the probability that a row supports a particular column permutation, with a closed-form formula derived to efficiently handle the special case of uniform value distribution and an accurate cubic spline approximation approach that works well with any uncertain value distributions. To efficiently check the probabilistic frequentness, several effective pruning rules are designed to efficiently prune insignificant OPSMs; two approximation techniques based on the Poisson and Gaussian distributions, respectively, are proposed for further speedup. These techniques are integrated into our two OPSM mining algorithms, based on prefix-projection and Apriori, respectively. We further parallelize our prefix-projection-based mining algorithm using PrefixFPM, a recently proposed framework for parallel frequent pattern mining, and we achieve a good speedup with the number of CPU cores. Extensive experiments on real microarray data demonstrate that the OPSMs found by our algorithms have a much higher quality than those found by existing approaches.

Frequent pattern mining (FPM) has been a focused theme in data mining research for decades, but there lacks a general programming framework that can be easily customized to mine different kinds of frequent patterns, and existing solutions to FPM over big transaction databases are IO-bound rendering CPU cores underutilized even though FPM is NP-hard. This paper presents, PrefixFPM, a general-purpose framework for FPM that is able to fully utilize the CPU cores in a multicore machine. PrefixFPM follows the idea of prefix projection to partition the workloads of PFM into independent tasks by divide and conquer. PrefixFPM exposes a unified programming interface to users who can customize it to mine their desired patterns, and the parallel execution engine is transparent to end-users and can be reused for mining all kinds of patterns. We have adapted the state-of-the-art serial algorithms for mining frequent patterns including subsequences, subtrees, and subgraphs on top of PrefixFPM, and extensive experiments demonstrate an excellent speedup ratio of PrefixFPM with the number of cores. A demo is available at https://youtu.be/PfioC0GDpsw; the code is available at https://github.com/yanlab19870714/PrefixFPM.

Window functions have been a part of the SQL standard since 2003 and have been studied extensively during the past decade. They are widely used in data analysis; almost all the current mainstream commercial databases support window functions. However, in recent years the size of datasets is growing steeply; the existing window function implementations are not efficient enough. Recently, some sampling-based algorithms (e.g., online aggregation) are proposed to deal with large and complex data in relational databases, which offer us a flexible trade-off between accuracy and efficiency. However, few sampling techniques has been considered for window functions in databases. In this paper, we extend our previous work (Song et al. in Asia-Pacific web and web-age information management joint conference on web and big data, Springer, pp 229–244, 2017 ) and proposed two new algorithms: range-based global sampling algorithm and row-labeled sampling algorithm. The proposed algorithms use global sampling rather than local sampling and are more efficient than other existing algorithms. And we find our proposed algorithms out performed the baseline method over the TPC-H benchmark dataset.