Differentially Private Hierarchical Heavy Hitters

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Differentially Private Hierarchical Heavy Hitters

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

Differentially Private Hierarchical Heavy Hitters* Ari Biswas, University of Warwick, [email protected] Graham Cormode, University of Oxford, [email protected] Yaron Kanza, AT&T Research, [email protected] Divesh Srivastava, AT&T Research, [email protected] Zhengyi Zhou, AT&T Research, [email protected]

Abstract The task of finding Hierarchical Heavy Hitters (HHH) was introduced by Cormode et al. [VLDB 2003] 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 study differentially private HHH release 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 residual count for any prefix is independent of the height of the hierarchy and the number of heavy hitters in the stream. Meanwhile, in the streaming setting, 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 steaming setting is independent of the available space.

1 Introduction The task of finding Heavy Hitters (HH), a.k.a. frequent items, in a dataset is one of the most well-studied problems in data science. The task has been studied under the streaming model of computation [12, 13], distributed computation [10], and even through the lens of secure computation [15]. In this work, we adopt the lens of differential privacy (DP) to study the Hierarchical Heavy Hitters (HHH) problem, introduced by Graham Cormode, Flip Korn, Shanmugavelayutham Muthukrishnan, and Divesh Srivastava. [13] as a general isation of the heavy hitter problem. The problem of DP-HHH is motivated by the observation that data is often both hierarchical and confidential. Consider checking for evidence of discrimination in mortgage lending decisions, as discussed in [32]. An analyst is given a database of historical lending decisions and asked to ascertain if a particular demographic has been treated unfairly. The personal information about loan applicants is inherently hierarchical. For example, a person’s residential address can be divided into street address, postcode, village, city, country, and so on. As historical data is often difficult to obtain, any given dataset might not include enough applicants from every fine-grained portion of the hierarchy. However, if we analysed the data at a coarser granularity, we might find a statistically significant number of participants to draw reliable conclusions. Naturally, whether hierarchical or not, demographic information is considered highly confidential. It is well known that even releasing summary statistics about a population can leak information about individuals in the dataset. Differential privacy has become the de facto standard for defending against such leakage. As a result, given a dataset, we wish to output its hierarchical heavy hitters privately.

* The original conference version accepted at PODS 2025 has a bug in the privacy analysis. The error was brought to our attention in personal communication with Christian Janos Lebeda, David Erb, Tudor Cebere, and Aurélien Bellet. , and details of the issue can be found in their manuscript [31].

Ari, Cormode, Kanza, Srivastava, Zhou

5 5

100

3 5

5 45

Hierarchical Heavy Hitters

3 5

5 45

Heavy Hitters

Figure 1: A dataset of 100 elements over a hierarchy with residual counts (left) and unconditional counts (right).

Note that finding hierarchical heavy hitters is not the same as finding heavy hitters at each level in a hierarchy (referred to as counting over trees in [23]). Hierarchical heavy hitters, which we formally define later (Definition 2.3.5), is a generalisation of the heavy hitters problem. At a high level, apart from telling us if an element is heavy, it also tells us how it is heavy. HHH allows us to distinguish between an element that is heavy because it has a heavy child (or a few heavy children) and an element that is heavy because it has many light children that are cumulatively heavy. Furthermore, if we are given the set of (exact) hierarchical heavy hitters of a dataset, we can derive the heavy hitters at each level of the hierarchy. The converse, however, is not true. Figure 1 illustrates this difference with a toy example. The figure shows a dataset of 100 elements drawn from a hierarchy of height 3. Each node in the tree corresponds to an element in the hierarchical universe. The leaf nodes are fully specified elements, while the root node describes the fully generalised element of the hierarchy. The edges between nodes represent a partial order between elements of the hierarchy (see Section 2 for formal details). Given a public threshold of 𝜏 = 10, a node is heavy if its count exceeds 𝜏 . The counts listed next to the nodes on the right tree are the underlined unconditional counts (Definition 2.3.1) of the node in the dataset. The nodes marked in teal on the right tree are the heavy hitters at each level of the hierarchy. The nodes marked in teal on the left tree are the hierarchical heavy hitters of the dataset. The counts listed next to the nodes on the left tree are called underlined residual counts (Definition 2.3.2). The residual count of a node is the count of a node ignoring its heavy children, whereas the unconditional count of a node is just the sum of the counts of its children. Observe that the root node is not a hierarchical heavy hitter, although its absolute count is greater than the threshold. The root node is heavy only because it has heavy children, not because it is an aggregation of several light children. If we were to just see the output of heavy hitters, we would lose this information.

1.1 Related work 1.1.1 Streaming HHH The hierarchical heavy hitter problem was first defined and studied in the streaming setting, as the offline problem is straightforward. Initial work defined the problem for streams of data drawn from a single hierarchy, and showed upper bounds on the problem, by building streaming heavy hitter summaries of data at each level [13, 33, 36]. Subsequent work extended the problem to data with multiple hierarchical attributes [11, 12], and showing lower bounds on the space required to solve the problem [26, 36]. In the streaming model, data arrives incrementally, and we assume that the algorithm does not have enough space to store the entire dataset, or enough counters for each element of the data universe. Michael Mitzenmacher, Thomas Steinke, and Justin Thaler. [36] show that approximating HHH via the Space Saving algorithm (SS) for heavy hitters [35] is optimal in terms of error and space complexity in the streaming setting. 1.1.2 Private Counting Despite its relevance to data analytics, the HHH problem has not been previously studied under differential privacy. However, there has been much research on simpler non-hierarchical heavy hitter estimation under 2

Differentially Private Hierarchical Heavy Hitters

privacy, in both the non-streaming [2, 3, 14, 24, 29], and streaming models [8, 30]. In this work, we show that despite this extensive body of work in the non-hierarchical setting, we need new algorithms to privately estimate HHH efficiently in theory and practice. The most closely related work to ours is concerned with outputting “unconditional counts” in a hierarchy, due to Ghazi et al. [23]. As any fully specified element (“leaf”) affects the counts for nodes at each level of the hierarchy, we must account for it every time we release a count for a node that is an ancestor of said leaf. Hence, the DP error scales linearly with the height ℎ √ of the hierarchy when using basic composition, or ℎ under advanced composition [20]. Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. [22] provide lower bounds showing that such a polynomial depen dence on the hierarchy height is unavoidable if we want to estimate just the unconditional counts for every element in the hierarchy1 with pure or approximate differential privacy (see Appendix B). Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. [23] circumvent this dependence on

the height of the hierarchy by relaxing the problem to consider relative error in estimating node counts, where the estimation gap for a node scales with the absolute count of the node2. Their algorithmic guarantees replace the linear dependence on the height of the hierarchy with a linear dependence of the maximum number of hierarchical heavy hitters in a dataset3. Although this is an asymptotic improvement, the number of heavy hitters is much larger than the hierarchy height for any practical scenario we can envisage. Hence the real-world performance will be much worse than the naive baseline of estimating the counts at each level and paying for ℎ levels of composition. Concretely, most real-world datasets are associated with shallow and wide hierarchies. Consider a dataset of bit strings of size 𝑛 = 106 , and a threshold of 2500, so there are up to 400 hierarchical heavy hitters. For this algorithm to improve on the simple baseline, the hierarchy would need to have more than 400 levels, implying over 2400 elements.

1.2 Our results 1.2.1 Non-Streaming Setting In this work, we show that the relative error4 for any node when estimating private hierarchical heavy hitters scales by a much smaller constant that is independent of both the height of the hierarchy and the number of hierarchical heavy hitters in the tree. Our algorithm is simpler to describe than that of [23:Algorithm 1], and it can be used to solve the more general problem with better error guarantees than prior attempts would imply. More specifically, the variance parameter of the noise added to each element is independent of both the height of the hierarchy and the number of heavy hitters. At a high level, an intuitive explanation is that by targeting relative error instead of absolute error, elements higher up in the hierarchy with larger frequencies can tolerate more DP noise. This structure proves to be critical for circumventing composition bounds, by allowing us to re-use information about lower regions of the hierarchy, and apply them to higher regions of the hierarchy. Bounding the absolute error for every node requires us to treat each node independently, therefore destroying the structure we leverage to propose more accurate algorithms. 1.2.2 Streaming Setting In the streaming setting, along with DP error and composition error, we also need to account for the approximation error due to space constraints. The main issue with streaming algorithms is that although 1

This is a strictly simpler problem than HHH, which involves estimating unconditional counts. Therefore these lower bounds immediately apply to HHH as well. 2 In other words, nodes with large unconditional frequencies are allowed to tolerate more estimation error than nodes with smaller unconditional frequencies. 3 Algorithm 1 of their paper uses the constant 𝑐, independent of the height of the hierarchy, as an upper bound on the maximum number of hierarchical heavy hitters. 4 We use a slightly different definition of relative error than [23], but one which we believe is more natural. Nevertheless the argument holds in general.

Ari, Cormode, Kanza, Srivastava, Zhou

the exact version of the function (exact hierarchical heavy hitters) has low global sensitivity (as counting queries are 1-sensitive), the approximation function can have high global sensitivity. For instance, the Space Saving (SS) algorithm described by Michael Mitzenmacher, Thomas Steinke, and Justin Thaler. [36] is optimal in the non-private setting, but T -H Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. [8] show that the global sensitivity of the approximation function induced by SS scales linearly with the number of counters per sketch (denoted with 𝜅 in this document). This would imply that scale of the noise used per node also scales linearly with 𝜅. However, Christian Janos Lebeda and Jakub Tetek. [30] improve on this naive bound by providing a DP mechanism for non-hierarchical heavy hitters, where the estimation error of the protocol does not rely on global sensitivity. Inspired by [30], we design algorithms for hierarchical heavy hitters with DP noise whose variance is independent of 𝜅. The intuition behind our algorithm is that although the approximation algorithm we use has high sensitivity, the counters in a sketch are highly correlated, with few degrees of freedom. This structure (correlated counters) can be used to bypass composition bounds typically enforced due to high global sensitivity of the function. This observation is closely related to why the seminal Sparse Vector Technique algorithm (SVT) by Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. [19] also circumvents composition bounds. Although the two appear unrelated at first glance, we show that releasing private counts for our sketching algorithm and SVT algorithm are essentially equivalent and use the same underlying theoretical concepts to bypass composition. More broadly, the message of this work is that “where we have structure (sparsity, monotonicity, correlation, etc.), we can leverage this structure to circumvent basic or advanced composition bounds”. Hierarchies offer structure in that the frequency of elements higher up in the hierarchy is computed using frequencies of elements lower down. In streams, we show that despite high global sensitivity, we can leverage correlation between counters in a sketch to circumvent composition bounds. We refer the reader to Appendix A for further discussion on the role of structure in circumventing composition. To summarize: 1. In Section 3, we propose the first known private algorithm for the task of hierarchical heavy hitter estimation. In the non-streaming setting, the relative error of our algorithm is independent of the height of the hierarchy and the number of hierarchical heavy hitters in the dataset. 2. In the streaming setting (Section 4), we show that the DP error of our HHH estimation algorithm is independent of the space bound. However, in this setting, the DP error still depends on the height of the hierarchy. Therefore, there is a gap in relative estimation error between the streaming setting and the nonstreaming setting under privacy. Despite this gap, for all practical situations, removing the dependence on space is far more critical than the dependence on the height of the hierarchy (as the number of counters is often orders of magnitude larger than the height of the hierarchy). The rest of the paper is organised as follows. In Section 2, we formally introduce the problem of hierarchical heavy hitter estimation and review preliminary results from differential privacy. In Section 3 we describe our solution in the non-streaming setting with unlimited space. In Section 4, we describe our algorithm in the streaming setting.

2 Prelims and Problem Statement 2.1 General Notation We describe sets with calligraphic font ℋ︀. For a probability distribution 𝐷, we denote with 𝑥 ←$𝐷 the event of sampling 𝑥 according to 𝐷. We highlight random variables and samples to distinguish them from constants, as shown above. For a randomized algorithm 𝐴, the notation 𝐴(𝑋; 𝑧, 𝑤) means that 𝐴 is run on

Differentially Private Hierarchical Heavy Hitters

input 𝑋 with random samples 𝑧 and 𝑤. If an argument is written without highlighting, as in 𝐴(𝑋; 𝑧, 𝑤), that value is fixed. For example, 𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ conditions on the fixed value 𝑤⃗ and leaves only 𝑣 ⃗ random. We write [𝑛] to denote the set {1, …, 𝑛}. For any event 𝐸, we denote with 𝐸, the complement of the event. Let 𝑧 ⃗ = (𝑧𝑖 )𝑖∈ℋ︀ be a vector indexed by an ordered set ℋ︀. Given ordered subset 𝒥︀ = (𝑗1 , …, 𝑗𝑚 ) ⊆ ℋ︀, the restriction of 𝑧 ⃗ to 𝒥︀ is given by 𝑧𝒥︀⃗ ≔ (𝑧𝑗1 , …, 𝑧𝑗𝑚 ).

(1)

When an algorithm 𝐴 has vector-valued output, we write 𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ 𝒥︀ for that output restricted to 𝒥︀. Next, we first review the necessary tools from differential privacy and its basic properties, and then formalise the idea of a hierarchical domain.

2.2 Differential Privacy Definitions We begin the standard definition of neighbouring datasets. Let 𝑋 and 𝑋 ′ be a multi sets of elements picked from some (possibly hierarchical) domain ℋ︀. 𝑋 and 𝑋 ′ are said to be neighbouring, (denoted as 𝑋 ∼ 𝑋 ′ ), if they differ by one element only, i.e., 𝑋 ′ = 𝑋 ∪ {𝑥′ }, or vice-versa. The following definition of differential privacy is often referred to as addition & removal differential privacy5. Definition 2.2.1 (Differential Privacy (DP)) Fix some function 𝑓 that maps a set of elements from a hierarchical domain ℋ︀ to some range 𝒴︀. Fix 𝑛 ∈ ℕ. Let 𝑋 ∈ ℋ︀𝑛 and 𝑋 ′ ∈ ℋ︀𝑛+1 denote any pair of neighbouring datasets. For 𝜀 > 0 and 𝛿 = 𝗇𝖾𝗀𝗅(𝑛), where 𝗇𝖾𝗀𝗅(⋅) is a negligible function in 𝑛, we say a random algorithm 𝘔 computes 𝑓 with (𝜀, 𝛿)-differential privacy if and only if for all 𝒜︀ ⊆ 𝒴︀, 𝑒−𝜀 (Pr[𝘔(𝑋 ′ , 𝑓) ∈ 𝒜︀] − 𝛿) ≤ Pr[𝘔(𝑋, 𝑓) ∈ 𝒜︀] ≤ 𝑒𝜀 Pr[𝘔(𝑋 ′ , 𝑓) ∈ 𝒜︀] + 𝛿 The special case of (𝜀, 𝛿)-DP with 𝛿 = 0 is referred to as pure DP, whereas 𝛿 > 0 is known as approximate DP. A standard approach to obtain DP is to add noise proportional to the global sensitivity of the function being evaluated. Given any function 𝑓 that maps a set of elements from a hierarchical domain ℋ︀ to ℝ, we define the global sensitivity Δ𝐺 (𝑓) of 𝑓 as Δ𝐺 (𝑓) ≔ max′ ‖𝑓(𝑋) − 𝑓(𝑋 ′ )‖1 , (𝑋, 𝑋 )

(2)

where the maximum is taken over any pair of neighbouring datasets 𝑋, 𝑋 ′ . It is well known that the global sensitivity of a counting query, such as the queries defined in Definition 2.3.1 and Definition 2.3.2 is 1. The following facts about differential privacy can be found in any introductory textbook on differential privacy [20]. Theorem 2.2.2 (Laplace Histograms ) Let 𝑓 be a function that maps elements from some domain to a subset of ℝ𝑑 , that has global sensitivity Δ𝐺 . Then the Laplace mechanism 𝘔 defined as 𝘔(𝑋) = 𝑓(𝑋) + (𝑌1 , …, 𝑌𝑑 ) where each 𝑌1 , …, 𝑌𝑑 ← 𝖫𝖺𝗉𝗅𝖺𝖼𝖾(Δ𝐺 /𝜀) is 𝜀-DP.

5 See https://differentialprivacy.org/one-sided/ for a more complete description of the nomenclature. The constants in the relative error of our results for non-streaming HHH can be further improved if we focused on just removal only privacy, but we choose to tackle the more complete definition.

Ari, Cormode, Kanza, Srivastava, Zhou

Theorem 2.2.3 (Basic Composition ) Let 𝘔1 and 𝘔2 be a (𝜀1 , 𝛿1 )-DP and (𝜀2 , 𝛿2 )-DP algorithm respectively. 𝘔(𝑋) = (𝘔1 (𝑋), 𝘔2 (𝑋)) is ((𝜀1 + 𝜀2 ), (𝛿1 + 𝛿2 ))-DP.

Theorem 2.2.4 (Post Processing) Let 𝘈1 be an (𝜀, 𝛿)-DP algorithm and 𝘈2 be a (possibly randomised) post-processing algorithm. Then the algorithm 𝘈(𝑥) = 𝘈2 (𝘈1 (𝑥)) is still an (𝜀, 𝛿)-DP algorithm.

2.3 Hierarchies Formally, a hierarchical domain is a set 𝒰︀ associated with a partial order (≻). In streaming literature [13, 36], this partial order is often represented by a function called 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾 : 𝒰︀ → 𝒰︀ which maps elements of the universe to other elements in the universe6. In this work, it suffices to think of a hierarchical domain as the set of elements that has one to one mapping with the nodes of a rooted tree with finite arity7. For any element 𝑥 ∈ 𝒰︀, 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾(𝑥) refers to the parent or prefix of 𝑥. We say an element ∗ is fully generalised or the root of the tree if 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾(∗) = ∗. We say an element 𝑒 is fully specified if there exists no 𝑠 ∈ 𝒰︀ such that 𝑒 = 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾(𝑠) (𝑒 is a leaf node of the rooted tree representing the hierarchy). We denote by 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾(𝑘) (𝑥) as the ancestor of 𝑥 that is 𝑘 steps away in the tree representation (element obtained by applying 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾 𝑘 times on 𝑥). The pair (𝒰︀, 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾) defines a hierarchical domain ℋ︀. The height ℎ of the hierarchy represents the maximum number of times any fully specified element must be generalised to get a fully generalised element (or more simply, the height of the tree representing the hierarchy). As a concrete example of a single-dimensional hierarchy, one can imagine 𝒰︀ to be the set of prefixes of ℎ-bit strings. When ℎ = 4, this universe has 16 fully specified elements: 0000, 0001, …, 1111. The prefix 000 ∗ is a generalisation of 0000 and 0001. We use notation 𝑥 ≻ 𝑝 (read as 𝑝 is reachable from 𝑥) if there exists a 𝑘 ∈ ℕ such that 𝑝 = 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾(𝑘) (𝑥), and 𝑥 ⪰ 𝑝 if 𝑝 = 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾(𝑘) (𝑥) ∨ 𝑥 = 𝑝. For any 𝑝 ∈ ℋ︀, 𝖲𝗎𝖼𝖼(𝑝) ≔ {𝑞 ∈ ℋ︀ : 𝑞 ≻ 𝑝} denotes the strict successors of 𝑝, and 𝖯𝖺𝗋(𝑝) ≔ {𝑞 ∈ ℋ︀ : 𝑝 ⪰ 𝑞} the ancestors of 𝑝 (including 𝑝 itself). Henceforth, we assume that any dataset 𝑋 is a multiset of fully specified elements from some hierarchical universe ℋ︀ of height ℎ. Throughout, we use the the convention wehere 𝑋 ′ ≔ 𝑋 ∪ {𝑥′ } is the larger multiset and has the extra fully specified element 𝑥′ . Definition 2.3.1 (Unconditional Count or Absolute Frequency) Given a dataset 𝑋, the unconditional frequency of any element 𝑝 ∈ ℋ︀, denoted by 𝑓𝑋 (𝑝), is the number of elements in 𝑋 that generalise to 𝑝. 𝑓𝑋 (𝑝) = ∑ 𝟙[𝑒 ⪰ 𝑝] 𝑒∈𝑋

