38 citations · 152 across the 25 of their papers we have counts for
20 papers · 1 filter
Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
Arpit Agarwal, Sanjeev Khanna, Huan Li +4
We present a parallel algorithm for the -approximate maximum flow problem in capacitated, undirected graphs with vertices and edges, achieving $O(ε^{-3}\text{polylog…
Near-Optimal -Clustering in the Sliding Window Model
David P. Woodruff, Peilin Zhong, Samson Zhou
Clustering is an important technique for identifying structural information in large-scale data analysis, where the underlying dataset may be too large to store. In many applicatio…
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree
Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan +1
We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set of points, the goal i…
Differentially Private Clustering in Data Streams
Alessandro Epasto, Tamalika Mukherjee, Peilin Zhong
Clustering problems (such as -means and -median) are fundamental unsupervised machine learning primitives, and streaming clustering algorithms have been extensively studied i…
Differentially Private Continual Releases of Streaming Frequency Moment Estimations
Alessandro Epasto, Jieming Mao, Andres Munoz Medina +3
The streaming model of computation is a popular approach for working with large-scale data. In this setting, there is a stream of items and the goal is to compute the desired quant…
Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni +1
Streaming computation plays an important role in large-scale data analysis. The sliding window model is a model of streaming computation which also captures the recency of the data…
Massively Parallel and Dynamic Algorithms for Minimum Size Clustering
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni +1
In this paper, we study the -gather problem, a natural formulation of minimum-size clustering in metric spaces. The goal of -gather is to partition points into clusters s…
Average Case Column Subset Selection for Entrywise -Norm Loss
Zhao Song, David P. Woodruff, Peilin Zhong
We study the column subset selection problem with respect to the entrywise -norm loss. It is known that in the worst case, to obtain a good rank- approximation to a matr…
Connected Components on a PRAM in Log Diameter Time
S. Cliff Liu, Robert E. Tarjan, Peilin Zhong
We present an -time randomized PRAM algorithm for computing the connected components of an -vertex, -edge undirected graph with maximum componen…
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
Alexandr Andoni, Clifford Stein, Peilin Zhong
We present a -approximate parallel algorithm for computing shortest paths in undirected graphs, achieving depth and $m\mathrm{poly}(\log n)…
Efficient Symmetric Norm Regression via Linear Sketching
Zhao Song, Ruosong Wang, Lin F. Yang +2
We provide efficient algorithms for overconstrained linear regression problems with size when the loss function is a symmetric norm (a norm invariant under sign-flips…
Streaming Balanced Clustering
Hossein Esfandiari, Vahab Mirrokni, Peilin Zhong
Clustering of data points in metric space is among the most fundamental problems in computer science with plenty of applications in data mining, information retrieval and machine l…
Log Diameter Rounds Algorithms for -Vertex and -Edge Connectivity
Alexandr Andoni, Clifford Stein, Peilin Zhong
Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarse-grained computation on large data --- da…
Towards a Zero-One Law for Column Subset Selection
Zhao Song, David P. Woodruff, Peilin Zhong
There are a number of approximation algorithms for NP-hard versions of low rank approximation, such as finding a rank- matrix minimizing the sum of absolute values of differ…
Subspace Embedding and Linear Regression with Orlicz Norm
Alexandr Andoni, Chengyu Lin, Ying Sheng +2
We consider a generalization of the classic linear regression problem to the case when the loss is an Orlicz norm. An Orlicz norm is parameterized by a non-negative convex function…
Parallel Graph Connectivity in Log Diameter Rounds
Alexandr Andoni, Clifford Stein, Zhao Song +2
We study graph connectivity problem in MPC model. On an undirected graph with nodes and edges, round connectivity algorithms have been known for over 35 years.…
Nearly Optimal Dynamic -Means Clustering for High-Dimensional Data
Wei Hu, Zhao Song, Lin F. Yang +1
We consider the -means clustering problem in the dynamic streaming setting, where points from a discrete Euclidean space can be dynamically inserted to o…
Relative Error Tensor Low Rank Approximation
Zhao Song, David P. Woodruff, Peilin Zhong
We consider relative error low rank approximation of with respect to the Frobenius norm: given an order- tensor , output a rank-$…
Low Rank Approximation with Entrywise -Norm Error
Zhao Song, David P. Woodruff, Peilin Zhong
We study the -low rank approximation problem, where for a given matrix and approximation factor , the goal is to output a rank- matrix $\wideha…
Optimal Principal Component Analysis in Distributed and Streaming Models
Christos Boutsidis, David P. Woodruff, Peilin Zhong
We study the Principal Component Analysis (PCA) problem in the distributed and streaming models of computation. Given a matrix a rank parameter $k < rank(A)…