Parallel and Streaming Algorithms for K-Core Decomposition
The $k$-core decomposition is a fundamental primitive in many machine learning and data mining applications. We present the first distributed and the first streaming algorithms to compute and maintain an approximate $k$-core decomposition with provable guarantees. Our algorithms achieve rigorous bounds on space complexity while bounding the number of passes or number of rounds of computation. We do so by presenting a new powerful sketching technique for $k$-core decomposition, and then by showing it can be computed efficiently in both streaming and MapReduce models. Finally, we confirm the effectiveness of our sketching technique empirically on a number of publicly available graphs.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Streaming Coresets for Symmetric Tensor Factorization
Factorizing tensors has recently become an important optimization module in a number of machine learning pipelines, especially in latent variable models. We show how to do this efficiently in the streaming setting. Given…
Streaming data recovery via Bayesian tensor train decomposition
In this paper, we study a Bayesian tensor train (TT) decomposition method to recover streaming data by approximating the latent structure in high-order streaming data. Drawing on the streaming variational Bayes method, w…
Tensor DecompositionVariational InferenceProbabilistic Streaming Tensor Decomposition
Tensor decomposition is a fundamental tool for multiway data analysis. While most decomposition algorithms operate a collection of static data and perform batch processes, many applications produce data in a streaming ma…
Bayesian InferenceTensor DecompositionA Reconfigurable Streaming Deep Convolutional Neural Network Accelerator for Internet of Things
Convolutional neural network (CNN) offers significant accuracy in image detection. To implement image detection using CNN in the internet of things (IoT) devices, a streaming hardware accelerator is proposed. The propose…
Streaming Factor Trajectory Learning for Temporal Tensor Decomposition
Practical tensor data is often along with time information. Most existing temporal decomposition approaches estimate a set of fixed factors for the objects in each tensor mode, and hence cannot capture the temporal evolu…