In Figure 1, the unconditional counts of each node are written next to each node in the tree for the figure on the right. Definition 2.3.2 (Residual Count / Conditional Frequencies) Given a dataset 𝑋, and a set 𝒮︀ ⊆ ℋ︀, we say 𝑥 ≻ 𝒮︀ if there does not exist 𝑞 ∈ 𝒮︀ such that 𝑥 ⪰ 𝑞. We define the conditional or residual count 𝐹𝑋,𝒮︀ (𝑝) of a prefix 𝑝 with respect to 𝒮︀ as the sum of all fully specified elements who do not have a parent already in 𝒮︀.

𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾 encodes partial order binary relation 𝑅 : 𝒰︀ × 𝒰︀ → {0, 1}, such that 𝑅(𝑥, 𝑝) = 1 ⟺ 𝑝 = 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾(𝑥) The HHH literature also considers multi-dimensional hierarchies, where the universe is represented by nodes of a lattice rather than a rooted tree. However, in this work, we focus on single dimensional hierarchies which can be represented by a tree. 7

Differentially Private Hierarchical Heavy Hitters

𝐹𝑋,𝒮︀ (𝑝) ≔

∑

𝑓𝑋 (𝑒)

𝑒∈𝑋∧ 𝑒⪰𝑝∧ 𝑒≻𝒮︀

We will use 𝐹𝑋′ ,𝒮︀′ (𝑝) ≔ ∑𝑒∈𝑋∧ 𝑒⪰𝑝∧ 𝑒≻𝒮︀ 𝑓𝑋′ (𝑒) to denote the residual count when using 𝑋 ′ ≔ 𝑋 ∪ {𝑥′ } as the input dataset. In the left tree in Figure 1, the set 𝒮︀ is shown by nodes in teal, and the conditional count with respect to 𝒮︀ is written by each node. Definition 2.3.3 (Level Of A Node / Prefix) The level of a prefix 𝑝 ∈ ℋ︀ is the (minimum) number of applications of 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾 to reach ∗ i.e. 𝖫𝖾𝗏𝖾𝗅(𝑝) = 𝑘 ⟺ ∗ = 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾(𝑘) (𝑝). For example, let ℋ︀ be the set of 4-bit bistrings. If we generalise 011 ∗ three times we get to ∗, so the level of the prefix is 3. The fully specified elements or leaf elements are at level ℎ = 4 and ∗ is at level 0. With these definitions in place, we can formally define the concept of a heavy hitter and a hierarchical heavy hitter. Definition 2.3.4 (Exact Heavy Hitters) For dataset 𝑋 and threshold 𝜏 ∈ ℝ, we say prefix 𝑝 is a heavy hitter (HH) if 𝑓𝑋 (𝑝) > 𝜏 . The set of heavy hitters of 𝑋 is ℋ︀ℋ︀ = {𝑒 ∈ 𝑋 : 𝑓𝑋 (𝑒) ≥ 𝜏 }.

Definition 2.3.5 (Exact Hierarchical Heavy Hitters) The set of exact hierarchical heavy hitters is defined inductively. Let 𝑋 denote a dataset drawn from a hierarchy of height ℎ, then 1. ℋ︀ℋ︀ℋ︀ℎ denotes the exact heavy hitters in 𝑋. 2. For any prefix 𝑝 at level 0 ≤ 𝑙 < ℎ, let 𝐹ℋ︀ℋ︀ℋ︀𝑙+1 (𝑝) be the residual count (Defn. Definition 2.3.2) of 𝑝 given ℋ︀ℋ︀ℋ︀𝑙+1 . Then ℋ︀ℋ︀ℋ︀𝑙 is defined as ℋ︀ℋ︀ℋ︀𝑙+1 ∪ {𝑝 ∈ 𝖫𝖾𝗏𝖾𝗅(𝑙) : 𝐹ℋ︀ℋ︀ℋ︀𝑙+1 (𝑝) ≥ 𝜏 }. 3. ℋ︀ℋ︀ℋ︀0 is the set of exact hierarchical heavy hitters of 𝑋. As discussed earlier, Figure 1 illustrates this difference between heavy hitters and hierarchical heavy hitters. 2.3.1 Approximate Hierarchical Heavy Hitters In this paper, the function 𝑓 that our algorithm 𝘔 computes is the hierarchical heavy hitters of a dataset 𝑋. By definition, differential privacy restricts us from outputting exact answers or using a deterministic algorithm to compute approximate values. As the output must be random, we can no longer output exact counts of the hierarchical heavy hitter problem. Thus, keeping in line with the definitions introduced in [13, 36] we define the task of approximate heavy hitters, where the estimates are within some approximation error 𝛼 with high confidence 1 − 𝛽. As we now have noise in the system, we relax the threshold by 𝛼 units, where 𝛼 allows the error to grow larger for larger values (i.e., relative error). Clearly the smaller the value of 𝛼, the closer we are to the definition of exact hierarchical heavy hitters. The coverage constraint says we relax our definition of what is heavy due to DP noise i.e., prevent false positives. Our goal is to come up with a theoretical bound on the error, and show that the error is small enough for practical use cases. Definition 2.3.6 (Private Approximate Hierarchical Heavy Hitters) Let 𝘔 denote an algorithm that receives as input a multi set 𝑋 of 𝑛 fully specified elements from some hierarchical domain ℋ︀. Fix a public threshold 𝜏 ∈ ℝ, a confidence parameter 𝛽 ∈ (0, 1), privacy parameters 𝜀 ∈ (0, log 𝑛) and 𝛿 = 𝗇𝖾𝗀𝗅(𝑛). We say the algorithm 𝘔 correctly finds approximate private hierarchical heavy hitters with relative error (𝛽, 𝛼) if it outputs 𝒮︀ ⊆ ℋ︀ and approximate counts 𝑓̃𝑋 (𝑝) such that:

Ari, Cormode, Kanza, Srivastava, Zhou

1. Privacy: 𝘔 is (𝜀, 𝛿)-DP. ̃

𝑓𝑋 (𝑝) 2. Simultaneous Relative Error: With probability 1 − 𝛽 we have max𝑝∈ℋ︀ | 𝑓𝑋 (𝑝)− | ≤ 𝑂(𝛼). 𝑓 (𝑝) 𝑋

3. Coverage: With probability 1 − 𝛽, every 𝑝 ∈ 𝒮︀ satisfies 𝐹𝑋,𝒮︀ (𝑝) ≥ 𝜏 − 𝛼 (no false positives), and every 𝑝 ∉ 𝒮︀ satisfies 𝐹𝑋,𝒮︀ (𝑝) ≤ 𝜏 + 𝛼 (with 𝐹𝑋,𝒮︀ (𝑝) as defined in Definition 2.3.2). We want to show that in the non-streaming setting, the relative error 𝛼 of our algorithm does not grow linearly with the the height of the hierarchy8, and is independent of the number of heavy hitters in the hierarchy (as discussed in the introduction above). In the streaming setting we will have to deal with error due to privacy and lack of space. Thus, the streaming version of our problem is the exact same problem with limited space. Definition 2.3.7 (Streaming Private HHH) The streaming problem is to solve Definition 2.3.6 with a constant amount of space 𝜅 = 𝑂(1). Of course, to prevent the problem from being degenerate, we will assume that the amount of space available is significantly smaller than the size of the stream 𝑛 or the size of the universe |ℋ︀|.

3 Offline Private Hierarchical Heavy Hitters In this section, we tackle the offline version of the problem, with no space constraints. Before describing the complete protocol and showing how it solves Definition 2.3.6, we provide an intuitive explanation of the techniques used to circumvent the dependence the height of the hierarchy and the number of hierarchical heavy hitters by working through a sequence of attempts. Let ℋ︀ denote a hierarchy with height ℎ and let 𝑋 denote a dataset of 𝑛 fully specified elements drawn from ℋ︀.

3.1 Laplace Histograms Observe that the unconditional frequencies for each prefix of the hierarchy can be estimated by computing ℎ histograms for each level of the hierarchy. For two neighbouring datasets 𝑋 and 𝑋 ′ that differ by a single input only, there is exactly one node per level for which the unconditional frequency of the nodes differ by one under 𝑋 and 𝑋 ′ . Thus, a first approach to hierarchical heavy hitter estimation is to release ℎ Laplace histograms by adding noise drawn from a Laplace noise distribution with scale ℎ𝜀 to every node in the hierarchy. By the privacy of the Laplace histograms (Theorem 2.2.2), each level is 𝜀/ℎ-private. As any node contributes to at most ℎ counts, by basic composition and the privacy of the Laplace mechanism, the set of realised counts is (𝜀, 0)-DP. Then, one could compute hierarchical heavy hitters via post-processing, which does not affect the privacy of the algorithm (Theorem 2.2.4). As we add noise with scale ℎ𝜀 to each node in ℋ︀, the DP error per node scales linearly in the height of the hierarchy. Furthermore, if we wanted to upper bound the simultaneous error over all prefixes in the hierarchy, then we need to apply the union bound over all nodes of the hierarchy. As the number of nodes is exponential in the height of the hierarchy, the relative estimation error scales 𝗉𝗈𝗅𝗒(ℎ).

As we want to bound the worst case simultaneous relative error for any element in the hierarchy, logarithmic dependence on height is unavoidable (via the union bound).

Differentially Private Hierarchical Heavy Hitters

3.2 Stability Histograms One solution to circumventing such a union bound over all the elements of the universe when the size of the universe is very large is to use stability histograms [2, 6, 42] instead of Laplace histograms. For fixed privacy parameters 𝜀 ∈ (0, log 𝑛) and 𝛿 = 𝗇𝖾𝗀𝗅(𝑛), the key intuition behind stability histograms is that if we only released private estimates (using the Laplace mechanism) for nodes with large enough non-zero frequency, the simultaneous error bound improves from log(|ℋ︀|) to log(𝑛) < log(1/𝛿) (as there are at most 𝑛 elements in 𝑋). This is advantageous when |ℋ︀| ≫ 𝑛 meaning that many nodes have zero frequency. For such nodes, we incur no error at all (as the algorithm ignores them). However, this technique cannot achieve pure DP as was possible in the Laplace histogram case. Observe that if 𝑋 ′ contains an element 𝑥′ that is not present in 𝑋 (we call such an 𝑥′ isolated), an adversary can perfectly distinguish between 𝑋 and 𝑋 ′ if the count of this element, albeit noisy, appeared in the output (as when processing 𝑋, nodes representing generalisations of 𝑥′ would have frequency 0, and would be ignored). Nevertheless, since stability histograms only output counts for elements with “large” counts, and as the frequency of such an isolated element 𝑥′ is 1 (from the definition of neighbouring datasets), we can set the frequency threshold for “large enough” such that with probability at least 1 − 𝛿 the isolated element will never show up in the final output. This is sufficient to achieve (𝜀, 𝛿)-DP. Over the whole tree representing the hierarchy, the case where 𝑥′ distinguishes 𝑋 and 𝑋 ′ can occur at at most ℎ levels of ℋ︀. Thus, if we output stability histograms with 𝛿 ′ = 𝛿/ℎ at each level then, by basic composition, the final output does not contain any isolated elements with probability at least 1 − 𝛿. In this way, stability histograms allow us to circumvent the union bound over all the nodes in ℋ︀, at the cost of going from pure to approximate DP. It does not however, circumvent the issue discussed above where the scale of the DP noise is ℎ𝜀 . In recent work, Christian Janos Lebeda, David Erb, Tudor Cebere, and Aurélien Bellet. [31] apply stability his tograms to finding a set of heavy nodes within a hierarchy. Their algorithm performs a set of parallel binary searches up and down the hierarchy, ensuring that each input element is only queried log ℎ times, so that the scale of the DP noise is poly-logarithmic in ℎ instead of polynomial in ℎ. Their notion of “heavy node” is similar to that of hierarchical heavy hitters, but there is no concept of residual count: any node marked as heavy automatically implies that all of its ancestors are heavy as well. Thus, this stability histogram-based approach does not solve the DP-HHH problem, and suggests a separation between the two problems of finding heavy nodes in a hierarchy and of finding hierarchical heavy hitters.

3.3 DP Counting On Trees One approach to resolving this issue is to make repeated use of the Above-Threshold Algorithm by Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. [19]. Given a hierarchy ℋ︀ then, by 𝑛 definition, there can be at most 𝑐 = 𝜏−Δ hierarchical heavy hitters. Observe that 𝑐 is a constant that depends only on 𝜏 and Δ, and is independent of the height of the hierarchy ℎ. When the height of the hierarchy ℎ is large and 𝑐 ≪ ℎ, we would incur lower per-node DP error if the scale of the noise were 𝜀𝑐 instead of ℎ𝜀 . Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. [23] observed this fact and proposed an algorithm that traverses the tree bottom up. At each level of the tree, their algorithm inspects only one node, the one with maximal unconditional count for that level. There are at most ℎ such nodes (one per level). However, even in the worst case, at most 𝑐 out of ℎ of these nodes can be conditionally heavy. Thus, we have ℎ counting queries, out of which 𝑐 are conditionally heavy. Their solution implicitly uses the Sparse Vector Technique (SVT) by composing Above-threshold ℎ times, but they pay only for the 𝑐 conditionally heavy nodes. Once 𝑐 levels have been identified, the algorithm prunes the tree, and restricts it to just the 𝑐 levels with at least one conditionally heavy node. Then it estimates the counts of the pruned tree by solving 𝑐

Ari, Cormode, Kanza, Srivastava, Zhou

instances of the private stability histogram estimation problem9 with privacy budget 𝜀/𝑐. As commented in the introduction, although this is an asymptotic improvement, it is very hard to imagine cases where 𝑐 ≪ ℎ. Thus, the simple Laplace stability histograms with composition error ℎ would outperform the algorithm by Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. [23] in almost all feasible situations.

3.4 Our Approach Our algorithm is based on the following critical observation. Although it is true that there are at most 𝑐 conditionally heavy levels in the tree, only one of the conditionally heavy nodes is truly influenced by 𝑥′ . For the remainder of the heavy nodes, there is no difference in the conditional frequencies of 𝑋 and 𝑋 ′ . It is this structure that we want to exploit to improve error our guarantees. In prior work, Haim Kaplan, Yishay Mansour, and Uri Stemmer. [28] show that there are instances where the composition error of the SVT algorithm is suboptimal, even when dealing with a stream of adaptively chosen queries by an unbounded adversary. Instead, they propose a general algorithm (called Threshold Monitor) where DP error of a query scales linearly by a constant 𝑂( 𝜀(𝑘+1) log 1/𝛿 ), where 𝑘 ≥ 1 represents the number of times any data point can contribute to a counting query being heavy. In this work, we revisit the Threshold monitor algorithm under a simplified regime. We note that our setting has a few advantages. Instead of adaptively chosen arbitrary counting queries, we will have a pre-determined set of monotonically increasing counting queries. Additionally for us, the structure of our problems corresponds to the case 𝑘 = 1, which can simplify the analysis. In estimating HHH in the non-streaming setting with central differential privacy, we can pre-select the order of queries to be bottom up (leveraging monotonicity and limited influence of any node), and we do not have to deal with adaptive queries. Thus, in the case of hierarchical heavy hitter estimation, paying a price of 𝑐/𝜀 of SVT or the larger constants of Threshold Monitor for adaptivity in composition is wasteful10. Instead, we use the general idea of threshold monitor, and with more direct privacy analysis we show that DP noise per node scales 𝑐0 /𝜀 instead of 𝑐/𝜀, where 𝑐0 is truly a constant since it is independent of both the height of the hierarchy and the number of heavy hitters in ℋ︀. Furthermore it is smaller than the constants used in threshold monitor. Algorithm 1 shows our algorithm for the non-streaming case.

9 While Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. do not explicitly refer to stability histograms, their use of bounded truncated Laplace noise is equivalent. In the case of bounded noise, the union bound is affected by the size of the support of the truncated noise distribution, which is upper bounded by 𝑂(1/𝛿). For stability histograms, it is affected by the number of elements which is upper bounded by 1/𝛿. 10 In the proofs we will pin-point exactly which parts of the general Threshold monitor algorithm we do not need, and instead can use simpler claims which led to improved constants.

Differentially Private Hierarchical Heavy Hitters

Algorithm 1: Non-Streaming DP-HHH Detection Input: Data 𝑋 of size 𝑛 over hierarchy ℋ︀ with height ℎ, Privacy parameter 𝜀 ∈ (0, log 𝑛), 𝛿 = 𝗇𝖾𝗀𝗅(𝑛), Threshold 𝜏 > 0, Confidence parameter 𝛽 ∈ (0, 1) 1 𝑐0 ≔ log 5 ( 1𝛿 ) 4 𝜂 ≔ log(𝜀 1 ) 2 𝛿

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Δ ≔ 𝜂1 log( 𝜂1 ) ≥ 1 𝜉 ≔ 2𝜂𝑐0 If 𝜏 < 24Δ log(2ℎ/(𝛿𝛽)), then output {} and end program as threshold is too low for stability histograms. for 𝑖 = ℎ, …, 1 do 𝒜︀𝑖 = {𝑝 ∈ ℋ︀ | 𝖫𝖾𝗏𝖾𝗅(𝑝) = 𝑖} for 𝑝 ∈ 𝒜︀𝑖 do If 𝐹𝑋,𝒮︀ (𝑝) = 0 then Continue, ignoring this node. 𝑤𝑝 ←$ 𝖫𝖺𝗉(6Δ) 𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂) 𝑣𝑝 ≔ min{𝑣𝑝 , Δ} if 𝐹𝑋,𝒮︀ (𝑝) + 𝑤𝑝 + 𝑣𝑝 ≥ 𝜏 then Output 𝑏𝑝 = ⊤ Update 𝒮︀ = 𝒮︀ ∪ {𝑝} Output 𝐹̃𝑋,𝒮︀ (𝑝) = 𝐹𝑋,𝒮︀ (𝑝) + 𝖫𝖺𝗉(𝜉) end if end for end for Output 𝒮︀ and {𝐹̃𝑋,𝒮︀ (𝑝)} . 𝑝∈𝒮︀

