Peilin Zhong
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Peilin Zhong has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Vahab Mirrokni
Google research
4 shared publications - Adel Javanmard
Department of Data Sciences and Operations University of Southern California
2 shared publications - Alessandro Epasto
Google research
2 shared publications - Andres Munoz Medina
Google, New York, NY, USA
2 shared publications - Hossein Esfandiari
Google Research, London, United Kingdom
2 shared publications - Josh Karlin
Google Chrome, Boston, MA, USA
2 shared publications
Latest Publications
- Open Access
- 3 August 2025
- Published by Association for Computing Machinery (ACM)
- p. 5379-5390
Differentially Private Synthetic Data Release for Topics API Outputs
- 3 August 2025
- Published by Association for Computing Machinery (ACM)
- p. 5379-5390
Open AccessDifferentially Private Synthetic Data Release for Topics API Outputs
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1911-1922
Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond
In the coordinator model of communication with s servers, given an arbitrary non-negative function f, we study the problem of approximating the sum ∑i ∈ [n]f(xi) up to a 1 ± ε factor. Here the vector x ∈ ℝn is defined to be x = x(1) + ⋯ + x(s), where x(j) ≥ 0 denotes the non-negative vector held by the j-th server. A special case of the problem is when f(x) = xk which corresponds to the well-studied problem of Fk moment estimation in the distributed communication model. We introduce a new parameter cf[s] which captures the communication complexity of approximating ∑i∈ [n] f(xi) and for a broad class of functions f which includes f(x) = xk for k ≥ 2 and other robust functions such as the Huber loss function, we give a two round protocol that uses total communication cf[s]/ε2 bits, up to polylogarithmic factors. For this broad class of functions, our result improves upon the communication bounds achieved by Kannan, Vempala, and Woodruff (COLT 2014) and Woodruff and Zhang (STOC 2012), obtaining the optimal communication up to polylogarithmic factors in the minimum number of rounds. We show that our protocol can also be used for approximating higher-order correlations. Our results are part of a broad framework for optimally sampling from a joint distribution in terms of the marginal distributions held on individual servers. Apart from the coordinator model, algorithms for other graph topologies in which each node is a server have been extensively studied. We argue that directly lifting protocols from the coordinator model to other graph topologies will require some nodes in the graph to send a lot of communication. Hence, a natural question is the type of problems that can be efficiently solved in general graph topologies. We address this question by giving communication efficient protocols in the so-called personalized CONGEST model for solving linear regression and low rank approximation by designing composable sketches. Our sketch construction may be of independent interest and can implement any importance sampling procedure that has a monotonicity property.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1911-1922
Open AccessOptimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond
In the coordinator model of communication with s servers, given an arbitrary non-negative function f, we study the problem of approximating the sum ∑i ∈ [n]f(xi) up to a 1 ± ε factor. Here the vector x ∈ ℝn is defined to be x = x(1) + ⋯ + x(s), where x(j) ≥ 0 denotes the non-negative vector held by the j-th server. A special case of the problem is when f(x) = xk which corresponds to the well-studied problem of Fk moment estimation in the distributed communication model. We introduce a new parameter cf[s] which captures the communication complexity of approximating ∑i∈ [n] f(xi) and for a broad class of functions f which includes f(x) = xk for k ≥ 2 and other robust functions such as the Huber loss function, we give a two round protocol that uses total communication cf[s]/ε2 bits, up to polylogarithmic factors. For this broad class of functions, our result improves upon the communication bounds achieved by Kannan, Vempala, and Woodruff (COLT 2014) and Woodruff and Zhang (STOC 2012), obtaining the optimal communication up to polylogarithmic factors in the minimum number of rounds. We show that our protocol can also be used for approximating higher-order correlations. Our results are part of a broad framework for optimally sampling from a joint distribution in terms of the marginal distributions held on individual servers. Apart from the coordinator model, algorithms for other graph topologies in which each node is a server have been extensively studied. We argue that directly lifting protocols from the coordinator model to other graph topologies will require some nodes in the graph to send a lot of communication. Hence, a natural question is the type of problems that can be efficiently solved in general graph topologies. We address this question by giving communication efficient protocols in the so-called personalized CONGEST model for solving linear regression and low rank approximation by designing composable sketches. Our sketch construction may be of independent interest and can implement any importance sampling procedure that has a monotonicity property.
- Open Access
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 77-88
Massively Parallel Tree Embeddings for High Dimensional Spaces
Efficient computation on massive high-dimensional data greatly benefits from efficient embedding techniques into simpler metrics. Perhaps the most celebrated technique is the dimension reduction a-la Johnson and Lindenstrauss [46]. Another important method embeds the data into a tree metric space, first efficiently achieved by Bartal [15]. Both of these algorithmic tools are among the most general theorems with numerous applications. In this paper, we study these two embedding methods in the Massively Parallel Computation (MPC) model. We develop a new hybrid partitioning algorithm which generalizes both random shifted grid and ball partitioning methods for generating tree embeddings. This leads to an O(1)-round randomized MPC algorithm for embedding high-dimensional data into a tree while approximating the distance between any two points within a factor of O(log(1.5)n) (and thus distortion O(log(1.5)n)) in expectation as long as the aspect ratio is O(poly(n)). This Euclidean result beats the lower bound of Ω(log n) MPC rounds for tree embeddings of general metric spaces and can extend to a number of problems, including densest ball, minimum spanning tree, and Earth-Mover distance. Along the way, we implement and use Ailon and Chazelle's Fast Johnson Lindenstrauss Transform [2] with sublinear memory and O(1) MPC rounds, which is of its own interest.
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 77-88
Open AccessMassively Parallel Tree Embeddings for High Dimensional Spaces
Efficient computation on massive high-dimensional data greatly benefits from efficient embedding techniques into simpler metrics. Perhaps the most celebrated technique is the dimension reduction a-la Johnson and Lindenstrauss [46]. Another important method embeds the data into a tree metric space, first efficiently achieved by Bartal [15]. Both of these algorithmic tools are among the most general theorems with numerous applications. In this paper, we study these two embedding methods in the Massively Parallel Computation (MPC) model. We develop a new hybrid partitioning algorithm which generalizes both random shifted grid and ball partitioning methods for generating tree embeddings. This leads to an O(1)-round randomized MPC algorithm for embedding high-dimensional data into a tree while approximating the distance between any two points within a factor of O(log(1.5)n) (and thus distortion O(log(1.5)n)) in expectation as long as the aspect ratio is O(poly(n)). This Euclidean result beats the lower bound of Ω(log n) MPC rounds for tree embeddings of general metric spaces and can extend to a number of problems, including densest ball, minimum spanning tree, and Earth-Mover distance. Along the way, we implement and use Ailon and Chazelle's Fast Johnson Lindenstrauss Transform [2] with sublinear memory and O(1) MPC rounds, which is of its own interest.
- Open Access
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 311-314
Brief Announcement: Streaming Balanced Clustering
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 learning. Many of these applications deal with large datasets, and hence researchers focused on designing algorithms for these problems in large scale settings such as the streaming setting. One of the sweet versions of clustering problems is balanced clustering (or more generally capacitated clustering), where we do not desire to have some giant and several small clusters. Despite the importance of the context, the best known streaming algorithm for capacitated clustering is far from optimal. The state-of-the-art streaming algorithm for capacitated clustering gives an O(1)-approximate solution, requires three passes and only handles insertions (Bateni et al. NeurIPS'14). We develop the first single pass streaming algorithm for the capacitated clustering problems that includes capacitated k-median and capacitated k-means in Euclidean space, using only poly(k dε-1 log Δ) space, where k is the number of clusters, d is the dimension and Δ is the maximum relative range of a coordinate. Our algorithm gives (1 + ε)-approximation and only violates the capacity constraint by a (1 + ε) factor. Interestingly, unlike the previous algorithm, our algorithm handles both insertions and deletions of points. To provide this result we introduce a decomposition of the space via some curved half-spaces which might be of independent interest.
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 311-314
Open AccessBrief Announcement: Streaming Balanced Clustering
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 learning. Many of these applications deal with large datasets, and hence researchers focused on designing algorithms for these problems in large scale settings such as the streaming setting. One of the sweet versions of clustering problems is balanced clustering (or more generally capacitated clustering), where we do not desire to have some giant and several small clusters. Despite the importance of the context, the best known streaming algorithm for capacitated clustering is far from optimal. The state-of-the-art streaming algorithm for capacitated clustering gives an O(1)-approximate solution, requires three passes and only handles insertions (Bateni et al. NeurIPS'14). We develop the first single pass streaming algorithm for the capacitated clustering problems that includes capacitated k-median and capacitated k-means in Euclidean space, using only poly(k dε-1 log Δ) space, where k is the number of clusters, d is the dimension and Δ is the maximum relative range of a coordinate. Our algorithm gives (1 + ε)-approximation and only violates the capacity constraint by a (1 + ε) factor. Interestingly, unlike the previous algorithm, our algorithm handles both insertions and deletions of points. To provide this result we introduce a decomposition of the space via some curved half-spaces which might be of independent interest.
- Open Access
- 13 June 2023
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 1 (2) , 1-26
Measuring Re-identification Risk
Compact user representations (such as embeddings) form the backbone of personalization services. In this work, we present a new theoretical framework to measure re-identification risk in such user representations. Our framework, based on hypothesis testing, formally bounds the probability that an attacker may be able to obtain the identity of a user from their representation. As an application, we show how our framework is general enough to model important real-world applications such as the Chrome's Topics API for interest-based advertising. We complement our theoretical bounds by showing provably good attack algorithms for re-identification that we use to estimate the re-identification risk in the Topics API. We believe this work provides a rigorous and interpretable notion of re-identification risk and a framework to measure it that can be used to inform real-world applications.
- 13 June 2023
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 1 (2) , 1-26
Open AccessMeasuring Re-identification Risk
Compact user representations (such as embeddings) form the backbone of personalization services. In this work, we present a new theoretical framework to measure re-identification risk in such user representations. Our framework, based on hypothesis testing, formally bounds the probability that an attacker may be able to obtain the identity of a user from their representation. As an application, we show how our framework is general enough to model important real-world applications such as the Chrome's Topics API for interest-based advertising. We complement our theoretical bounds by showing provably good attack algorithms for re-identification that we use to estimate the re-identification risk in the Topics API. We believe this work provides a rigorous and interpretable notion of re-identification risk and a framework to measure it that can be used to inform real-world applications.