Timezone: »

 
Poster
Differentially Private Linear Sketches: Efficient Implementations and Applications
Fuheng Zhao · Dan Qiao · Rachel Redberg · Divyakant Agrawal · Amr El Abbadi · Yu-Xiang Wang

Thu Dec 01 09:00 AM -- 11:00 AM (PST) @ Hall J #932
in Poster Session 5 »

Linear sketches have been widely adopted to process fast data streams, and they can be used to accurately answer frequency estimation, approximate top K items, and summarize data distributions. When data are sensitive, it is desirable to provide privacy guarantees for linear sketches to preserve private information while delivering useful results with theoretical bounds. We show that linear sketches can ensure privacy and maintain their unique properties with a small amount of noise added at initialization. From the differentially private linear sketches, we showcase that the state-of-the-art quantile sketch in the turnstile model can also be private and maintain high performance. Experiments further demonstrate that our proposed differentially private sketches are quantitatively and qualitatively similar to noise-free sketches with high utilization on synthetic and real datasets.

Keywords: differential privacy · frequency · Linear Sketch · Quantile · Top K · Frequent Items · Heavy Hitter · Streaming Algorithm
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Fuheng Zhao (UC Santa Barbara)
Dan Qiao (UCSB)
Rachel Redberg (UC Santa Barbara)
Divyakant Agrawal (University of California-Santa Barbara)
Amr El Abbadi (University of California, Santa Barbara)
Yu-Xiang Wang (UC Santa Barbara)

More from the Same Authors