Algorithm 1: Non-Streaming DP-HHH Detection

Before stating our theorem statement, we introduce notation that is used throughout this section. The above algorithm can be broken down into two steps. First output the set 𝒮︀ with the tops and bots. Then, use the Laplace mechanism to release counts. The main technical challenge will be to prove that the release of 𝒮︀ is private. Much like the original SVT analysis, we can just use sequential composition of the release of actual counts to argue full privacy. Observe that once we fix the output of the algorithm to 𝑏 ⃗ ∈ {⊥, ⊤}|ℋ︀| , this fully determines the set of hierarchical heavy hitters 𝒮︀. That is, 𝒮︀ ≔ 𝒮︀(𝑏)⃗ = {𝑝 ∈ ℋ︀ : 𝑏𝑝 = ⊤}

(3)

Under the same output 𝑏,⃗ the neighbour 𝑋 ′ = 𝑋 ∪ {𝑥′ } induces the same selected set, 𝒮︀′ ≔ 𝒮︀′ (𝑏)⃗ = 𝒮︀. Next observe, that given 𝑏 ⃗ we can partition ℋ︀ into 3 sets ℐ︀Active , ℐ︀Unrelated , ℐ︀After as shown in Figure 2.

Ari, Cormode, Kanza, Srivastava, Zhou

Figure 2: Given any outout 𝑏 ⃗ ∈ {⊥, ⊤}|ℋ︀| we can partition ℋ︀ into 3 sets ℐ︀Active , ℐ︀Unrelated , ℐ︀After . The key insight is that 𝑥′ does not affect the counts of nodes in ℐ︀Unrelated so these nodes will not affect privacy analysis. The nodes in ℐ︀After have the same residual counts in 𝑋 and 𝑋 ′ as 𝑥′ s contribution has been removed at this point. It gets removed exactly at 𝑖⋆ marked in red solid colour inside the dotted block.

Before we can formally define the conditions of membership of the above sets, we need to define the Inflexion operator. Definition 3.4.1 (Inflexion Operator And The Stopped Path) Fix a sequence of counting queries (𝑝1 , …, 𝑝ℎ ) ordered from leaf-to-root and an output vector 𝑎⃗ ∈ (⊥, ⊤)ℎ . We define the inflexion operator by 𝖨𝗇𝖿𝗅𝖾𝗑𝗂𝗈𝗇(𝑎)⃗ ≔ min{𝑖 ∈ [ℎ] : 𝑎𝑝𝑖 = ⊤}. If no such index exists, set 𝖨𝗇𝖿𝗅𝖾𝗑𝗂𝗈𝗇(𝑎)⃗ = ℎ + 1. We also define the stopped path induced by 𝑎⃗ as 𝒫︀(𝑎)⃗ ≔ (𝑝1 , …, 𝑝min{𝖨𝗇𝖿𝗅𝖾𝗑𝗂𝗈𝗇(𝑎),ℎ} ). ⃗ Although defined for any path, throughout this work the path we focus on is the leaf-to-root path containing 𝑥′ . To prevent notation pollution, we use 𝑖⋆ (𝑎)⃗ ≔ 𝖨𝗇𝖿𝗅𝖾𝗑𝗂𝗈𝗇(𝑎)⃗ as short hand for the inflexion operator. Let 𝑎⃗ = (𝑏𝑝1 , …, 𝑏𝑝ℎ ) denote the restriction of the full output 𝑏 ⃗ to the leaf-to-root path involving 𝑥′ , Then ℐ︀Unrelated ≔ {𝑝 ∈ ℋ︀ : 𝑥′ ⪰ 𝑝}

(4.1)

ℐ︀Active ≔ {𝑝1 , …, 𝑝min{𝖨𝗇𝖿𝗅𝖾𝗑𝗂𝗈𝗇(𝑎),ℎ} } ⃗

(4.2)

ℐ︀After ≔ ℋ︀ ∖ (ℐ︀Active ∪ ℐ︀Unrelated )

(4.3)

In Figure 2, the set of nodes in ℐ︀Active is denoted by red dotted lines, ℐ︀Unrelated are marked with green stripes and ℐ︀After is marked in green solid colour. Remark: We draw the readers attention to a seemingly obvious fact, but one that is easily misunderstood when reading the analysis later with all the moving parts. The location of 𝑖⋆ is a function of the output stream restriction 𝑎⃗ only. The internal randomness of Algorithm 1 determines the probability of seeing said output 𝑎,⃗ but the location 𝑖⋆ is determined by the output and the output alone. Now with the above partition defined, we can further classify the nodes in ℐ︀Active using the samples 𝑤⃗ drawn by Algorithm 1.

Differentially Private Hierarchical Heavy Hitters

Definition 3.4.2 (Sets Induced By Random Samples And Output) Let Δ ≥ 1 be as defined in Algorithm 1. Fix any full output vector 𝑏 ⃗ ∈ (⊥, ⊤)|ℋ︀| and path (𝑝1 , …, 𝑝ℎ ) ordered from leaf to root. Let 𝑎⃗ ≔ (𝑏𝑝1 , …, 𝑏𝑝ℎ ) ∈ (⊥, ⊤)ℎ be the restriction of 𝑏 ⃗ to this path. Let 𝒫︀ ≔ 𝒫︀(𝑎)⃗ be the stopped path from Definition 3.4.1. For any vector 𝑤⃗ = (𝑤𝑝 ) ∈ ℝ|𝒫︀| , define the following (overlapping) subsets of 𝒫︀. 𝑝∈𝒫︀

ℐ︀Inflex (𝑎)⃗ ≔ {𝑝 ∈ 𝒫︀ : 𝑎𝑝 = ⊤} ℐ︀Far (𝑤,⃗ 𝑎)⃗ ≔ {𝑝 ∈ 𝒫︀ : 𝑎𝑝 = ⊥ ∧ 𝐹𝑋,𝒮︀ (𝑝) + 𝑤𝑝 < 𝜏 − Δ − 1} ℐ︀Almost (𝑤,⃗ 𝑎)⃗ ≔ {𝑝 ∈ 𝒫︀ : 𝑎𝑝 = ⊥ ∧ 𝐹𝑋,𝒮︀ (𝑝) + 𝑤𝑝 ≥ 𝜏 − 2Δ} We also use the following subsets of ℐ︀Almost (𝑤,⃗ 𝑎). ⃗ ℐ︀Special (𝑤,⃗ 𝑎)⃗ ≔ {𝑝 ∈ ℐ︀Almost (𝑤,⃗ 𝑎)⃗ : 𝜏 − Δ − 1 ≤ 𝐹𝑋,𝒮︀ (𝑝) + 𝑤𝑝 < 𝜏 − Δ} ℐ︀Upper-Almost (𝑤,⃗ 𝑎)⃗ ≔ {𝑝 ∈ ℐ︀Almost (𝑤,⃗ 𝑎)⃗ : 𝐹𝑋,𝒮︀ (𝑝) + 𝑤𝑝 ≥ 𝜏 − Δ} Once again Definition 3.4.2 is defined generally for any leaf to root path, but for our analysis it will always be the path containing 𝑥′ . The nodes from ℐ︀Active can be projected onto the real number line as shown on the right in Figure 2 and that is the picture to think of whenever we write 𝒫︀(𝑎)⃗ downstream. Remark: As mentioned earlier, ℐ︀Active is determined by 𝑎⃗ which is a restriction of the full output 𝑏,⃗ to just the leaf-to-root path starting from leaf that contains 𝑥′ . Once ℐ︀Active is defined the subsequent subsets ℐ︀Far , ℐ︀Special , ℐ︀Upper-Almost together with the inflexion node ℐ︀Inflex partition the stopped path ℐ︀Active ; the first three depend only on the samples 𝑤⃗ (given 𝑎)⃗ and not on the samples 𝑣.⃗ Intuitively, what we are saying is that although ℐ︀Active could have size ℎ, only certain nodes will be “dangerous”, and contribute to our privacy budget. These are the nodes that correspond to queries in ℐ︀Special and ℐ︀Upper-Almost , as these are such that the value of 𝑣 ⃗ could allow us to distinguish between 𝑋 and 𝑋 ′ . As we have 𝑣 ≤ Δ, if a node belongs to ℐ︀Far , then no matter if the node contains 𝑥′ or not, it will always stay below 𝜏 i.e., there is no sampled value of 𝑣 that can help distinguish 𝑋 and 𝑋 ′ . The nodes in ℐ︀Special ∪ ℐ︀Upper-Almost ⊂ ℐ︀Almost are the ones that the privacy adversary can take advantage of, and our privacy budget scales linearly with their size. Thus, we do not want the size of ℐ︀Special or ℐ︀Upper-Almost to be large11. So we define a good event as Definition 3.4.3 (Good Event For A Fixed Output) Let 𝑐0 be as defined in Algorithm 1. Fix any full output vector 𝑏 ⃗ ∈ (⊥, ⊤)|ℋ︀| and path (𝑝1 , …, 𝑝ℎ ) ordered from leaf to root. Let 𝑎⃗ ≔ (𝑏𝑝1 , …, 𝑏𝑝ℎ ) ∈ (⊥, ⊤)ℎ be the restriction of 𝑏 ⃗ to this path. Let 𝒫︀ ≔ 𝒫︀(𝑎)⃗ be the stopped path from Definition 3.4.1. For any vector 𝑤⃗ = (𝑤𝑝 ) ∈ ℝ|𝒫︀| , define the good event 𝑝∈𝒫︀

𝐸(𝑤,⃗ 𝑎)⃗ ≔ 𝟙[|ℐ︀Almost (𝑤,⃗ 𝑎)| ⃗ < 𝑐0 ] where ℐ︀Almost (𝑤,⃗ 𝑎)⃗ is as defined in Definition 3.4.2. Intuitively, what Definition 3.4.3 is conveying is that, if we run Algorithm 1 and get output 𝑎⃗ in the leafto-root path containing 𝑥′ using samples 𝑣 ⃗ and 𝑤,⃗ then the good event is one where 𝑤⃗ and 𝑎⃗ only put a nodes queries in ℐ︀Almost . If this event happens with extremely high likelihood, and we can prove privacy 11

We will be loose in our analysis and upper bound the size ℐ︀Almost instead which may contain a few nodes that are in ℐ︀Far as well. However, we show even ℐ︀Almost is very likely to be small, and this keeps our analysis simpler.

Ari, Cormode, Kanza, Srivastava, Zhou

under this event, then we can bound the other events to have probability mass at most 𝛿. This is what we do subsequently. We show that that good events are extremely likely by upper bounding the reward of the following game in Lemma 3.4.4. Connection with general threshold monitor: The analysis in Appendix A.2 of [28] requires a more complicated game to accommodate 𝑘 > 1 and arbitrary queries. For us, the order and the queries are fixed, and 𝑘 = 1, so this simpler game (and therefore proof) suffices. Lemma 3.4.4 (Coin Flipping Game) Fix ℎ ∈ ℕ. Given inputs 𝛾 ∈ (0, 12 ) and 𝜑 ∈ [ 𝛾4 , 1 − 𝛾] define the following distribution 𝒟︀ over the domain {𝖤𝖭𝖣, 0, 1} where Pr [𝑧 = 0] = 1 − 𝛾 − 𝜑

𝑧←$𝒟︀

Pr [𝑧 = 1] = 𝛾

𝑧←$𝒟︀

Pr [𝑧 = 𝖤𝖭𝖣] = 𝜑

𝑧←$𝒟︀

We sample a sequence of random variables 𝑍1 , 𝑍2 , … i.i.d. from 𝒟︀ and stop at the random time 𝑇 ≔ min(ℎ, min{𝑖 ≥ 1 : 𝑍𝑖 = 𝖤𝖭𝖣}), i.e., as soon as we either observe a 𝖤𝖭𝖣 or reach ℎ samples, whichever comes first. Let 𝑟 ≔ ∑𝑇𝑖=1 𝟙[𝑍𝑖 = 1] be the number of 1’s observed before we stop. Then for every integer 𝑐0 ≥ 1, 𝑐

Pr[𝑟 ≥ 𝑐0 ] ≤ (

𝑐

0 𝛾 4 0 ) ≤( ) 𝛾+𝜑 5

𝛾 Proof. Fix 𝑐0 ≥ 1. Set 𝜌 ≔ 𝛾+𝜑 , and let 𝑝ℎ,𝑐0 be the probability that the game with horizon ℎ yields more than 𝑐0 ones. We prove 𝑝ℎ,𝑐0 ≤ 𝜌𝑐0 by induction on ℎ.

Base (ℎ = 0). No sample is drawn, so 𝑟 = 0 and 𝑝0,𝑐0 = 0 ≤ 𝜌𝑐0 . Step. Fix ℎ ≥ 1 and assume 𝑝ℎ−1,𝑐0 ≤ 𝜌𝑐0 for all 𝑐0 ≥ 1. Condition on the first sample 𝑋1 ; if the game does not stop, the rest is an independent game with horizon ℎ − 1. With probability 𝜑 we draw ⊥ and stop with 𝑟 = 0; with probability 1 − 𝛾 − 𝜑 we draw 0 and still need 𝑐0 ones; with probability 𝛾 we draw 1 and need 𝑐0 − 1 more. Hence 𝑝ℎ,𝑐0 = (1 − 𝛾 − 𝜑)𝑝ℎ−1,𝑐0 + 𝛾𝑝ℎ−1,𝑐0 −1 .

(5)

Here 𝑝ℎ−1,𝑐0 ≤ 𝜌𝑐0 by hypothesis, and 𝑝ℎ−1,𝑐0 −1 ≤ 𝜌𝑐0 −1 as well (using the boundary 𝑝ℎ−1,0 = 1 = 𝜌0 when 𝑐0 = 1). With (𝛾 + 𝜑)𝜌 = 𝛾, 𝑝ℎ,𝑐0 ≤ (1 − 𝛾 − 𝜑)𝜌𝑐0 + 𝛾𝜌𝑐0 −1 = 𝜌𝑐0 −1 ((1 − 𝛾 − 𝜑)𝜌 + 𝛾) = 𝜌𝑐0 .

(6)

𝑐0

𝛾 4 Thus Pr[𝑟 ≥ 𝑐0 ] ≤ 𝜌𝑐0 = ( 𝛾+𝜑 ) , and 𝜑 ≥ 𝛾4 gives 𝛾 + 𝜑 ≥ 5𝛾 4 , hence 𝜌 ≤ 5 and 𝑐

4 0 5 Pr[𝑟 ≥ 𝑐0 ] ≤ ( ) = 𝑒−𝑐0 ln( 4 ) . 5

(7) ⁠ □

Next, we illustrate with Figure 3 why the game in Lemma 3.4.4 is relevant for privacy analysis. As we process nodes (𝑝1 , …, 𝑝𝑖⋆ ) from leaf to root containing 𝑥′ , the game gives us the random variables 𝑍1 , …, 𝑍𝑖⋆ . We treat

Differentially Private Hierarchical Heavy Hitters

the allocation of nodes to regions in Figure 3 by 𝑤 as fixed, and map the action of the random noise 𝑣 to outcomes of the game. If 𝑝𝑖 ∈ ℐ︀Special ∪ ℐ︀Upper-Almost and 𝑣 fails to push the noisy count above 𝜏 i.e., 𝑎𝑝𝑖 = ⊥, then 𝑍𝑖 = 1. Otherwise, if 𝑎𝑝𝑖 = ⊥ and 𝑝𝑖 ∈ ℐ︀Far then 𝑍𝑖 = 0. Finally, we have 𝑍𝑝⋆ = 𝖤𝖭𝖣. What the game is really saying is that it is extremely unlikely we will have many nodes in ℐ︀Almost such that 𝑣 fails to push at least one of them over the threshold of 𝜏 .

Figure 3: The above figure maps the coin flipping game to the events on ℐ︀Active . The crux of the privacy argument simply says that once a node is marked to be in ℐ︀Upper-Almost , the chances of it staying a ⊥ are roughly the same as it becoming a ⊤ once 𝑣 ⃗ is sampled.

Corollary 3.4.4.1 (Good Event Is Extremely Likely) Fix privacy parameters 𝜀 > 0 and 𝛿 ∈ 𝑜( 𝑛1 ), and set 𝑐0 ≔ log 5 1𝛿 . Fix a dataset 𝑋, a full output vector 𝑏 ⃗ ∈ (⊥, ⊤)|ℋ︀| , and a leaf-to-root path (𝑝1 , …, 𝑝ℎ ). 4 Let 𝑎⃗ ≔ (𝑏𝑝1 , …, 𝑏𝑝ℎ ) and 𝒫︀ ≔ 𝒫︀(𝑎)⃗ as defined in Definition 3.4.1. Pr

[𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ∧ ¬𝐸(𝑤,⃗ 𝑎)] ⃗ ≤𝛿

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

Proof. Fix 𝑝 ∈ ℐ︀Active . Mapping the variables of Lemma 3.4.4, we have 𝑍 = 1 corresponds to the event where 𝑝 ∈ ℐ︀Almost . 𝑍 = 0 corresponds to a node being in ℐ︀Far ∖ ℐ︀Almost and 𝑍 = 𝖤𝖭𝖣 corresponds to the event that 𝑝 = 𝑝𝑖∗ . Let 𝑊 = {𝑤 ∈ ℝ : 𝑤 ≥ 𝜏 − 2Δ − 𝐹𝑋,𝒮︀ (𝑝)} and 𝖫𝖺𝗉(6Δ)|𝑊 denote the Laplace distrib ution re-normalised over the set 𝑊 . Similarly, let 𝑣 ←$𝖫𝖺𝗉(1/𝜂)| 𝑣<𝑐 denote the conditional distribution obtained by conditioning that the domain of the Laplace distribution is restricted to values less than some 𝑐 ∈ ℝ. 𝛾≔ = ≤

[𝐹𝑋,𝒮︀ (𝑝) + 𝑤 + 𝑣 < 𝜏 ∧ 𝐹𝑋,𝒮︀ (𝑝) + 𝑤 ≥ 𝜏 − 2Δ]

(8.1)

[𝜏 − 𝐹𝑋,𝒮︀ (𝑝) − 2Δ ≤ 𝑤 < 𝜏 − 𝐹𝑋,𝒮︀ (𝑝) − 𝑣]

(8.2)

[𝑣 < −Δ] +

𝑤←$ 𝖫𝖺𝗉(6Δ) 𝑣←$ 𝖫𝖺𝗉(1/𝜂)

𝑣←$ 𝖫𝖺𝗉(1/𝜂)

𝑤←$ 𝖫𝖺𝗉(6Δ) 𝑣←$𝖫𝖺𝗉(1/𝜂)| 𝑣≥−Δ

[𝜏 − 𝐹𝑋,𝒮︀ (𝑝) − 2Δ ≤ 𝑤 < 𝜏 − 𝐹𝑋,𝒮︀ (𝑝) − 𝑣 | 𝑣 ≥ −Δ] (8.3)

≤

1 + Pr [𝜏 − 𝐹𝑋,𝒮︀ (𝑝) − 2Δ ≤ 𝑤 < 𝜏 − 𝐹𝑋,𝒮︀ (𝑝) − 𝑣 | 𝑣 = −Δ] 4 𝑤←$ 𝖫𝖺𝗉(6Δ)

