Search papers, labs, and topics across Lattice.
This paper introduces the concept of differentially private Hierarchical Heavy Hitters (HHH) in both streaming and non-streaming contexts, addressing a significant gap in the literature regarding privacy-preserving data analysis. The authors reveal that in the non-streaming case, the relative error in estimating counts for any prefix is unaffected by the hierarchy's height or the number of heavy hitters, leading to improved error guarantees over existing methods. In the streaming setting, they overcome challenges related to high global sensitivity of approximation functions, demonstrating that absolute error in frequency estimation remains independent of available space.
Surprisingly, the error in estimating counts for hierarchical prefixes remains constant regardless of hierarchy height or the number of heavy hitters.
The task of finding Hierarchical Heavy Hitters (HHH) was introduced by Cormode et al. [12] as a generalisation of the heavy hitter problem. While finding HHH in data streams has been studied extensively, the question of releasing HHH when the underlying data is private remains unexplored. In this paper, we formalise and study the notion of differentially private HHH, in both the streaming and non-streaming setting. In the non-streaming setting, we show the surprising result that the relative error in estimating the count for any prefix is independent of the height of the hierarchy and the number of heavy hitters in the stream. Additionally, our algorithms also improve the error guarantees of Ghazi et al. [24] for the problem of counting over trees. Meanwhile, in the streaming setting, the main issue is that although the exact version of HHH has low global sensitivity (as counting queries are 1-sensitive), the approximation functions due to streaming have high global sensitivity, linear in the available space. Despite this obstacle, we show that the absolute error for estimating frequencies in the streaming setting is independent of the available space.