DAMS: Differentially Private Sketching Data Structures

We propose an improved private count-mean-sketch data structure and show its applicability to differentially private contact tracing. Our proposed scheme (Diversifed Averaging for Meta estimation of Sketches-DAMS) provides a better trade-off between true positive rates and false positive rates as well as a variance reduction while maintaining differential privacy (a widely accepted formal standard for privacy) with respect to count, inner-product and range queries.