Peilin Zhong

Peilin Zhong

Auto-generated profile, based on publicly available information

Peilin Zhong

Google Research, New York, NY, USA

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
13 June 2023 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
CCCj Carey
Cj Carey
TDTravis Dick
Travis Dick
AEAlessandro Epasto
Alessandro Epasto
AJAdel Javanmard
Adel Javanmard
JKJosh Karlin
Josh Karlin
PZPeilin Zhong
Peilin Zhong
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.

10 June 2024
Verified
Conference Paper
Open access
HEHossein Esfandiari
Hossein Esfandiari
PKPraneeth Kacham
Praneeth Kacham
VMVahab Mirrokni
Vahab Mirrokni
DWDavid P. Woodruff
David P. Woodruff
PZPeilin Zhong
Peilin Zhong
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.

17 June 2023
Verified
Conference Paper
Open access
AAAmirMohsen Ahanchi
AmirMohsen Ahanchi
AAAlexandr Andoni
Alexandr Andoni
MHMohammadTaghi Hajiaghayi
MohammadTaghi Hajiaghayi
MKMarina Knittel
Marina Knittel
PZPeilin Zhong
Peilin Zhong
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
Verified
Conference Paper
Open access
HEHossein Esfandiari
Hossein Esfandiari
VMVahab Mirrokni
Vahab Mirrokni
PZPeilin Zhong
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 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.

3 August 2025
Verified
Conference Paper
Open access
TDTravis Dick
Travis Dick
AEAlessandro Epasto
Alessandro Epasto
AJAdel Javanmard
Adel Javanmard
JKJosh Karlin
Josh Karlin
AMAndrés Muñoz Medina
Andrés Muñoz Medina
PZPeilin Zhong
Peilin Zhong