(8.4)

≤

1 + Pr [𝜏 − 𝐹𝑋,𝒮︀ (𝑝) − 2Δ ≤ 𝑤 < 𝜏 − 𝐹𝑋,𝒮︀ (𝑝) + Δ] 4 𝑤←$ 𝖫𝖺𝗉(6Δ)

(8.5)

≤

1 1 1 + = 4 4 2

(8.6)

In Equation 8.4, as we are in the business of upper bounds, we can remove the randomness over 𝑣 by simply observing that after conditioning over 𝑣 ≥ −Δ, the conditional probability is maximal when we

Ari, Cormode, Kanza, Srivastava, Zhou

fix 𝑣 = −Δ (as this maximizes the possible interval on which sampled 𝑤 can land). Equation 8.6 comes from the fact that 𝑤 ←$ 𝖫𝖺𝗉(6Δ) and Equation 8.5 requires 𝑤 be in an interval of size 3Δ, hence easily upper bounded by 1/4. The bound Pr[𝑣 < −Δ] ≤ 1/4 used above relies on the first quartile of 𝖫𝖺𝗉(1/𝜂): it holds whenever Δ ≥ (ln 2)/𝜂, i.e. for 𝜂 small enough, which is the case in our regime 𝜂 = 𝜀/ log(1/𝛿) with 𝛿 negligible. 𝜑≔ =

[𝐹𝑋,𝒮︀ (𝑝) + 𝑤 + 𝑣 ≥ 𝜏 ∧ 𝐹𝑋,𝒮︀ (𝑝) + 𝑤 ≥ 𝜏 − 2Δ]

[𝐹𝑋,𝒮︀ (𝑝) + 𝑤 ≥ 𝜏 − 2Δ]

𝑤←$ 𝖫𝖺𝗉(6Δ) 𝑣←$ 𝖫𝖺𝗉(1/𝜂)

(9.1)

𝑤←$ 𝖫𝖺𝗉(6Δ)

⋅

≥𝛾⋅ ≥𝛾⋅ ≥𝛾⋅ ⋅

=𝛾⋅

≥𝛾⋅

[𝑤 ≥ 𝜏 − 𝑣 − 𝐹𝑋,𝒮︀ (𝑝) | 𝑤 ≥ 𝜏 − 𝐹𝑋,𝒮︀ (𝑝) − 2Δ]

(9.2)

[𝑤 ≥ 𝜏 − 𝑣 − 𝐹𝑋,𝒮︀ (𝑝) | 𝑤 ≥ 𝜏 − 𝐹𝑋,𝒮︀ (𝑝) − 2Δ]

(9.3)

[𝑤 ≥ 𝜏 − 𝑣 − 𝐹𝑋,𝒮︀ (𝑝) | 𝑝 ∈ ℐ︀Almost ]

(9.4)

1 𝑣←$ 𝖫𝖺𝗉( 𝜂 ) 𝑤←$𝖫𝖺𝗉(6Δ)|𝑊

𝑣←$ 𝖫𝖺𝗉(1/𝜂) 𝑤←$𝖫𝖺𝗉(6Δ)|𝑊

Pr [𝑣 ≥ −Δ | 𝑝 ∈ ℐ︀Almost ]

𝖫𝖺𝗉(1/𝜂)

𝑣←$𝖫𝖺𝗉(1/𝜂)|𝑣≥−Δ 𝑤←$𝖫𝖺𝗉(6Δ)|𝑊

[𝑤 ≥ 𝜏 − 𝑣 − 𝐹𝑋,𝒮︀ (𝑝) | 𝑝 ∈ ℐ︀Almost ∧ 𝑣 ≥ −Δ]

[𝑣 ≥ −Δ] ⋅

𝑣←$ 𝖫𝖺𝗉(1/𝜂)

𝑣←$𝖫𝖺𝗉(1/𝜂)|𝑣≥−Δ 𝑤←$𝖫𝖺𝗉(6Δ)|𝑊

[𝑤 ≥ 𝜏 − 𝑣 − 𝐹𝑋,𝒮︀ (𝑝) | 𝑝 ∈ ℐ︀Almost ∧ 𝑣 ≥ −Δ]

1 ⋅ Pr [𝑤 ≥ 𝜏 − 𝑣 − 𝐹𝑋,𝒮︀ (𝑝) | 𝑝 ∈ ℐ︀Almost ∧ 𝑣 > −Δ] 2 𝑣←$𝖫𝖺𝗉(1/𝜂)|𝑣>−Δ

(9.5)

(9.6)

(9.7)

𝑤←$𝖫𝖺𝗉(6Δ)|𝑊

≥𝛾⋅

1 ⋅ Pr [𝑤 ≥ 𝜏 + Δ − 𝐹𝑋,𝒮︀ (𝑝) | 𝑝 ∈ ℐ︀Almost ∧ 𝑣 = −Δ] 2 𝑤←$𝖫𝖺𝗉(6Δ)|𝑊

(9.8)

≥𝛾⋅

1 1 𝛾 ⋅ = 2 2 4

(9.9)

The last inequality comes from the following analysis. The variable 𝑤 follows 𝖫𝖺𝗉(6Δ) conditioned on 𝑤 ≥ ℓ, where ℓ ≔ 𝜏 − 2Δ − 𝐹𝑋,𝒮︀ (𝑝) is the left endpoint of 𝑊 . Once we fix 𝑣 = −Δ, the target event is {𝑤 ≥ 𝜏 + Δ − 𝐹𝑋,𝒮︀ (𝑝)} = {𝑤 ≥ ℓ + 3Δ}, so the factor equals Pr[𝑤 ≥ ℓ + 3Δ | 𝑤 ≥ ℓ]. As a function of ℓ this is minimised at ℓ ≥ 0, where it equals exactly 𝑒−3Δ/6Δ = 𝑒−0.5 ≈ 0.61 ≥ 1/2; for ℓ < 0 it is only larger. Hence the factor is at least 1/2 for every node, irrespective of 𝐹𝑋,𝒮︀ (𝑝). ⁠ □ Connection to General Threshold monitor: In the general threshold monitor algorithm [28], a good event is more complex. The analysis separately bounds ℐ︀Upper-Almost and ℐ︀Almost , as it is not guaranteed that every query has 𝑓𝑋′ (𝑥′ ) = 1 (since that algorithm deals with arbitrary queries). It defines a good event to be when both the above conditions hold, and this makes the constants worse in the general algorithm. Proving good events are likely is not enough, we also need to show that privacy is preserved under good events. We do this next.

Differentially Private Hierarchical Heavy Hitters

Lemma 3.4.5 (Privacy Conditioned On Good Events) Fix privacy parameters 𝜀 > 0 and 𝛿 ∈ 𝑜( 𝑛1 ), and set 𝜉 ≔ 2𝜂𝑐0 . Fix neighbouring datasets 𝑋 and 𝑋 ′ ≔ 𝑋 ∪ {𝑥′ }. Fix any full output vector 𝑏 ⃗ ∈ (⊥, ⊤)|ℋ︀| and leaf-to-root path (𝑝1 , …, 𝑝ℎ ) containing 𝑥′ . Let 𝑎⃗ ≔ (𝑏𝑝1 , …, 𝑏𝑝ℎ ) and 𝒫︀ ≔ 𝒫︀(𝑎). ⃗ For every vector 𝑢⃗ = (𝑢𝑝 )

𝑝∈𝒫︀

∈ ℝ|𝒫︀| satisfying 𝐸(𝑢,⃗ 𝑎), ⃗ define 𝑢′⃗ = (𝑢′𝑝 )

𝑝∈𝒫︀

coordinate-wise by

𝑢 − 1 if 𝑎𝑝 = ⊤ 𝑢′𝑝 ≔ { 𝑝 𝑢𝑝 otherwise Then Pr

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

[𝐴(𝑋 ′ ; 𝑢′⃗ , 𝑣)⃗ = 𝑎𝒫︀ ⃗ ]≤ 𝒫︀

[𝐴(𝑋; 𝑢,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ] ≤ 𝑒𝜉

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

[𝐴(𝑋 ′ ; 𝑢,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ].

Proof. As 𝑢⃗ and 𝑎⃗ are fixed, we also get our sets ℐ︀Almost , ℐ︀Far , ℐ︀Special and ℐ︀Upper-Almost as defined in Definition 3.4.2. Observe that Pr

[𝐴(𝑋; 𝑢,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ]=

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

[𝐹𝑋,𝒮︀ (𝑝𝑖⋆ ) + 𝑢𝑖⋆ + 𝑣𝑝𝑖⋆ ≥ 𝜏 ]

𝑣𝑝 ⋆ ←$ 𝖫𝖺𝗉(1/𝜂) 𝑖

⋅ ∏

𝑝∈ℐ︀Far

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

⋅

∏

[𝐹𝑋,𝒮︀ (𝑝) + 𝑢𝑝 + 𝑣𝑝 = ⊥] Pr

𝑝∈ℐ︀Upper-Almost ∪ℐ︀Special

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

(10.1)

[𝐹𝑋,𝒮︀ (𝑝) + 𝑢𝑝 + 𝑣𝑝 = ⊥]

The products in Equation 10.1 comes from the fact that given 𝒫︀ each output along the path is decided independently of the others. Upper Bound: We will bound each product term individually. Inflexion Point. Now as 𝐹𝑋′ ,𝒮︀′ (𝑝𝑖⋆ ) > 𝐹𝑋,𝒮︀ (𝑝𝑖⋆ ) the following is immediately true Pr

[𝐹𝑋,𝒮︀ (𝑝𝑖⋆ ) + 𝑢𝑖⋆ + 𝑣𝑝𝑖⋆ ≥ 𝜏 ] ≤

𝑣𝑝 ⋆ ←$ 𝖫𝖺𝗉(1/𝜂) 𝑖

𝑣𝑝 ⋆ ←$ 𝖫𝖺𝗉(1/𝜂)

[𝐹𝑋′ ,𝒮︀′ (𝑝𝑖⋆ ) + 𝑢𝑖⋆ + 𝑣𝑝𝑖⋆ ≥ 𝜏 ]

(11)

𝑖

Far nodes. Observe that as 𝑣𝑝 ≤ Δ, for all 𝑝 ∈ ℐ︀Far , Pr

[𝐹𝑋,𝒮︀ (𝑝) + 𝑢𝑝 + 𝑣𝑝 = ⊥] =

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

[𝐹𝑋′ ,𝒮︀′ (𝑝) + 𝑢𝑝 + 𝑣𝑝 = ⊥] = 1

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

(12)

Upper Almost nodes. For any 𝑝 ∈ ℐ︀Upper-Almost , we have 𝐹𝑋,𝒮︀ (𝑝) + 𝑢𝑝 ≥ 𝜏 − Δ, so for Pr𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂) [𝐹𝑋,𝒮︀ (𝑝) + 𝑢𝑝 + 𝑣𝑝 = ⊥] > 0 we need 𝑣𝑝 ≤ 𝜏 − (𝐹𝑋,𝒮︀ (𝑝) + 𝑢𝑝 ) ≤ Δ

(13)

Using that Pr𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂) [𝑣𝑝 < 𝑐] ≤ 𝑒𝜂 Pr𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂) [𝑣𝑝 < 𝑐 − 1] for any 𝑐 (shifting the threshold by the sensitivity 1), this gives us Pr

[𝐹𝑋,𝒮︀ (𝑝) + 𝑢𝑝 + 𝑣𝑝 = ⊥] =

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

[𝑣𝑝 < 𝜏 − (𝐹𝑋,𝒮︀ (𝑝) + 𝑢𝑝 )]

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

≤ 𝑒𝜂

[𝑣𝑝 < 𝜏 − (𝐹𝑋,𝒮︀ (𝑝) + 𝑢𝑝 ) − 1]

(14.2)

[𝐹𝑋′ ,𝒮︀′ (𝑝) + 𝑢𝑝 + 𝑣𝑝 < 𝜏 ]

(14.3)

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

= 𝑒𝜂 ⋅

(14.1)

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

Ari, Cormode, Kanza, Srivastava, Zhou

≤ 𝑒𝜂 ⋅

[𝐹𝑋′ ,𝒮︀′ (𝑝) + 𝑢𝑝 + 𝑣𝑝 < 𝜏 ]

(14.4)

[𝐹𝑋′ ,𝒮︀′ (𝑝) + 𝑢𝑝 + 𝑣𝑝 < 𝜏 ]

(14.5)

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

≤ 𝑒2𝜂 ⋅

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

Special nodes. The special nodes bridge between the far and upper-almost nodes, and so require a slightly different treatment. It is the key part of the proof that depends on the value of 𝜂. For any 𝑝 ∈ ℐ︀Special , as 𝜂 ≔ log(𝜀 1 ) ∈ (0, 1) (since 𝛿 is cryptographically negligible and 𝜀 is a small real constant) 𝛿

[𝐹𝑋,𝒮︀ (𝑝) + 𝑢𝑝 + 𝑣𝑝 = ⊥] ≤ 1

(15.1)

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

𝜂 ≤ 𝑒𝜂 (1 − ) 2 ≤ 𝑒𝜂 ≤ 𝑒𝜂

(15.2)

[𝑣𝑝 < Δ]

(15.3)

[𝐹𝑋,𝒮︀ (𝑝) + 𝑢𝑝 + 𝑣𝑝 < 𝜏 ]

(15.4)

[𝐹𝑋′ ,𝒮︀′ (𝑝) + 𝑢𝑝 + 𝑣𝑝 < 𝜏 ]

(15.5)

[𝐹𝑋′ ,𝒮︀′ (𝑝) + 𝑢𝑝 + 𝑣𝑝 < 𝜏 ]

(15.6)

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂) 𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

≤ 𝑒2𝜂 ≤ 𝑒2𝜂

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂) 𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

Equation 15.2 follows from the fact that for any 𝜂 ∈ (0, 1), we have 𝑒𝜂 (1 − 𝜂2 ) > 1. Equation 15.3 comes from the fact that Δ ≔ 𝜂1 log( 𝜂1 ), and by tail bounds we have Pr𝑣𝑖 ←$ 𝖫𝖺𝗉(1/𝜂) [𝑣𝑖 ≥ Δ] ≤ 𝜂2 . We have handled all four types of nodes that appear in Equation 10.1. Combining them all [𝐴(𝑋; 𝑢,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ] ≤ 𝑒2𝜂 |ℐ︀Upper-Almost ∪ℐ︀Special |

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

≤ 𝑒2𝜂 |ℐ︀Almost | ≤ 𝑒2𝜂𝑐0

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

[𝐴(𝑋 ′ ; 𝑢,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ]

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

[𝐴(𝑋 ′ ; 𝑢,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ]

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

(16.1) (16.2) (16.3)

Equation 16.3 comes from our assumption that 𝐸(𝑢,⃗ 𝑎)⃗ = 1, and this completes our proof of the upper bound. Lower Bound: The lower bound is noticeably simpler. For the inflexion node 𝑝⋆ we have, [𝐹𝑋′ ,𝒮︀′ (𝑝𝑖⋆ ) + 𝑢′𝑖⋆ + 𝑣𝑝𝑖⋆ ≥ 𝜏 ] =

𝑣𝑝 ⋆ ←$ 𝖫𝖺𝗉(1/𝜂) 𝑖

[𝐹𝑋′ ,𝒮︀′ (𝑝𝑖⋆ ) + 𝑢𝑖⋆ − 1 + 𝑣𝑝𝑖⋆ ≥ 𝜏 ]

(17.1)

[𝐹𝑋,𝒮︀ (𝑝𝑖⋆ ) + 𝑢𝑖⋆ + 𝑣𝑝𝑖⋆ ≥ 𝜏 ]

(17.2)

𝑣𝑝 ⋆ ←$ 𝖫𝖺𝗉(1/𝜂) 𝑖

For 𝑝 ∈ (ℐ︀Far ∪ ℐ︀Upper-Almost ∪ ℐ︀Special ), we have (deterministically) 𝑎𝑝 = ⊥ so 𝑢′𝑝 = 𝑢𝑝 , and Pr

[𝐹𝑋′ ,𝒮︀′ (𝑝) + 𝑢′𝑝 + 𝑣𝑝 < 𝜏 ] =

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

≤

[𝐹𝑋,𝒮︀ (𝑝) + 1 + 𝑢𝑝 + 𝑣𝑝 < 𝜏 ]

(18.1)

[𝐹𝑋,𝒮︀ (𝑝) + 𝑢𝑝 + 𝑣𝑝 < 𝜏 ]

(18.2)

[𝐴(𝑋; 𝑢,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ]

(19)

𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂) 𝑣𝑝 ←$ 𝖫𝖺𝗉(1/𝜂)

Putting all these together, we can conclude, Pr

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

[𝐴(𝑋 ′ ; 𝑢′⃗ , 𝑣)⃗ = 𝑎𝒫︀ ⃗ ]≤ 𝒫︀

This completes the proof. 18

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

Differentially Private Hierarchical Heavy Hitters

⁠ □

3.5 Release On ℐ︀Active is private We have already shown that if restricted to nodes in ℐ︀Active , and conditioning on good events, we have 𝜉 -privacy. Now we remove the conditioning, and prove that the release is (𝜉, 𝛿) private, still restricting to nodes in ℐ︀Active . Once this is done, the full privacy over the entire output will immediately follow and is given in Section 3.6. Lemma 3.5.1 (Privacy Upper Bound) Fix privacy parameters 𝜀 > 0 and 𝛿 ∈ 𝑜( 𝑛1 ), and set 𝜉 ≔ 2𝜂𝑐0 . Fix neighbouring datasets 𝑋 and 𝑋 ′ ≔ 𝑋 ∪ {𝑥′ }. Fix any full output vector 𝑏 ⃗ ∈ (⊥, ⊤)|ℋ︀| and leaf-to-root path (𝑝1 , …, 𝑝ℎ ) containing 𝑥′ . Let 𝑎⃗ ≔ (𝑏𝑝1 , …, 𝑏𝑝ℎ ) and 𝒫︀ ≔ 𝒫︀(𝑎). ⃗ [𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ] ≤ 𝑒𝜉

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

[𝐴(𝑋 ′ ; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ]+𝛿

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

Proof. The noise samples on 𝒫︀ are drawn independently of the data, with 𝑤⃗ ←$ 𝖫𝖺𝗉(6Δ) and 𝑣 ⃗ ← $ 𝖫𝖺𝗉(1/𝜂) i.i.d. per node. For fixed stopped path 𝒫︀ and output 𝑎 ⃗ we have Pr

[𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ]=

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

+ ≤

[𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ∧ 𝐸(𝑤,⃗ 𝑎)] ⃗

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

(20.1)

[𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ∧ ¬𝐸(𝑤,⃗ 𝑎)] ⃗

[𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ∧ 𝐸(𝑤,⃗ 𝑎)] ⃗ +𝛿

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

(20.2)

Equation 20.2 comes by applying Corollary 3.4.4.1. Since 𝐸(𝑤,⃗ 𝑎)⃗ is determined by 𝑤⃗ and the fixed output vector 𝑎,⃗ we can expand the good-event term by conditioning only on the 𝑤-samples: 𝐸(𝑢,⃗ 𝑎). ⃗ Since 𝑤⃗ is continuous, let 𝑓𝑤⃗ denote the density of 𝑤⃗ ←$𝖫𝖺𝗉(6Δ)⊗ |𝒫︀| . Then Pr

[𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ∧ 𝐸(𝑤,⃗ 𝑎)] ⃗

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

=∫

𝑓𝑤⃗ (𝑢)⃗ ⋅

𝑢∈ℝ ⃗ |𝒫︀| :𝐸(𝑢,⃗ 𝑎)⃗

𝑓𝑤⃗ (𝑢)⃗ ⋅ 𝑒𝜉

≤∫ 𝑢∈ℝ ⃗ |𝒫︀| :𝐸(𝑢,⃗ 𝑎)⃗

≤ 𝑒𝜉 ∫

𝑓𝑤⃗ (𝑢)⃗ ⋅

𝑢∈ℝ ⃗ |𝒫︀|

= 𝑒𝜉

[𝐴(𝑋; 𝑢,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ] d𝑢⃗

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

[𝐴(𝑋 ′ ; 𝑢,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ] d𝑢⃗

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

[𝐴(𝑋 ′ ; 𝑢,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ] d𝑢⃗

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

[𝐴(𝑋 ′ ; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ].

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

(21.1)

(21.2) (21.3) (21.4) (21.5)

The first step conditions on 𝑤⃗ = 𝑢⃗ (with 𝑣 ⃗ independent), the second applies Lemma 3.4.5 on 𝐸(𝑢,⃗ 𝑎), ⃗ and the third extends the region to all 𝑢.⃗ ⁠ □

Ari, Cormode, Kanza, Srivastava, Zhou

Lemma 3.5.2 (Privacy Lower Bound) Fix privacy parameters 𝜀 > 0 and 𝛿 ∈ 𝑜( 𝑛1 ), and set 𝜉 ≔ 2𝜂𝑐0 . Fix neighbouring datasets 𝑋 and 𝑋 ′ ≔ 𝑋 ∪ {𝑥′ }. Fix any full output vector 𝑏 ⃗ ∈ (⊥, ⊤)|ℋ︀| and leaf-to-root path (𝑝1 , …, 𝑝ℎ ) containing 𝑥′ . Let 𝑎⃗ ≔ (𝑏𝑝1 , …, 𝑏𝑝ℎ ) and 𝒫︀ ≔ 𝒫︀(𝑎). ⃗ 𝑒−𝜉

[𝐴(𝑋 ′ ; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ]−𝛿

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) ⃗ $ 𝖫𝖺𝗉(1/𝜂) ( 𝑣←

≤ )

[𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ]

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

Proof. The noise samples on 𝒫︀ are drawn independently of the data, with 𝑤⃗ ←$ 𝖫𝖺𝗉(6Δ) and 𝑣 ⃗ ← |𝒫︀| $ 𝖫𝖺𝗉(1/𝜂) i.i.d. per node. Let 𝑢⃗ ∈ ℝ be a vector such that 𝐸(𝑢,⃗ 𝑎)⃗ holds. Let 𝑢⃗′ ∈ ℝ|𝒫︀| be as defined in Lemma 3.4.5 where 𝑢 − 1 if 𝑎𝑝 = ⊤ 𝑢′𝑝 ≔ { 𝑝 𝑢𝑝 otherwise

(22)

Let 𝑓𝑤⃗ denote the joint density of 𝑤⃗ ←$𝖫𝖺𝗉(6Δ)⊗ |𝒫︀| and 𝑓𝑤𝑝 the density of each coordinate 𝑤𝑝 ← $ 𝖫𝖺𝗉(6Δ). Then, 𝑓𝑤⃗ (𝑢)⃗ = 𝑓𝑤𝑝⋆ (𝑢𝑝⋆ )

∏

𝑓𝑤𝑝 (𝑢𝑝 )

(23.1)

𝑓𝑤𝑝 (𝑢′𝑝 )

(23.2)

𝑝∈ℐ︀Far ∪ℐ︀Almost

= 𝑓𝑤𝑝⋆ (𝑢𝑝⋆ )

∏ 𝑝∈ℐ︀Far ∪ℐ︀Almost

≥ 𝑒− 6Δ 𝑓𝑤𝑝⋆ (𝑢′𝑝⋆ )

𝑓𝑤𝑝 (𝑢′𝑝 )

∏

(23.3)

𝑝∈ℐ︀Far ∪ℐ︀Almost

= 𝑒− 6Δ 𝑓𝑤⃗ (𝑢⃗′ )

(23.4)

≥ 𝑒−𝜉 𝑓𝑤⃗ (𝑢⃗′ )

(23.5)

The last inequality is due to 𝜉 = 2𝜂𝑐0 = 2𝜀/ log(5/4) (as 𝜂 = 𝜀/ log(1/𝛿), 𝑐0 = log 5 (1/𝛿)). Since 𝜂 = 4 𝜀/ log(1/𝛿) ≤ min(𝜀, 1/𝑒) for 𝛿 ∈ 𝑜(1/𝑛), 1/(6Δ) = 𝜂/(6 log(1/𝜂)) ≤ 𝜂/6 ≤ 𝜀/6 ≤ 2𝜀/ log(5/4) = 𝜉. Pr

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

[𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ]≥

[𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ∧ 𝐸(𝑤,⃗ 𝑎)] ⃗

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

=∫

𝑓𝑤⃗ (𝑢)⃗ ⋅

𝑢∈ℝ ⃗ |𝒫︀| :𝐸(𝑢,⃗ 𝑎)⃗

≥ 𝑒−𝜉 ∫

𝑓𝑤⃗ (𝑢⃗′ ) ⋅

𝑢∈ℝ ⃗ |𝒫︀| :𝐸(𝑢,⃗ 𝑎)⃗

= 𝑒−𝜉 ∫

≥ 𝑒−𝜉

[𝐴(𝑋; 𝑢,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ] d𝑢⃗ [𝐴(𝑋 ′ ; 𝑢⃗′ , 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ] d𝑢⃗

[𝐴(𝑋 ′ ; 𝑢⃗′ , 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ] d𝑢′⃗ (24.4)

[𝐴(𝑋 ′ ; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ∧ 𝐸(𝑤,⃗ 𝑎)] ⃗

(24.3)

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

(24.2)

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

𝑓𝑤⃗ (𝑢⃗′ ) ⋅

𝑢⃗ ′ ∈ℝ|𝒫︀| :𝐸(𝑢⃗ ′ ,𝑎)⃗

= 𝑒−𝜉

𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

(24.1)

(24.5)

Differentially Private Hierarchical Heavy Hitters

+𝑒−𝜉

≥ 𝑒−𝜉

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) ⃗ $ 𝖫𝖺𝗉(1/𝜂) ( 𝑣←

[𝐴(𝑋 ′ ; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ∧ 𝐸(𝑤,⃗ 𝑎)] ⃗ −𝛿

(24.6) )

[𝐴(𝑋 ′ ; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ ⃗ ]−𝛿

(24.7) )

Equation 24.3 comes from Equation 23.5 and the lower bound in Lemma 3.4.5. Equation 24.4 is justified because 𝐸(𝑢,⃗ 𝑎)⃗ = 𝐸(𝑢⃗′ , 𝑎): ⃗ since 𝑢⃗ and 𝑢⃗′ differ only at the inflexion node 𝑝⋆ (never in ℐ︀Almost , as 𝑎𝑝⋆ = ⊤), we have ℐ︀Almost (𝑢,⃗ 𝑎)⃗ = ℐ︀Almost (𝑢⃗′ , 𝑎), ⃗ so the translation 𝑢⃗ ↦ 𝑢⃗′ maps the region onto itself. Equation 24.6 ′ uses Pr𝑤← ⃗ ∧ 𝐸(𝑤,⃗ 𝑎)] ⃗ ≤ 𝛿. Although 𝐸 is the 𝑋-based good event, 𝐹𝑋′ ,𝒮︀′ (𝑝) = ⃗ $ 𝖫𝖺𝗉(6Δ) [𝐴(𝑋 ; 𝑤,⃗ 𝑣)⃗ 𝒫︀ = 𝑎𝒫︀ 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

𝐹𝑋,𝒮︀ (𝑝) + 1 on the path, so every node of ℐ︀Almost under 𝑋 remains in ℐ︀Almost under 𝑋 ′ ; hence the bad event 𝐸 is only more likely under 𝑋 ′ , and Corollary 3.4.4.1 applied to 𝑋 ′ bounds it by 𝛿. ⁠ □

3.6 The Full Proof Of Privacy Now we have all the tools needed for the full privacy proof. Theorem 3.6.1 (Privacy) Algorithm 1 is (2𝜉, 2𝛿)-DP. Proof. Fix datasets 𝑋 and 𝑋 ′ ≔ 𝑋 ∪ {𝑥′ }. We can safely assume that 𝑓𝑋 (𝑝) ≠ 1 for all 𝑥′ ⪰ 𝑝 by the stability histograms argument. In more detail, fix any such node 𝑝. There can be at most ℎ such isolated nodes. As 𝐹𝑋,𝒮︀ (𝑝) = 0, the algorithm never considers its release. However, 𝐹𝑋′ ,𝒮︀′ (𝑝) = 1 so the algorithm considers release. The adversary distinguish 𝑋 from 𝑋 ′ , only if 𝐹𝑋′ ,𝒮︀′ (𝑝) + 𝑤𝑝 + 𝑣𝑝 ≥ 𝜏 , equivalently 𝑤𝑝 + 𝑣𝑝 ≥ 𝜏 − 1. Using 𝑣𝑝 ≤ Δ after clipping and 𝑤𝑝 ←$ 𝖫𝖺𝗉(6Δ), a Laplace tail bound gives Pr

[𝑤𝑝 + Δ ≥ 𝜏 − 1] ≤

𝑤𝑝 ←$ 𝖫𝖺𝗉(6Δ)

𝛿 ℎ

(25)

with room to spare, where the inequality comes from threshold guard of Algorithm 1 forces 𝜏 = Ω(Δ log(ℎ/𝛿)). A union bound over the at most ℎ isolated nodes gives us that with probability at most 𝛿 the output is not private. From here on we can safely assume that 𝑥′ is never the only contributor the residual frequence of any node 𝑝. Fix output 𝑎⃗ ≔ (𝑎𝑝 ) where each coordinate is either ⊥ or ⊤. Let (𝑝1 , …, 𝑝ℎ ) be the leaf-to-root 𝑝∈ℋ︀

path of 𝑥′ ordered from leaf to root, and let 𝑎𝑥⃗ ′ ≔ (𝑎𝑝1 , …, 𝑎𝑝ℎ ) be the restriction of 𝑎⃗ to this path (shown in colour in Figure 2 in the dotted block). Let 𝑖⋆ ≔ 𝑖⋆ (𝑎𝑥⃗ ′ ) and define the stopped path ℐ︀Active ≔ 𝒫︀(𝑎𝑥⃗ ′ ).

(26)

′ Define 𝑀 ≔ |ℋ︀|. Let (𝛽1 , …, 𝛽𝑀 ) ←$𝐴(𝑋) and (𝛽1′ , …, 𝛽𝑀 ) ←$𝐴(𝑋 ′ ) be the output of Algorithm 1 on ′ inputs 𝑋 and 𝑋 respectively with randomness over the samples (𝑤,⃗ 𝑣)⃗ ∈ ℝ𝑀 . Now for this fixed 𝑏,⃗ we use the three sets ℐ︀Unrelated , ℐ︀Active , ℐ︀After as described by Figure 2.

Let ℛ︀ ≔ ℋ︀ \ ℐ︀Unrelated = ℐ︀Active ∪ ℐ︀After . By Bayes rule, we have Pr[𝛽 ⃗ = 𝑎]⃗ = Pr[𝛽ℐ︀⃗ Unrelated = 𝑎ℐ︀⃗ Unrelated ] ⋅ Pr[𝛽ℛ︀⃗ = 𝑎ℛ︀ ⃗ | 𝛽ℐ︀⃗ Unrelated = 𝑎ℐ︀⃗ Unrelated ]

(27.1)

Ari, Cormode, Kanza, Srivastava, Zhou

Focusing on the left hand term of the product in Equation 27.1, we need only consider 𝑝 ∈ ℐ︀Unrelated . As the algorithm proceeds bottom up, we have for any 𝑝 ∈ ℐ︀Unrelated , ⃗ Pr[𝛽𝑝 = 𝑎𝑝 ∧ 𝛽𝖲𝗎𝖼𝖼(𝑝) = 𝑎𝖲𝗎𝖼𝖼(𝑝) ⃗ ] ⃗ ⃗ = Pr[𝛽𝑝 = 𝑎𝑝 | 𝛽𝖲𝗎𝖼𝖼(𝑝) = 𝑎𝖲𝗎𝖼𝖼(𝑝) ⃗ ] ⋅ Pr[𝛽𝖲𝗎𝖼𝖼(𝑝) = 𝑎𝖲𝗎𝖼𝖼(𝑝) ⃗ ].

(28.1)

The corresponding local factor is the same under 𝑋 ′ : ⃗ Pr[𝛽𝑝 = 𝑎𝑝 | 𝛽𝖲𝗎𝖼𝖼(𝑝) = 𝑎𝖲𝗎𝖼𝖼(𝑝) ⃗ ] = Pr[𝛽𝑝′ = 𝑎𝑝 | 𝛽⃗′ 𝖲𝗎𝖼𝖼(𝑝) = 𝑎𝖲𝗎𝖼𝖼(𝑝) ⃗ ].

(29.1)

⃗ To justify Equation 29.1, condition on the event 𝛽𝖲𝗎𝖼𝖼(𝑝) = 𝑎𝖲𝗎𝖼𝖼(𝑝) ⃗ . This fixes exactly which alreadyprocessed successors of 𝑝 have been selected into 𝒮︀, namely those 𝑞 ∈ 𝖲𝗎𝖼𝖼(𝑝) with 𝑎𝑞 = ⊤. Therefore the threshold test at 𝑝 is determined by the same fresh noise (𝑤𝑝 , 𝑣𝑝 ) and by the residual count of 𝑝 after removing this fixed set of selected successors. As the unconditional count of 𝑝 is the same under 𝑋 and 𝑋 ′ , the probabilities are equal. For brevity of notation define the two unrelated-output events 𝑋 𝐸Unrel ≔ {𝛽ℐ︀⃗ Unrelated = 𝑎ℐ︀⃗ Unrelated }

(30.1)

𝑋′ 𝐸Unrel ≔ {𝛽⃗′ ℐ︀

(30.2)

Unrelated

= 𝑎ℐ︀⃗ Unrelated }.

Applying Equation 29.1 bottom up through the hierarchy over ℐ︀Unrelated gives ′

𝑋 𝑋 Pr[𝐸Unrel ] = Pr[𝐸Unrel ]

(31.1)

Thus, to prove the theorem it suffices to show that 𝑋′ 𝑋 𝑋′ 𝑒−𝜉 (Pr[𝛽⃗′ ℛ︀ = 𝑎ℛ︀ ⃗ | 𝐸Unrel ] − 𝛿) ≤ Pr[𝛽ℛ︀⃗ = 𝑎ℛ︀ ⃗ | 𝐸Unrel ] ≤ 𝑒𝜉 Pr[𝛽⃗′ ℛ︀ = 𝑎ℛ︀ ⃗ | 𝐸Unrel ]+𝛿

(32.1)

Now by Bayes rule and the structure of ℋ︀, we have 𝑋 𝑋 𝑋 Pr[𝛽ℛ︀⃗ = 𝑎ℛ︀ ⃗ | 𝐸Unrel ] = Pr[𝛽ℐ︀⃗ After = 𝑎ℐ︀⃗ After | 𝐸Unrel ∧ 𝛽ℐ︀⃗ Active = 𝑎ℐ︀⃗ Active ] Pr[𝛽ℐ︀⃗ Active = 𝑎ℐ︀⃗ Active | 𝐸Unrel ] (33)

Notice that 𝑎⃗ defines 𝒮︀, and given the unrelated-output event and the decomposition above, we have 𝑋 Pr[𝛽ℐ︀⃗ After = 𝑎ℐ︀⃗ After | 𝐸Unrel ∧ 𝛽ℐ︀⃗ Active = 𝑎ℐ︀⃗ Active ] = Pr[𝛽⃗′ ℐ︀

After

𝑋′ = 𝑎ℐ︀⃗ After | 𝐸Unrel ∧ 𝛽⃗′ ℐ︀

Active

= 𝑎ℐ︀⃗ Active ]

(34)

as the contribution of 𝑥′ has been removed in the residual counts. Thus to prove Equation 32.1 it suffices to show 𝑒−𝜉 (Pr[𝛽⃗′ ℐ︀

Active

𝑋′ 𝑋 = 𝑎ℐ︀⃗ Active | 𝐸Unrel ] − 𝛿) ≤ Pr[𝛽ℐ︀⃗ Active = 𝑎ℐ︀⃗ Active |𝐸Unrel ]

≤ 𝑒𝜉 Pr[𝛽⃗′ ℐ︀

Active

′

𝑋 = 𝑎ℐ︀⃗ Active | 𝐸Unrel ]+𝛿 ′

(35.1)

𝑋 𝑋 For the upper inequality in Equation 35.1, first observe that conditioning on 𝐸Unrel or 𝐸Unrel fixes the same unrelated output 𝑎ℐ︀⃗ Unrelated , hence fixes which unrelated successors have already been selected into 𝒮︀. Given this fixed unrelated output, the residuals on ℐ︀Active are fixed functions of the data, and the remaining randomness on ℐ︀Active is independent of the randomness used on ℐ︀Unrelated . Thus, conditioning on this event plays no further role in the privacy analysis (we can pretend it was never there). For the fixed stopped path ℐ︀Active , the fresh noise on ℐ︀Active is drawn independently of the data, with 𝑤⃗ ←$ 𝖫𝖺𝗉(6Δ) and 𝑣 ⃗ ←$ 𝖫𝖺𝗉(1/𝜂) i.i.d. per node. Now apply Lemma 3.5.1 to the leaf-to-root path (𝑝1 , …, 𝑝ℎ ) with the

Differentially Private Hierarchical Heavy Hitters

full output vector equal to the fixed output 𝑎.⃗ The stopped path 𝒫︀ in Lemma 3.5.1 is exactly ℐ︀Active , so the upper bound follows. Although Lemma 3.5.1 uses the left hand side of the equations below, in its theorem statement, we are really proving a fact about the conditional here when we apply the lemma. The reason we don’t introduce the notation, is because it plays no role in the privacy analysis, and hence we do not pollute the analysis with unnecessary notation. Pr

𝑋 [𝐴(𝑋; 𝑤,⃗ 𝑣)⃗ ℐ︀Active = 𝑎ℐ︀⃗ Active ] ≔ Pr[𝛽ℐ︀⃗ Active = 𝑎ℐ︀⃗ Active | 𝐸Unrel ]

[𝐴(𝑋 ′ ; 𝑤,⃗ 𝑣)⃗ ℐ︀

𝑤← ⃗ $ 𝖫𝖺𝗉(6Δ) 𝑣← ⃗ $ 𝖫𝖺𝗉(1/𝜂)

Active

= 𝑎ℐ︀⃗ Active ] ≔ Pr[𝛽⃗′ ℐ︀

Active

′

𝑋 = 𝑎ℐ︀⃗ Active | 𝐸Unrel ]

(36.1)

(36.2)

The matching lower inequality will follow analogously from Lemma 3.5.2.

⁠ □

Theorem 3.6.2 (Coverage And Error) Let 𝒮︀ denote the set of hierarchical heavy hitters selected by Algorithm 1, and for any 𝑝 ∈ ℋ︀ let 𝑓̃𝑋 (𝑝) ≔ ∑𝑞∈𝒮︀∧𝑞⪰𝑝 𝐹̃𝑋,𝒮︀ (𝑞) be the estimate of its unconditional frequency reconstructed from the released residual counts, with 𝑐𝑝 ≔ |{𝑞 ∈ 𝒮︀ : 𝑞 ⪰ 𝑝}|. Set 𝛼 = Ω(

log( 1𝛿 ) log( 1𝛿 ) 1 ℎ ⋅ log( ) ⋅ (log[ ] + log[ ])) 𝜀 𝜀 𝛿 𝛽

Then, with probability 1 − 𝛽: 1. (Coverage) every 𝑝 ∈ 𝒮︀ has 𝐹𝒮︀ (𝑝) ≥ 𝜏 − 𝛼, and every 𝑝 ∉ 𝒮︀ has 𝐹𝒮︀ (𝑝) ≤ 𝜏 + 𝛼. 2. (Relative error) every 𝑝 ∈ 𝒮︀ has 𝑓 (𝑝) − 𝑓̃𝑋 (𝑝) 2𝛼 | 𝑋 |≤ 𝑓𝑋 (𝑝) 𝜏 and every 𝑝 ∉ 𝒮︀ has 𝑓 (𝑝) − 𝑓̃𝑋 (𝑝) 1 2𝛼 | 𝑋 |≤ + 𝑓𝑋 (𝑝) 𝑐𝑝 + 1 𝜏 Proof. The analysis for coverage and error follows from the tail bounds of the Laplace distribution and the union bound. Coverage: We give exact answers for any node 𝑝 with 𝐹𝑋,𝒮︀ (𝑝) = 𝐹̃𝑋,𝒮︀ (𝑝) = 0 (by stability histograms). For each level of the tree we have at most 2𝑛 Laplace variables: the two samples 𝑤𝑝 ←$ 𝖫𝖺𝗉(6Δ) and 𝑣𝑝 ← 1 1 1 1 1 $ 𝖫𝖺𝗉( 𝜂 ) drawn per node. Since Δ = 𝜂 log( 𝜂 ) ≥ 𝜂 , we have 𝜂 ≤ 6Δ, so the tail of 𝑣𝑝 is dominated by 𝑡 that of 𝑤𝑝 , namely Pr𝑣 ←$ 𝖫𝖺𝗉( 1 ) [|𝑣𝑝 | > 𝑡] = 𝑒−𝜂𝑡 ≤ 𝑒− 6Δ ; we may therefore treat both as 𝖫𝖺𝗉(6Δ) samples. 𝑝

𝜂

Clipping only decreases magnitude, so |𝑣𝑝 | ≤ |𝑣𝑝 |. Taking the union bound over all 2𝑛 samples at a level with total failure probability ℎ𝛽 , with probability 1 − ℎ𝛽 every node satisfies |𝑤𝑝 |, |𝑣𝑝 | ≤ 6Δ log( 2𝑛ℎ 𝛽 ), hence |𝑤𝑝 + 𝑣𝑝 | ≤ |𝑤𝑝 | + |𝑣𝑝 | ≤ 12Δ log(

2𝑛ℎ 𝑛ℎ ) = 𝑂(Δ log( )) 𝛽 𝛽

ℎ Since 𝛿 = 𝗇𝖾𝗀𝗅(𝑛) gives 𝑛 ≤ 1𝛿 , this is at most 𝑂(Δ log( 𝛿𝛽 )) = 𝑂(Δ(log[ 1𝛿 ] + log[ ℎ𝛽 ])). So if we set

(37)

Ari, Cormode, Kanza, Srivastava, Zhou

1 ℎ 𝛼 = Ω(Δ(log[ ] + log[ ])) 𝛿 𝛽 1 1 1 ℎ = Ω( log( )(log[ ] + log[ ])) 𝜂 𝜂 𝛿 𝛽 = Ω(

log( 1𝛿 ) log( 1𝛿 ) 1 ℎ ⋅ log( ) ⋅ (log[ ] + log[ ])), 𝜀 𝜀 𝛿 𝛽

(38.1) (38.2) (38.3)

then taking the union bound over the ℎ levels of the tree, with probability 1 − 𝛽 the per-node DP noise satisfies |𝑤𝑝 + 𝑣𝑝 | ≤ 𝛼 for every node. Recall that 𝑝 ∈ 𝒮︀ if and only if 𝐹𝑋,𝒮︀ (𝑝) + 𝑤𝑝 + 𝑣𝑝 ≥ 𝜏 , and condition on the good event |𝑤𝑝 + 𝑣𝑝 | ≤ 𝛼 (probability ≥ 1 − 𝛽). If 𝑝 ∈ 𝒮︀, then 𝐹𝑋,𝒮︀ (𝑝) ≥ 𝜏 − (𝑤𝑝 + 𝑣𝑝 ) ≥ 𝜏 − 𝛼, so every selected prefix has residual at least 𝜏 − 𝛼 (no false positives). Conversely, if 𝑝 ∉ 𝒮︀, then 𝐹𝑋,𝒮︀ (𝑝) < 𝜏 − (𝑤𝑝 + 𝑣𝑝 ) ≤ 𝜏 + 𝛼. Equivalently, every prefix that is 𝛼-far from 𝜏 is classified correctly: 𝐹𝑋,𝒮︀ (𝑝) ≥ 𝜏 + 𝛼 forces 𝑝 ∈ 𝒮︀, and 𝐹𝑋,𝒮︀ (𝑝) ≤ 𝜏 − 𝛼 forces 𝑝 ∉ 𝒮︀. Relative Error Fix 𝑝 ∈ 𝒮︀. We have ∑

𝐹𝑋,𝒮︀ (𝑞) = 𝑓𝑋 (𝑝),

(39)

𝐹̃𝑋,𝒮︀ (𝑞)|

(40.1)

𝑞∈𝒮︀∧𝑞⪰𝑝

Therefore, |𝑓𝑋 (𝑝) − 𝑓̃𝑋 (𝑝)| = |𝑓𝑋 (𝑝) −

∑ 𝑞∈𝒮︀∧𝑞⪰𝑝

≤ |𝑓𝑋 (𝑝) − ∑ 𝐹𝑋,𝒮︀ (𝑞)| + ∑ |𝐹𝑋,𝒮︀ (𝑞) − 𝐹̃𝑋,𝒮︀ (𝑞)| 𝑞∈𝒮︀∧𝑞⪰𝑝 𝑞∈𝒮︀∧𝑞⪰𝑝 ⏟

(40.2)

≤ 𝑐𝑝 ⋅ 𝛼 = 𝑐𝑝 𝛼

(40.3)

where the last bound uses |𝐹𝑋,𝒮︀ (𝑞) − 𝐹̃𝑋,𝒮︀ (𝑞)| ≤ 𝛼 on the good event from the coverage analysis, summed over the 𝑐𝑝 selected prefixes. To turn this into a relative error, bound 𝑓𝑋 (𝑝) from below. By coverage, each of the 𝑐𝑝 selected 𝑞 with 𝑞 ⪰ 𝑝 has 𝐹𝑋,𝒮︀ (𝑞) ≥ 𝜏 − 𝛼, and these residual masses are disjoint and all lie under 𝑝, so 𝑓𝑋 (𝑝) =

∑

𝐹𝑋,𝒮︀ (𝑞) ≥ 𝑐𝑝 (𝜏 − 𝛼).

(41)

𝑐𝑝 𝛼 𝑓 (𝑝) − 𝑓̃𝑋 (𝑝) 𝛼 | 𝑋 |≤ = . 𝑓𝑋 (𝑝) 𝑐𝑝 (𝜏 − 𝛼) 𝜏 −𝛼

(42)

𝑞∈𝒮︀∧𝑞⪰𝑝

Therefore

Finally, the explicit threshold guard of Algorithm 1 forces any non-trivial run to satisfy 𝜏 ≥ 24Δ log(2ℎ/(𝛿𝛽)). The coverage bound gives 𝛼 ≤ 12Δ log(2𝑛ℎ/𝛽) ≤ 12Δ log(2ℎ/(𝛿𝛽)) (using 𝑛 ≤ 1/𝛿), so this guard is exactly the condition 𝜏 ≥ 2𝛼, i.e. 𝛼 ≤ 𝜏 /2. Hence 𝜏 − 𝛼 ≥ 𝜏 /2, so 𝛼 2𝛼 ≤ , 𝜏 −𝛼 𝜏 Now 𝑝 ∉ 𝒮︀, so 𝑝 is no longer a selected ancestor of the mass beneath it. 24

(43)

Differentially Private Hierarchical Heavy Hitters

𝑓𝑋 (𝑝) −

∑

𝐹𝑋,𝒮︀ (𝑞) = 𝐹𝑋,𝒮︀ (𝑝).

(44)

𝑞∈𝒮︀∧𝑞⪰𝑝

The key point is that this miss is small as 𝐹𝑋,𝒮︀ (𝑝) + 𝑤𝑝 + 𝑣𝑝 < 𝜏 , so on the good event (𝑤𝑝 + 𝑣𝑝 ≥ −𝛼) 𝐹𝑋,𝒮︀ (𝑝) < 𝜏 + 𝛼,

(45)

(46.1)

This gives us,

=𝐹𝑋,𝒮︀ (𝑝)

≤ 𝐹𝑋,𝒮︀ (𝑝) + 𝑐𝑝 𝛼

(46.2)

By the residual decomposition, 𝑓𝑋 (𝑝) = 𝐹𝑋,𝒮︀ (𝑝) +

∑

𝐹𝑋,𝒮︀ (𝑞) ≥ 𝐹𝑋,𝒮︀ (𝑝) + 𝑐𝑝 (𝜏 − 𝛼)

(47)

𝑞∈𝒮︀∧𝑞⪰𝑝

since the 𝑐𝑝 selected residuals under 𝑝 are disjoint and each at least 𝜏 − 𝛼. Hence 𝐹𝑋,𝒮︀ (𝑝) + 𝑐𝑝 𝛼 𝑓 (𝑝) − 𝑓̃𝑋 (𝑝) | 𝑋 |≤ 𝑓𝑋 (𝑝) 𝐹𝑋,𝒮︀ (𝑝) + 𝑐𝑝 (𝜏 − 𝛼)

(48.1)

≤

(𝜏 + 𝛼) + 𝑐𝑝 𝛼 (𝜏 + 𝛼) + 𝑐𝑝 (𝜏 − 𝛼)

(48.2)

≤

1 2𝛼 + , 𝑐𝑝 + 1 𝜏

(48.3)

where the second line maximises over 𝐹𝑋,𝒮︀ (𝑝) < 𝜏 + 𝛼 (the ratio increases in 𝐹𝑋,𝒮︀ (𝑝) since 𝜏 − 𝛼 > 𝛼) and the third uses 𝛼 ≤ 𝜏 /2 from the threshold guard. ⁠ □

4 Streaming Private Hierarchical Heavy Hitters In the previous section we proved that the scale of the DP noise per query scales only by a small constant factor that is independent of the height of the hierarchy and the number of hierarchical heavy hitters in the dataset. A critical factor to being able to bypass composition was that there was no space limitation, and we could store the exact conditional count for every query in memory. This meant that we could eventually remove the contribution of the neighbouring element 𝑥′ completely (restricting the privacy loss entirely to the green and orange nodes in Figure 2). Thus for a large majority of queries, neighboring inputs 𝑋 and 𝑋 ′ were treated identically.

Ari, Cormode, Kanza, Srivastava, Zhou

Algorithm 2: Insert into MG Sketch Input: Next data 𝑥 ∈ ℋ︀, increment 𝑣 > 0. Parameters: Number of counters 𝜅. 1 if 𝑥 ∈ 𝒯︀ then 2 𝐶[𝑥] = 𝐶[𝑥] + 𝑣 3 else if 𝐶[𝑖] ≥ 𝑣 for all 𝑖 ∈ 𝒯︀ then 4 𝐶[𝑖] = 𝐶[𝑖] − 𝑣 for all 𝑖 ∈ 𝒯︀ 5 else 6 Let 𝑦̃ = arg min𝑦∈𝒯︀ 𝐶[𝑦] 7 𝒯︀ = (𝒯︀ \ {̃ 𝑦}) ∪ {𝑥} 8 𝐶[𝑥] = 𝑣 9 end if Algorithm 2: Insertion Operation For A Single MG Sketch

In the streaming setting, we do not have the luxury of storing exact counts. Thus, we will need to use some streaming data structure [8, 13, 36] in order to approximate residual frequencies. In this work, we use one Misra Gries (MG) sketch with 𝜅 counters per level of the hierarchy. Thus the total space used is 𝑂(𝜅ℎ). We choose the MG sketch for two reasons. Firstly, Pankaj K Agarwal, Graham Cormode, Zengfeng Huang, Jeff M Phillips, Zhewei Wei, and Ke Yi. [1] showed that the MG sketch is isomorphic to the Space Saving algorithm, and Michael Mitzenmacher, Thomas Steinke, and Justin Thaler. [36] show that the space saving algorithm is optimal for non-private hierarchical heavy hitter estimation. Thus, if we replace SS with MG in the non private HHH estimation problem, we retain the same optimality results. Secondly, with the MG sketch we leverage the structure in the output to circumvent the composition bounds due to approximation. The main bottleneck in approximation algorithms is that the approximated function might have large global sensitivity. Indeed T -H Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. [8] show that the MG sketch has global sensitivity Δ𝐺 = 𝜅. This implies that if we naively used noise scaled by the sensitivity of the function, the DP error grows as the streaming error drops. However we are able to leverage the critical observation made by [30:Lemma 5], who show that if the global sensitivity of the MG sketch is high, then counts of each counter after processing neighbouring streams are highly correlated. Just like in Section 3 where we made use of monotonicity of residual queries, we will use this correlation to circumvent composition. Our techniques are related to the more general observation that structure has often been used to bypass compo sition in the privacy community [19, 21, 25, 28]. In summary, to construct our HHH estimation algorithm in the streaming setting, we first modify the Michael Mitzenmacher, Thomas Steinke, and Justin Thaler. [36] HHH algorithm to use the modified MG sketch from Christian Janos Lebeda and Jakub Tetek. [30] instead of the SpaceSaving algorithm. Then we repeatedly leverage the structure of the output to bound the DP error to be independent of the available space. Note, we cannot avoid the approximation error introduced due to lack of space, regardless of privacy. In the streaming setting, our contribution is to show that the DP error for HHH is not affected by this approximation parameter 𝜅. Before describing our algorithm, we first provide an overview of the proof behind how we keep the DP error independent of the number of counters, and why the tricks used in the non-streaming section to make the noise independent of the height of the hierarchy no longer apply.

4.1 Technical Overview Our main insight in the non-streaming setting was that the DP noise could be independent of the height of the hierarchy ℎ. Unfortunately, in the streaming setting, this claim no longer holds true. To fully describe 26

Differentially Private Hierarchical Heavy Hitters

why, we first re-state a lemma by [30:Lemma 5] which formally describes the observed outcomes when a MG sketch processes neighbouring input streams. Lemma 4.1.1 (Lebeda & Tětek; Lemma 5, restated) Let 𝑋 = 𝑋 ′ ∪ {𝑥}. Let (𝒯︀, 𝐶) ← 𝖬𝖦(𝜅, 𝑋) and (𝒯︀′ , 𝐶 ′ ) ← 𝖬𝖦(𝜅, 𝑋 ′ ) be the output of Algorithm 2 with inputs 𝑋 and 𝑋 ′ . Then, |𝒯︀ ∪ 𝒯︀′ | ≥ 𝜅 − 2; for all 𝑥 ∉ 𝒯︀ ∪ 𝒯︀′ , 𝐶[𝑥] ≤ 1 and 𝐶 ′ [𝑥] ≤ 1; and exactly one of the following is true: 1. ∃𝑖 ∈ 𝒯︀, such that 𝐶[𝑖] = 𝐶 ′ [𝑖] + 1, and ∀𝑗 ≠ 𝑖 : 𝐶[𝑗] = 𝐶 ′ [𝑗]. 2. ∀𝑖 ∈ 𝒯︀′ : 𝐶[𝑖] = 𝐶 ′ [𝑖] − 1, and 𝐶 ′ [𝑗] = 0 for 𝑗 ∉ 𝒯︀′ . In the lemma above, (𝒯︀, 𝐶) and (𝒯︀′ , 𝐶 ′ ) denote the output of the MG algorithm (Algorithm 2) on the two neighbouring streams 𝑋 and 𝑋 ′ . The lemma states that there can be at most 2 elements that are in 𝒯︀, but not in 𝒯︀′ , and vice versa. We will refer to these as isolated elements. Furthermore, the count of an isolated element must always be at most 1. We can use the thresholding trick from stability histograms to suppress isolated elements with high probability. The threshold for suppression is set a little higher, as there are two isolated elements instead of one. Along with the above statements, after processing neighbouring data streams, Lemma 4.1.1 also states that the resulting sketches could be in one of two scenarios illustrated in Figure 4. In the scenario shown in Figure 4 (b), we have two histograms with 𝜅 bins that differ in at most two locations by a count of 1. All other bins have the exact same values across both sketches. We can easily release private versions of these histograms by simply applying the Laplace mechanism with suppression of small values. The other scenario, described by Figure 4 (a), appears more problematic at first glance. We have that the counts across two outputs 𝐶 and 𝐶 ′ in the two sketches all differ by the same amount across all the bins. This is undesirable in two ways. First, now the global sensitivity of the approximated counts is 𝜅, so it appears that the DP noise will need to scale linearly in 𝜅 (which can be a large constant). Secondly, notice that we can no longer restrict the influence of differing nodes in 𝒯︀′ to a single hierarchical heavy hitter like we did in the illustration given in Figure 2. The neighbouring elements are now spread across all the bins, and they influence multiple hierarchical heavy hitters. Furthermore, as the MG sketch often underapproximates the true count of an element, we cannot guarantee that we have removed the influence of a neighbouring element higher up in the tree by removing a descendant lower in the tree. This means we cannot restrict the influence of neighbouring elements and partition the tree like before to avoid paying the privacy loss due to composition for ℎ levels of the hierarchy. Therefore, it seems challenging to circumvent composition bounds due to the height when using the MG sketch.

<latexit sha1_base64="g18plxlLmzRbcIeYK7a2spJyOjY=">AAAB6HicbVBNS8NAEJ3Ur1q/qh69LBbBU0lEqseCF48t2A9oQ9lsJ+3azSbsboQS+gu8eFDEqz/Jm//GbZuDtj4YeLw3w8y8IBFcG9f9dgobm1vbO8Xd0t7+weFR+fikreNUMWyxWMSqG1CNgktsGW4EdhOFNAoEdoLJ3dzvPKHSPJYPZpqgH9GR5CFn1Fip2R2UK27VXYCsEy8nFcjRGJS/+sOYpRFKwwTVuue5ifEzqgxnAmelfqoxoWxCR9izVNIItZ8tDp2RC6sMSRgrW9KQhfp7IqOR1tMosJ0RNWO96s3F/7xeasJbP+MySQ1KtlwUpoKYmMy/JkOukBkxtYQyxe2thI2poszYbEo2BG/15XXSvqp6tWqteV2pkzyOIpzBOVyCBzdQh3toQAsYIDzDK7w5j86L8+58LFsLTj5zCn/gfP4ArxGMxQ==</latexit>

<latexit sha1_base64="XUwzTTmtKTE+Jvk+CBYAJwzG1Wc=">AAAB6XicbVBNS8NAEJ3Ur1q/qh69LBbRU0lEqseCF49V7Ae0oWy2k3bpZhN2N0IJ/QdePCji1X/kzX/jts1BWx8MPN6bYWZekAiujet+O4W19Y3NreJ2aWd3b/+gfHjU0nGqGDZZLGLVCahGwSU2DTcCO4lCGgUC28H4dua3n1BpHstHM0nQj+hQ8pAzaqz00Dnvlytu1Z2DrBIvJxXI0eiXv3qDmKURSsME1brruYnxM6oMZwKnpV6qMaFsTIfYtVTSCLWfzS+dkjOrDEgYK1vSkLn6eyKjkdaTKLCdETUjvezNxP+8bmrCGz/jMkkNSrZYFKaCmJjM3iYDrpAZMbGEMsXtrYSNqKLM2HBKNgRv+eVV0rqserVq7f6qUid5HEU4gVO4AA+uoQ530IAmMAjhGV7hzRk7L86787FoLTj5zDH8gfP5Aw94jPY=</latexit>

44553

33442

44552

04550 14550 (b)

(a)

Figure 4: The figure above illustrates the implications of Lemma 4.1.1. There are two possible config urations after processing neighbouring streams. One configuration, depicted by figure (a), is that every count in one sketch is different from the count in the other sketch by one unit in the same direction. The other outcome is that either exactly one counter is different for all counters that are nonzero in both sketches. Additionally, when in configurations depicted by Figure (b), there can be at most 2 elements per sketch that are not in the other sketch. The count of these elements when present is always 1. The second outcome, denoted by figure (b) is identical to the configuration discussed for stability histograms in the previous section, where each sketch has at most a single count that is different.

Ari, Cormode, Kanza, Srivastava, Zhou

Although we cannot remove the dependence on the height of the hierarchy in the streaming setting, inspired by the observations made by Christian Janos Lebeda and Jakub Tetek. [30], we are still able to remove the dependence on 𝜅. We show that, even in the scenario depicted by Figure 4 (a), the DP noise is actually independent of the number of counters in the sketch. This might appear unintuitive at first glance, as the global sensitivity is still 𝜅. To gain intuition towards understanding why, we first review the privacy proof of the original SVT algorithm. The main observation there was that before we see the first ⊤, we could group all the small valued queries for which the output was ⊥, and treat them as one query, thus paying for them only once. We could do so because the event that all of those queries being small is equivalent to saying that the maximum of all the those queries is small. Given two neighbouring datasets, we might have 𝑡 − 1 queries, each with sensitivity 1, and thus a total sensitivity of 𝑡 − 1, but the max of these queries is still a single query with sensitivity 1. Thus, we have a single equivalent query that captures the event described by 𝑡 − 1 queries with output ⊥. A similar reframing also applies to the sketches produced by neighbouring streams. Observe that despite 𝜅 bins being different in 𝐶 and 𝐶 ′ , the direction in which they are different and the amount by which they are different is the same for all bins. Thus, we have a guarantee that, if one of the bins in 𝐶 and 𝐶 ′ is different, all bins are different, and importantly in the exact same way. There is actually just one degree of freedom, despite there being 𝜅 different counts to consider. Once one bin differs by one, all bins differ by one (i.e. the counts are correlated). In the Above threshold (a single invocation of the SVT algorithm), we looked at the max query, and in this case we can look at any one query (say the first one, which reveals everything about the other ones). The effect is equivalent. In the proof for Theorem 4.1.2 we formally show how we can handle all 𝜅 counts being different with just one sample of noise, as if we had just a single query. Remark: [30:Lemma 6] make the same claim to use one sample to cover all bins. Although the final claim is correct, there is a minor issue in their proof. In their proof, the authors define the function 𝑔 : ℝ → ℝ𝑘 such that 𝑔(𝑎) = 𝑎1𝑘 . Thus, 𝑔−1 (𝑥)⃗ is defined only if all coordinates of 𝑥⃗ are the same. Lemma 4.1.1 does not guarantee that all the counts are the same, only that two neighbouring differ by the same amount in the same direction. However, their proof [30] relies on inverting 𝑔−1 (𝑥)⃗ for general 𝑥 ∈ ℝ𝑘 , which is undefined. In our analysis, there is no need to define such a function 𝑔 and we can obtain our results using the above observations. Algorithm 4 describes our algorithm for computing hierarchical private heavy hitters. First, we compute noisy heavy hitters at each level of the hierarchy using Algorithm 3. We show that the output of Algorithm 3 is private. Then we conservatively post-process this private output to get our desired result. Remark: For a fixed level ℓ, Algorithm 3 is identical to [30:Algorithm 2], with an essential alteration. In the count-release step of the algorithm, we generate a fresh batch of randomness independent of thresholding operation to release approximate counts. The reason for this is subtle but immediate when viewing the algorithm from the lens of the SVT (where this issue is well documented). The construction described by Christian Janos Lebeda and Jakub Tetek. [30] re-uses the thresholding noise and it is therefore not (𝜀, 𝛿) differentially private. The intuition for this is the following: If we re-use the noise in the thresholding/ release lines, then we reveal partial information about the global sample 𝛾𝑙 every time we release a noisy count. With every release, we restrict the possible values 𝛾𝑙 could take, thereby shrinking the variance of the privacy distribution. We pay for this shrinkage with a reduced privacy budget, in that the algorithm is now 𝜀′ private for 𝜀′ > 𝜀. See Appendix D for more details about how our privacy proof would break if we re-used noise.

Differentially Private Hierarchical Heavy Hitters

Algorithm 3: Private Release Input: Data stream 𝑋, Privacy parameters 𝜀 and 𝛿. Construct ℎ sketches (𝖬𝖦1 , …, 𝖬𝖦ℎ ) by running Algorithm 2 for each 𝑥 ∈ 𝑋 and every generali 1 sation of 𝑥. 2 for ℓ ∈ [ℎ, ℎ − 1, …, 1] do 3 𝛾ℓ ← 𝖫𝖺𝗉𝗅𝖺𝖼𝖾( 2ℎ 𝜀 ) 4 Let (𝒯︀ℓ , 𝐶ℓ ) = 𝖬𝖦ℓ 5 for 𝑖 ∈ 𝒯︀ℓ do 6 𝑤𝑖 ← 𝖫𝖺𝗉𝗅𝖺𝖼𝖾( 4ℎ 𝜀 ) 7 if 𝐶ℓ [𝑖] + 𝛾ℓ + 𝑤𝑖 > 1 + 6ℎ 𝜀 log(3ℎ/𝛿) then 8 𝐶ℓ [𝑖] = 𝐶ℓ [𝑖] + 𝖫𝖺𝗉𝗅𝖺𝖼𝖾( 4ℎ 𝜀 ) (fresh noise) 9 else 10 𝐶ℓ [𝑖] = 0 11 end if 12 end for 13 Set 𝖬𝖦ℓ = (𝒯︀ℓ , 𝐶ℓ ) 14 end for 15 Output (𝖬𝖦1 , …, 𝖬𝖦ℎ ). Algorithm 3: Private Release

Theorem 4.1.2 (Privacy) Algorithm 3 is (𝜀, 𝛿)-DP. Proof. Fix some level ℓ. At each level of the tree, we have at most 𝜅 + 1 independent samples from a Laplace distribution, denoted by 𝑤1 , …, 𝑤𝜅 and 𝛾ℓ in Algorithm 3. We also process each level of the data structure independently. The resulting output (𝒯︀ℓ , 𝐶ℓ ) or (𝒯︀ℓ′ , 𝐶ℓ′ ) is in one of two conditions stated in Lemma 4.1.1 and as illustrated in Figure 4. We will use the first 𝜅 independent samples to handle the case in Figure 4 (b), which is essentially the stability histogram problem with Laplace noise and global sensitivity 2. Case 1. First we need to handle the isolated counters in stability histograms. Remember that in isolated counter events there is an element 𝑥 ∈ 𝒯︀ℓ but 𝑥 ∉ 𝒯︀ℓ′ , or vice versa. From Lemma 4.1.1, as |𝒯︀ ∩ 𝒯︀′ | ≥ 𝜅 − 2, there can be at most 2 isolated elements included in the output of the algorithm at any given level ℓ. Let 𝑎, 𝑏 ∈ 𝒯︀ℓ denote the possible isolated elements at level ℓ after processing 𝑋. If 𝑎 or 𝑏 were to ever show up in the output, the privacy adversary could perfectly distinguish 𝑋 and 𝑋 ′ . For convenience, define 𝜐 ≔ 2ℎ 3ℎ 𝜀 log( 𝛿 ). For 𝑎 to show up in the final output, we need 𝑤𝑎 + 𝛾ℓ to push the noisy count of 𝑎 over 1 + 3𝜐. Once again from the tail bounds of the Laplace distribution, we have that the probability Pr[𝑤𝑎 > 2𝜐] ≤ 𝛿 3ℎ . A similar argument bounds the probability of either of 𝛾ℓ and 𝑤𝑏 exceeding 𝜐 and 2𝜐, respectively. Using the same union bound across both events, we get with probability at least 1 − 𝛿/ℎ that both 𝑤𝑎 + 𝛾ℓ ≤ 3𝜐 and 𝑤𝑏 + 𝛾ℓ ≤ 3𝜐. For all counters, we add noise drawn from a Laplace distribution, using privacy parameter 𝜀/4ℎ once during thresholding, and once during public release. Taking the union over the height of the hierarchy, we get that the first case is handled with (𝜀, 𝛿)-privacy. Case 2. Next we show that the other case (Figure 4 (a)), where all counters in 𝐶 and 𝐶 ′ are off by the same amount in the same direction, is also handled with 𝜀/2ℎ-DP. This is case (2) of Lemma 4.1.1, where

Ari, Cormode, Kanza, Srivastava, Zhou

𝐶[𝑖] = 𝐶 ′ [𝑖] − 1 for all 𝑖 ∈ 𝒯︀′ . Remember that our analysis considered the noise in 𝑤1 , …, 𝑤𝜅 already for stability histograms. Thus we want 𝛾ℓ to cover for this other case entirely. Here we use notation 𝑎1𝜅 to denote the vector [𝑎, 𝑎, …, 𝑎] of size 𝜅 for any 𝑎 ∈ ℝ, and 𝑤⃗ succinctly denotes all the 𝑤𝑖 ’s at level ℓ. The analysis below is for any fixed ℓ ∈ [ℎ], so we drop the subscript ℓ to avoid an overload of notation. Let 𝑦 ⃗ ∈ {⊥, ⊤}𝜅 be the released-or-not pattern, with coordinate 𝑖 equal to ⊤ exactly when the noisy count 3ℎ ′ 𝜅 exceeds the threshold 1 + 6ℎ 𝜀 log( 𝛿 ). Since 𝐶 = 𝐶 − 1 , Pr

𝛾←$ 𝖫𝖺𝗉((2ℎ)/𝜀) 𝑤← ⃗ $𝖫𝖺𝗉((4ℎ)/𝜀)⊗𝜅

= ∫ 𝑓𝑤⃗ (𝑧)⃗ ⋅ = ∫ 𝑓𝑤⃗ (𝑧)⃗ ⋅

[𝐶 + 𝛾1𝜅 + 𝑤⃗ = 𝑦]⃗

= 𝑒𝜀/2ℎ

[𝐶 + 𝛾1𝜅 + 𝑧 = 𝑦]⃗ d𝑧 ⃗

(49.2)

[𝐶 ′ + (𝛾 − 1)1𝜅 + 𝑧 = 𝑦]⃗ d𝑧 ⃗

(49.3)

[𝐶 ′ + 𝛾1𝜅 + 𝑧 = 𝑦]⃗ d𝑧 ⃗

(49.4)

𝛾←$ 𝖫𝖺𝗉((2ℎ)/𝜀)

≤ 𝑒𝜀/2ℎ ∫ 𝑓𝑤⃗ (𝑧)⃗ ⋅ Pr

(49.1)

𝛾←$ 𝖫𝖺𝗉((2ℎ)/𝜀)

𝛾←$ 𝖫𝖺𝗉((2ℎ)/𝜀) 𝑤← ⃗ $𝖫𝖺𝗉((4ℎ)/𝜀)⊗𝜅

[𝐶 ′ + 𝛾1𝜅 + 𝑤⃗ = 𝑦]⃗

⊗𝜅

(49.5)

𝑓𝑤⃗ denotes the density of 𝖫𝖺𝗉(4 ℎ𝜀 ) . Finally, applying basic composition over ℎ levels of the tree, we get that the entire algorithm restricted to the scenario depicted in Figure 4 (a) is (𝜀/2, 0)-DP. Once we have decided which counters will be used, the final noisy release is (𝜀/2, 0)-DP. Hence, regardless of which case we happen to be in, we obtain that the whole protocol is (𝜀, 𝛿)-DP. ⁠ □

Differentially Private Hierarchical Heavy Hitters

Algorithm 4: Final HHH-Streaming Algorithm Input: Data 𝑋, Privacy parameter 𝜀 ∈ (0, log 𝑛), 𝛿 = 𝑜(1/𝑛), Threshold 𝜏 > 0, Confidence Parameter 𝛽 ∈ (0, 1/2). Parameters: Number of counters 𝜅, Height of hierarchy ℎ. Run Algorithm 3 with input 𝑋, Threshold 𝜏 , and privacy parameters (𝜀, 𝛿) to get outputs 1 (𝖬𝖦1 , …, 𝖬𝖦ℎ ). 𝑛 2𝜅ℎ 2 𝛼1 = (1 + 6ℎ log[3ℎ/𝛿] ) + 𝜅+1 + ( 8ℎ 𝜀 𝜀 log[ 𝛽 ]) 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

2𝜅ℎ 𝛼2 = (1 + 6ℎ log[3ℎ/𝛿] ) + ( 8ℎ 𝜀 𝜀 log[ 𝛽 ])

for 𝑙 ∈ [ℎ, ℎ − 1, …, 1] do Let (𝒯︀𝑙 , 𝐶𝑙 ) = 𝖬𝖦𝑙 for 𝑒 ∈ 𝒯︀𝑙 do if 𝐶𝑙 [𝑒] + 𝛼1 > 𝜏 − 𝛼1 then 𝒮︀ = 𝒮︀ ∪ {𝑒} 𝑓̃𝑋 (𝑒) = 𝐶𝑙 [𝑒] (Noisy Estimate) for 𝑝 ∈ 𝖦𝖾𝗇𝖾𝗋𝖺𝗅𝗂𝗌𝖾(𝑒) do Let 𝑖 = 𝖫𝖾𝗏𝖾𝗅(𝑝), (𝒯︀𝑖 , 𝐶𝑖 ) = 𝖬𝖦𝑖 if 𝑝 ∈ 𝒯︀𝑖 then 𝐶𝑖 [𝑝] = 𝐶𝑖 [𝑝] − (𝐶𝑙 [𝑒] − 𝛼2 ) (conservatively remove residual) end if end for end if end for end for Output (𝒮︀, 𝑓̃𝑋 (𝒮︀)). Algorithm 4: Final Algorithm

Corollary 4.1.2.1 (Privacy of Final Algorithm) Algorithm 4 is (𝜀, 𝛿)-DP The proof follws from that the fact the output is post-processing the (𝜀, 𝛿)-DP output of Algorithm 3. Theorem 4.1.3 (Error) For all 𝑝 ∈ 𝒮︀, we have with probability 1 − 𝛽, |𝑓̃𝑋 (𝑝) − 𝑓𝑋 (𝑝)| ≤ 𝛼 where 𝛼 = (1 +

6ℎ log(3ℎ/𝛿) 𝑛 8ℎ 2𝜅ℎ )+ + ( log( )) 𝜀 𝜅+1 𝜀 𝛽

Proof. Next we state the well known estimation error due to space constraints for the Misra Gries algorithm. A proof for this lemma can be found in [4:Section 2]. Lemma 4.1.4 (MG Error) Let 𝐶[𝑥] denote the frequency estimate for 𝑥 ∈ 𝑋, given by a MG sketch 𝑛 with 𝜅 counters on input stream 𝑋. Then 𝐶[𝑥] ∈ [𝑓𝑋 (𝑥) − 𝜅+1 , 𝑓𝑋 (𝑥)].

Ari, Cormode, Kanza, Srivastava, Zhou

For any fixed level of the hierarchy, with probability 1 − 𝛽/ℎ we have three sources of error. The first 𝑛 source of 1 + 6ℎ log(3ℎ/𝛿) comes from suppressing isolated counts. The second error term 𝜅+1 comes from 𝜀 the error of the deterministic MG counter (Lemma 4.1.4). For the third error term, for some 𝑏 to be defined later, at each level 𝑙 ∈ [ℎ], we want with probability at most 𝛽/2ℎ that |𝛾𝑙 | > 𝑏/2 and with probability at most 𝛽/2ℎ we want for 𝑖 ∈ [𝜅], |𝑤𝑖 | > 𝑏/2. This guarantees, with probability 1 − 𝛽/ℎ, that max𝑖∈𝜅 |𝑤𝑖 | + |𝛾𝑙 | ≤ 𝑏. Using the tail bounds of the Laplace distribution, and taking union bounds over all the counters we get 𝜀

Pr[max 𝑤𝑖 > 𝑏/2] ≤ 𝜅𝑒− 8ℎ 𝑏 𝑖∈𝜅

(50)

𝜀

Setting 𝛽/2ℎ = 𝜅𝑒− 8ℎ 𝑏 , we get 𝑏≥

8ℎ 2𝜅ℎ log 𝜀 𝛽

(51)

We can also bound the error from 𝛾𝑙 using a similar analysis, and it turns out the above value for 𝑏 suffices to bound the error due to 𝛾𝑙 . Finally, we take the union bound over all ℎ levels, and get with probability 1 − 𝛽, the total error incurred by any node is at most 𝛼 = (1 +

6ℎ log(3ℎ/𝛿) 𝑛 8ℎ 2𝜅ℎ )+ + ( log( )) 𝜀 𝜅+1 𝜀 𝛽

(52) ⁠ □

We note that the dependence on ℎ here is not optimal. We have used basic composition to show a linear dependence on ℎ, in order to keep the development clear. However, it is possible to show an improved √ dependence on ℎ, by invoking more advanced composition theorems [5, 20]. Since we assume that ℎ is relatively small in practice, we don’t expand on this point in this presentation. Note that as we cannot avoid the composition error due to the height of the hierarchy, we can directly estimate the unconditional frequen cies of a node 𝑝 by looking at the noisy count of 𝐶𝖫𝖾𝗏𝖾𝗅(𝑝) [𝑝]. However, this means that there is no advantage to reporting relative error guarantees instead of the absolute error in the streaming case: all prefixes incur noise of the same magnitude. We leave it open to show whether this gap is provably unavoidable or can be surmounted using different techniques. Theorem 4.1.5 (Coverage) For all 𝑝 ∉ 𝒮︀, with probability 1 − 𝛽, 𝐹𝑋,𝒮︀ (𝑝) ≤ 𝜏 − 𝛼. Proof. Let 𝒮︀ denote the output of Algorithm 4. Fix 𝑝 ∉ 𝒮︀, define 𝒜︀𝑝 = {𝑞 ∈ 𝒮︀ : 𝑞 ≻ 𝑝 ∧ ∄𝑞 ′ s.t. 𝑞 ≻ 𝑞 ′ ∧ 𝑞 ′ ≻ 𝑝}. Let 𝑠𝑝 denote the amount of weight removed from the unconditional count of 𝑝 in the removal step of Algorithm 4 for prefix 𝑝. Note that 𝑠𝑝 ≤ ∑𝑞∈𝒜︀ 𝑓𝑋 (𝑞) by definition, as MG counts cannot ever 𝑝

overestimate 𝑓𝑋 (𝑒). We need to account any overestimation due to differential privacy. With probability 1 − 𝛽, we have that the noise per node due to DP is 𝛼2 . Thus, with probability 1 − 𝛽, 𝐶𝑙 [𝑒] − 𝛼2 in the removal line is strictly less than 𝑓𝑋 (𝑒) (as we have removed the DP contribution and 𝐶𝑙 [𝑒] ≤ 𝑓𝑋 (𝑒)). So we always take off less than we could from the count of 𝑝. Any prefix 𝑝 is included in 𝒮︀ only if 𝐶𝑙 [𝑝] + 𝛼1 > 𝜏 − 𝛼1 . So for all 𝑝 ∉ 𝒮︀, we must have 𝐶𝑙 [𝑝] + 𝛼1 − 𝑠𝑝 ≤ 𝜏 − 𝛼1 . Therefore, with probability 1 − 𝛽, 𝐹𝑋,𝒮︀ (𝑝) = 𝑓𝑋 (𝑝) − ∑ 𝑓𝑋 (𝑞)

(53.1)

𝑞∈𝒜︀𝑝

≤ (𝐶𝑙 [𝑝] + 𝛼1 ) − 𝑠𝑝

(53.2)

Differentially Private Hierarchical Heavy Hitters

≤ 𝜏 − 𝛼1

(53.3)

Equation 53.1 comes from the definition of residual count. Equation 53.2 comes from the fact that 𝑠𝑝 ≤ ∑𝑞∈𝒜︀ 𝑓𝑋 (𝑞), and 𝑓𝑋 (𝑝) ≤ 𝐶𝑙 [𝑝] + 𝛼1 with probability 1 − 𝛽 (from Theorem 4.1.3). ⁠ □ 𝑝

Ari, Cormode, Kanza, Srivastava, Zhou

References [1]

Pankaj K Agarwal, Graham Cormode, Zengfeng Huang, Jeff M Phillips, Zhewei Wei, and Ke Yi. 2013. Mergeable summaries. ACM Transactions on Database Systems (TODS) 38, 4 (2013), 1–28.

[2]

Victor Balcer and Salil Vadhan. 2017. Differential privacy on finite computers. arXiv preprint arXiv:1709.05396 (2017).

[3]

Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Guha Thakurta. 2017. Practical locally private heavy hitters. Advances in Neural Information Processing Systems 30, (2017).

[4]

Prosenjit Bose, Evangelos Kranakis, Pat Morin, and Yihui Tang. 2003. Bounds for Frequency Estimation of Packet Streams. In SIROCCO, 2003. 18–20.

[5]

Mark Bun and Thomas Steinke. 2016. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, 2016. 635–658.

[6]

Mark Bun, Kobbi Nissim, and Uri Stemmer. 2019. Simultaneous private learning of multiple concepts. Journal of Machine Learning Research 20, 94 (2019), 1–34.

[7]

Mark Bun, Thomas Steinke, and Jonathan Ullman. 2017. Make up your mind: The price of online queries in differential privacy. In Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms, 2017. 1306–1325.

[8]

T -H Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. 2012. Differentially private continual monitoring of heavy hitters from distributed streams. In Privacy Enhancing Technologies: 12th Interna tional Symposium, PETS 2012, Vigo, Spain, July 11-13, 2012. Proceedings 12, 2012. 140–159.

[9]

Yan Chen and Ashwin Machanavajjhala. 2015. On the privacy properties of variants on the sparse vector technique. arXiv preprint arXiv:1508.07306 (2015).

[10] Albert Cheu. 2021. Differential privacy in the shuffle model: A survey of separations. arXiv preprint arXiv:2107.11839 (2021). [11] Graham Cormode, Flip Korn, S Muthukrishnan, and Divesh Srivastava. 2004. Diamond in the rough: Finding hierarchical heavy hitters in multi-dimensional data. In Proceedings of the 2004 ACM SIGMOD international conference on Management of data, 2004. 155–166. [12] Graham Cormode, Flip Korn, S Muthukrishnan, and Divesh Srivastava. 2008. Finding hierarchical heavy hitters in streaming data. ACM Transactions on Knowledge Discovery from Data (TKDD) 1, 4 (2008), 1–48. [13] Graham Cormode, Flip Korn, Shanmugavelayutham Muthukrishnan, and Divesh Srivastava. 2003. Finding hierarchical heavy hitters in data streams. In Proceedings 2003 VLDB Conference, 2003. 464–475. [14] Graham Cormode, Cecilia Procopiuc, Divesh Srivastava, and Thanh TL Tran. 2012. Differentially private summaries for sparse data. In Proceedings of the 15th International Conference on Database Theory, 2012. 299–311. [15] Henry Corrigan-Gibbs and Dan Boneh. 2017. Prio: Private, robust, and scalable computation of aggregate statistics. In 14th USENIX symposium on networked systems design and implementation (NSDI 17), 2017. 259–282. [16] Wei Dong, Dajun Sun, and Ke Yi. 2023. Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy. Proceedings of the ACM on Management of Data 1, 2 (2023), 1–26.

Differentially Private Hierarchical Heavy Hitters

[17] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. 2015. Preserving statistical validity in adaptive data analysis. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, 2015. 117–126. [18] Cynthia Dwork, Frank McSherry, and Kunal Talwar. 2007. The price of privacy and the limits of LP decoding. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007. 85–94. [19] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. 2009. On the com plexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009. 381–390. [20] Cynthia Dwork, Aaron Roth, and others. 2014. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science 9, 3–4 (2014), 211–407. [21] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. 2010. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010. 51–60. [22] Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. 2020. The power of factorization mechanisms in local and central differential privacy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020. 425–438. [23] Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. 2022. On Differentially Private Counting on Trees. arXiv preprint arXiv:2212.11967 (2022). [24] Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. 2009. Universally utility-maximizing privacy mechanisms. In Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009. 351–360. [25] Moritz Hardt and Kunal Talwar. 2010. On the geometry of differential privacy. In Proceedings of the forty-second ACM symposium on Theory of computing, 2010. 705–714. [26] John Hershberger, Nisheeth Shrivastava, Subhash Suri, and Csaba D Tóth. 2005. Space complexity of hierarchical heavy hitters in multi-dimensional data streams. In Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2005. 338–347. [27] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2015. The composition theorem for differential privacy. In International conference on machine learning, 2015. 1376–1385. [28] Haim Kaplan, Yishay Mansour, and Uri Stemmer. 2021. The sparse vector technique, revisited. In Conference on Learning Theory, 2021. 2747–2776. [29] Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. 2009. Releas ing search queries and clicks privately. In Proceedings of the 18th international conference on World wide web, 2009. 171–180. [30] Christian Janos Lebeda and Jakub Tetek. 2023. Better differentially private approximate histograms and heavy hitters using the Misra-Gries sketch. In Proceedings of the 42nd ACM SIGMOD-SIGACTSIGAI Symposium on Principles of Database Systems, 2023. 79–88. [31] Christian Janos Lebeda, David Erb, Tudor Cebere, and Aurélien Bellet. 2026. Lumberjack: Better Dif ferentially Private Random Forests through Heavy Hitter Detection in Trees. Retrieved from https:// arxiv.org/abs/2605.22756 [32] Michelle Seng Ah Lee and Luciano Floridi. 2021. Algorithmic fairness in mortgage lending: from absolute conditions to relational trade-offs. Minds and Machines 31, 1 (2021), 165–191.

Ari, Cormode, Kanza, Srivastava, Zhou

[33] Yuan Lin and Hongyan Liu. 2007. Separator: sifting hierarchical heavy hitters accurately from data streams. In Advanced Data Mining and Applications: Third International Conference, ADMA 2007 Harbin, China, August 6-8, 2007. Proceedings 3, 2007. 170–182. [34] Min Lyu, Dong Su, and Ninghui Li. 2016. Understanding the sparse vector technique for differential privacy. arXiv preprint arXiv:1603.01699 (2016). [35] Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. 2006. An integrated efficient solution for computing frequent and top-k elements in data streams. ACM Transactions on Database Systems (TODS) 31, 3 (2006), 1095–1133. [36] Michael Mitzenmacher, Thomas Steinke, and Justin Thaler. 2012. Hierarchical heavy hitters with the space saving algorithm. In 2012 Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX), 2012. 160–174. [37] Jack Murtagh and Salil Vadhan. 2015. The complexity of computing the optimal composition of differential privacy. In Theory of Cryptography Conference, 2015. 157–175. [38] Kobbi Nissim, Uri Stemmer, and Salil Vadhan. 2016. Locating a small cluster privately. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016. 413–427. [39] David Pujol and Damien Desfontaines. 2023. Open problem - Better privacy guarantees for larger groups. [40] Thomas Steinke and Jonathan Ullman. 2015. Between pure and approximate differential privacy. arXiv preprint arXiv:1501.06095 (2015). [41] Thomas Steinke. 2022. Composition of differential privacy & privacy amplification by subsampling. arXiv preprint arXiv:2210.00597 (2022). [42] Abhradeep Guha Thakurta and Adam Smith. 2013. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference on Learning Theory, 2013. 819–850. [43] Jun Zhang, Xiaokui Xiao, and Xing Xie. 2016. Privtree: A differentially private algorithm for hierar chical decompositions. In Proceedings of the 2016 international conference on management of data, 2016. 155–170. [44] Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. 2022. Differentially private linear sketches: Efficient implementations and applications. Advances in Neural Information Processing Systems 35, (2022), 12691–12704.

Differentially Private Hierarchical Heavy Hitters

A Composition and Structure Differential Privacy was initially motivated by the study of counting queries, and heavy hitter estimation can be seen as post processing of private release of counting queries. The privacy community has studied extensively the composition of privacy parameters when dealing with arbitrary counting queries. From basic composition we know that the maximum DP error of 𝑞 invocations of the Laplace mechanism scales 𝑂(1/𝜀 ⋅ 𝑞 log[𝑞]). Thomas Steinke and Jonathan Ullman. [40] show that we can save the log 𝑞 factor by exploiting the structure of correlated noise used for DP, and have error scale by 𝑂(𝑞/𝜀). Of course we could also use advanced composition [21] on top of this to further reduce the error to 𝑂(1/𝜀 ⋅ √𝑞 log[1/𝛿]). Peter Kairouz, Sewoong Oh, and Pramod Viswanath. [27] show an exact characterisation of the best privacy parameters that can be guaranteed when composing many (𝜀, 𝛿)-differentially private mechanisms. Unfortunately computing these parameters for arbitrary queries with different privacy parameters is #𝖯-complete [37]. While the early work was focused on arbitrary counting queries, there has been considerable work in exploiting structure in queries to obtain better error than basic or advanced composition. Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. [19] proposed the Above Threshold algorithm and showed that one can group similar queries together, and replace them with a single query to pay for many queries just once. This insight has led to multiple constructions of highly accurate DP algorithms that would have been impractical if we considered basic or advanced composition [7, 9, 17, 38]. Haim Kaplan, Yishay Mansour, and Uri Stemmer. [28] identified that for certain distribution of queries, the composition of the above threshold algorithm could be further improved, by observing that not all large queries include the neighbouring element. Wei Dong, Dajun Sun, and Ke Yi. [16] show how to bypass composition for special class of conjunctive queries. We direct the reader to the chapter by Thomas Steinke. [41] for a detailed survey on the role of composition in differential privacy. Despite an enormous body of work on counting queries and composition, the question of hierarchical counting with privacy has remained unexplored. In this work, we show that one can use similar tricks to the above work to exploit the structure of a hierarchy, and get highly accurate algorithms, that are not possible with general purpose techniques.

B Greater Privacy For Larger Groups As discussed earlier, we only bound the relative error of approximating the unconditional frequency of any prefix. As pointed out by [23:Page 2], if we instead wanted to upper bound the worst case absolute error, then it is known that the error must scale linearly with the height of the hierarchy. The problem of estimating private counts in a tree can be reformulated as releasing a linear query of the form 𝐴𝑥⃗ privately, where 𝑥⃗ is a vector of unconditional counts for all leaves in the hierarchy, and then finding heavy hitters post processing. The matrix 𝐴 ∈ {0, 1}|ℋ︀| × |ℋ︀| is an adjacency matrix representation of the tree that represents if one node is a parent of another or not. Releasing linear queries privately has been exhaustively studied in the privacy community [18, 22, 25, 44]. Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. [22] provide lower bounds for the absolute error of linear queries under pure and approximate differential privacy. They show that even when considering (𝜀, 𝛿)-DP, the absolute error for any private linear query algorithm scales ‖𝐴‖∞ = Θ(ℎ) (which is the same as just releasing the entire tree privately with Laplace noise). Remember, we are able to circumvent composition by leveraging the structure of a hierarchy. Requiring the error of every estimate at every level to be bounded by the same constant destroys this structure. We cannot use information gained lower down the hierarchy to make useful claims about elements higher in the hierarchy. We need to treat each level independently as we want the noise for each node to be independent. Thus the advantage of our algorithm, and that of [23:Algorithm 1], is that we can re-use information from earlier queries while still preserving privacy, paying for absolute error instead. A second advantage to considering

Ari, Cormode, Kanza, Srivastava, Zhou

relative error is that it is the more practical notion of error. This was also observed by David Pujol and Damien Desfontaines. [39], who posted as an open problem the task of finding algorithms that allow larger groups to have more privacy than smaller groups. When dealing with hierarchies, nodes higher up in the tree by definition can be estimated by counts lower in the tree (via partitions or hierarchical heavy hitters) — and this information is public knowledge. So we would like to utitlise this when designing algorithms. Consider the situation where the exact count of a node is 106 . If we incur an absolute error of 100 units when estimating the count of a node, we do not expect that to affect the final social decision associated with this private statistic. However, when the exact answer is 99, say, and we incur an error of 100 units, such a large error in estimation is unacceptable.

C Relationship To Counting Over Trees The estimation error from Theorem 3.6.2 can be used to obtain better results in practice for [23:Definition 1.4] for the simpler problem of estimating unconditional frequencies with constant relative error. Note the main difference between our result and that of Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. [23] is that they add noise with scale 𝑂(𝑐/𝜀) to estimate the count of any node, regardless of the distribution of heavy hitters12. In our case, the relative error is independent of both the height and the number of hierarchical heavy hitters. Furthermore, our algorithm is simpler to define. In [23:Algorithm 3], the authors use a geometric progression of decreasing 𝜏 ’s, and repeatedly apply [23:Algorithm 1] on these thresholds to get the relative error guarantee. It is not clear how to set these thresholds for practical algorithms on real-world datasets, and the constants are larger than the height of any hierarchical domain in practice.

D A Note About Re-using Random Samples In this section we describe how the privacy proof analysis breaks down if we re-use the same random samples for thresholding, and outputting the counts. Borrowing notation from the proof of Theorem 4.1.2, if we used fresh randomness then we can go from Pr [𝐶 + 𝛾1𝜅 + 𝑤⃗ = 𝑦]⃗ = Pr[𝐶 + 𝛾1𝜅 + 𝑤⃗ = 𝑦 ⃗ | 𝑤]⃗ Pr[𝑤]⃗ 𝛾

𝑤,𝛾 ⃗

(54)

to 𝜅

= Pr[𝑤]⃗ ∏ Pr[𝐶[𝑖] + 𝛾 + 𝑤𝑖 = 𝑦𝑖 | 𝑤𝑖 ] 𝑖=1

𝛾

(55)

without any issues. The noisy released count of 𝐶[𝑖] is independent of the thresholding operation, and the proof holds. On the other hand, if we reused noise then the second equation has further constraints. Consider the event that all noisy counters are above the threshold (this is the worst case, where we reveal maximal information about 𝛾), and let 𝑋𝑖 = 𝐶[𝑖] + 𝛾 + 𝑤𝑖 for 𝑖 ∈ [𝜅]. Then assuming we release counts in lexicographical order, we have 𝜅

̃ ∧ 𝑋 ≥ 𝜏 ]. Pr [𝐶 + 𝛾1𝜅 + 𝑤⃗ = 𝑦]⃗ = Pr[𝑤]⃗ ∏ Pr[𝑋𝑖 = 𝑦𝑖 | 𝑤⃗ ∧𝑗<𝑖 𝑋𝑗 = 𝐶[𝑗] 𝑗<𝑖 𝑗

𝑤,𝛾 ⃗

𝑖=1

𝛾

Remember 𝑐 is an upper bound on the total number of hierarchical heavy hitters.

(56)

Differentially Private Hierarchical Heavy Hitters

Each release of a noisy count puts a constraint on the possible values of 𝛾. Thus, we are no longer able to just use the pdf of the Laplace distribution to upper bound the ratios as we did in our proof (because the privacy distribution has changed to a truncated version of Laplace distribution). Viewing the same algorithm with the SVT lens, [34:Page 5, Algorithm 3] argue how not using a fresh batch of randomness is not differentially private by showing how a constraint on the value of 𝛾 needs to be ignored to complete the privacy proof (equation 11 on Page 5). This issue was originally pointed out by [43:Appendix A] where they show that re-using randomness puts additional constraints on the support of the randomness, which results in the variance of the privacy distribution to shrink. To make up for this shrinkage, they show that the scale of the noise distribution would need to be linear with the number of queries. This destroys any benefit to using SVT in the first place.

Record · ID 271714 · SHA-256 3cd367dff7e35f85
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.