1 Introduction↩︎

Complex decision support (DS) queries with multiple aggregate conditions underpin many analytical applications, including clinical diagnosis [1], [2], building management [3], and KPI evaluation [4]. They commonly arise in online analytical processing (OLAP) [5], where analysts compute group-level aggregates and compare them to thresholds to drive decisions. However, such data sources often contain sensitive individual information, meaning aggregate releases can cause serious privacy leaks [6], [7]. Differential privacy (DP) [8], [9] addresses this by limiting any single record’s influence on the output, but introduces noise that can harm decision quality. In DS settings, mechanisms must therefore provide formal utility guarantees: noisy answers can induce false positives (FP), where predicates are incorrectly accepted, and false negatives (FN), where true predicates are missed. This motivates a “utility-first” line of work [10]–[14] that specifies target utility and maximizes privacy subject to that requirement, rather than fixing a privacy budget and optimizing utility.

Prior work has made significant progress on accuracy-first differential privacy for decision support. APEx [11] introduced the paradigm but leaves errors unbounded near thresholds; MIDE [13] provides one-sided FNR guarantees for simple queries; and ProBE [14] achieves dual \((\alpha, \beta)\) guarantees for complex queries with minimal privacy loss. However, all three treat each query independently and do not exploit the natural overlap in interactive analyst sessions.

In practice analysts rarely issue queries in isolation. The nature of decision support is inherently interactive: an analyst issues an initial query, inspects the results, and then refines their analysis by tightening accuracy bounds, adjusting thresholds, changing logical operators, or combining previously queried metrics. Under the current paradigm, each such refinement incurs the full privacy cost as if it were an entirely new query, causing the cumulative privacy budget to grow linearly with the number of interactions even when successive queries are closely related. Consider, for instance, the following sequence over a medical dataset:

2.5pt

Yet the noisy aggregate values computed for Q1 already contain information that could be leveraged to answer Q2 (the same query with a tighter bound) and Q3 (which only differs in the thresholds) at a significantly reduced cost. This observation motivates the central question of this work: how can we systematically reuse cached results from previous differentially private queries to answer new, related queries while maintaining formal FNR and FPR guarantees? Answering this question introduces several challenges.

First, different types of query refinements admit fundamentally different reuse strategies. Tightening the accuracy bound \(\beta\) on the same query, shifting the threshold \(c\), changing the logical structure (AND \(\leftrightarrow\) OR), and deriving new aggregate functions from cached ones each require distinct derivation with different privacy cost implications. A systematic framework to identify when reuse is possible and how to exploit it for each type of refinement is thus needed. Second, the cache must store not only final query answers but also intermediate results at the right granularity to maximize reuse opportunities. For instance, caching the results of composed sub-expressions (e.g., \(Q_1 \cap Q_2\)) in addition to individual atomic sub-query results enables reuse even when the overall query structure changes. The design of this multi-layered cache structure, including what to store and how to efficiently identify maximal overlap with incoming queries, is a non-trivial design problem. Third, when a requested query cannot fully be answered within the remaining privacy budget, the system should be able to propose alternative queries (e.g., with relaxed bounds or adjusted thresholds) that can be answered at lower cost, presenting the analyst with meaningful trade-offs rather than simply denying the query.

In this paper, we propose ReBound, a framework for differentially private interactive decision support that addresses the three challenges above. At its core, ReBound proposes a reuse framework that supports multiple types of query changes, including threshold changes, bound tightening, logical structure modifications, and linear combinations of cached aggregate functions, with minimal additional privacy loss while maintaining formal FNR and FPR guarantees. To do so, ReBound uses a cache graph structure that stores not only atomic sub-query results but also composed sub-expressions, enabling efficient lookup of maximal reusable subgraphs when a new query arrives and fast insertion of new results upon execution. Finally, ReBound supports a privacy negotiation mechanism wherein queries requesting accuracy bounds that cannot be met within the remaining privacy budget result in a counteroffer with relaxed bounds or adjusted parameters that can be satisfied at lower cost, allowing the analyst to accept an alternative rather than receiving an outright denial.

2 Background↩︎

Let \(D \in \mathcal{D}\) denote a sensitive dataset. Two datasets \(D,D'\in\mathcal{D}\) are neighbors, written \(D \sim D'\), if they differ in one tuple. We consider the following ex-post differential privacy notion.

A complex decision-support (DS) query \(Q_{\Lambda,F}\) is an expression over atomic queries \(Q_{a_1},\ldots,Q_{a_n}\) that share the same predicate set \(\Lambda\) but may have different filters \(F=\{f_1,\ldots,f_n\}\), aggregates \(G=\{g_1,\ldots,g_n\}\), and thresholds \(C=\{c_1,\ldots,c_n\}\), combined using \(\cap\) (AND) and \(\cup\) (OR). Equivalently: \[Q_{\Lambda,F} ::= Q_a \mid Q_{\Lambda,F_1}\cap Q_{\Lambda,F_2} \mid Q_{\Lambda,F_1}\cup Q_{\Lambda,F_2}.\] Each atomic aggregate threshold query is defined as follows.

The accuracy constraints for DS queries are specified as predicate-wise false negative rates (FNRs) and false positive rates (FPRs).

3 Problem Setup↩︎

We consider an interactive decision-support workflow where an analyst adaptively issues DS queries, possibly depending on prior answers. At each round, the system minimizes incremental privacy cost while meeting \((\alpha,\beta)\) under a budget cap \(\varepsilon_{\max}\); if infeasible, it proposes a minimal relaxation of \((\alpha,\beta)\). Under this interactive setting, several interesting research questions arise.

RQ1: Designing DP Caches for DS Queries. Existing work [15]–[17] on DP caching all focus on linear/counting workloads, and store historical noisy answers/parameters to reuse them under post-processing. Their target accuracy notions are primarily numerical error bounds. However, DS query workloads [11], [13], [14] are threshold-classification queries where the utility is often defined as predicate-wise FNRs and/or FPRs. The outputs of DS queries are sets rather than numerical results, making it insufficient to just store the noisy answers and recheck the bounds when analysts change the query thresholds or demand different FNR/FPR guarantees.

Our goal is to design efficient DP caches for DS queries that capture not only answers to existing queries, but an indexed region of future DS queries for which the answers can be reused and composed. We would like to develop a novel hierarchical structure that organizes domain information, query metadata, decomposed predicates, and historical query answers, alongside algorithms to efficiently look up and update the cache when answering DS queries.

RQ2: Cache-Aware Privacy Optimization under Budget Constraints. Given the nature of uncertainty in the online/interactive query systems, an arriving complex DS query may partially overlap with historical queries yet differ in several ways, e.g., tighter FNR/FPR requirements, modified logical structure, shifted predicate thresholds, or even newly introduced predicates not present in the cache. When the cache cannot fully answer the request, how can the system acquire only the missing information and combine it with cached DP results to satisfy \((\alpha,\beta)\) with minimal incremental privacy cost, or else compute a minimal feasible utility bound relaxation under \(\varepsilon_{\max}\)?

Prior work [16], [18], [19] on refining accuracy guarantees by calibrating correlated noise and adaptive reuse is largely tailored to numerical error metrics and fixed query semantics, and therefore does not directly extend to DS queries. APEx [11] optimizes the per-query budget for DS queries, but it treats each arriving query as fresh (no cache); moreover, the uniform privacy apportionment assumptions (across predicates) of its mechanism can be misaligned with heterogeneous cached uncertainties, leading to suboptimal “top-ups” when only parts of a query can be answered from cached results. In this paper, we design cache-aware DP mechanisms that certify reusable sub-structures under new utility constraints and minimize incremental privacy cost via structure-aware allocation. When infeasible under \(\varepsilon_{\max}\), the mechanisms should return a minimal \((\alpha,\beta)\) relaxation as a counteroffer.

4 Framework Overview↩︎

Interactive DP workloads exhibit natural query overlap: analysts refine predicates, adjust thresholds, and explore related aggregates over time. ReBound maintains a structured cache of prior DP releases and derives new answers from cached results when possible, negotiating with analysts when budget constraints conflict with accuracy requirements (Figure 1). Our design follows three principles: post-processing reuse, where computations over prior DP outputs incur no additional privacy cost; utility propagation, where derived results have computable \((\alpha,\beta)\) bounds that are verified before returning reused answers; and budget-aware negotiation, where the system and analyst negotiate acceptable tradeoffs when reuse is insufficient under a constrained budget. We build on ProBE [14] as a base mechanism, which guarantees \((\alpha, \beta)\) bounds at a minimal privacy loss, but treats each query independently. It first decomposes complex queries into atomic sub-queries and optimally apportions \(\beta\) across them [13] to guarantee the overall \(\beta\)-bound, then enforces \(\alpha\) in a data-dependent step that estimates false positives and tightens the error region around the threshold when needed.

The remainder of this section describes reuse strategies, cache structure, and query processing; formal proofs are deferred to the full paper.

4.1 Reuse Strategies↩︎

ReBound treats reuse as a candidate derivation from cached DP releases and returns an answer at \(\Delta\varepsilon=0\) only when the requested utility bounds are met. For each HAVING atom \((\phi,\mathcal{F},\tau)\in\mathcal{A}\), it traverses cached predicate nodes \(\{P_i\}\) and scalar nodes \(\{A_i\}\) to derive a candidate by post-processing, propagates a \(\beta\) bound from the contributing releases, and then checks whether the induced false-positive guarantee satisfies \(\alpha\). If the \(\alpha\) check fails, ReBound runs ProBE [14]’s \(\alpha\)-guarantee step, spending incremental cost \(\varepsilon' \! >0\) to tighten the uncertainty region. We defer proofs of the propagation procedure and associated parameters to the full paper.

Exact Match. If the cache contains a release for the same atom \((\phi,\mathcal{F},\tau)\), ReBound reuses the corresponding scalar node \(S_i\) and its noisy value \(\widetilde{G}\) by post-processing. The candidate inherits \(\beta\) from the cached release, after which ReBound checks whether the induced \(\alpha\) meets the requested bound. If so, reuse is returned with \(\Delta\varepsilon=0\); otherwise, ReBound runs [14]’s \(\alpha\)-step starting from the cached state, incurring incremental cost \(\varepsilon'\) to satisfy \(\alpha\).

Threshold Change. For the same \((\phi,\mathcal{F})\) but a different threshold \(\tau'\), ReBound reuses the cached noisy scalar \(\widetilde{G}\) and recomputes the decision \(\mathbb{I}[\widetilde{G}>\tau']\) by post-processing. The propagated \(\beta\) bound transfers from the cached release (since it depends on the uncertainty region rather than the threshold), but the false-positive bound must be re-checked for \(\tau'\). If the \(\alpha\) requirement is not met, ReBound again spends incremental budget \(\varepsilon'\) to satisfy \(\alpha\) (or reuse is rejected).

Predicate Decomposition. If a requested predicate \(\phi\) can be expressed using cached predicate nodes \(\{P_i\}\) via set operations (e.g., union, intersection, set difference), ReBound derives the corresponding aggregate by combining the relevant cached scalars. For additive functions (COUNT, SUM), these set operations induce linear combinations of noisy scalars (e.g., disjoint unions sum). ReBound propagates \(\beta\) conservatively across the contributing releases and then checks whether the derived decision satisfies the requested \(\alpha\), after which it may again incur an incremental cost \(\varepsilon'\) to ensure the final FPR is bounded by \(\alpha\).

Linear Combination. If a requested aggregate can be expressed as a deterministic function of cached scalar nodes \(\{S_i\}\) (e.g., linear forms for additive aggregates like COUNT(x)+COUNT(y), or rewriting ratios like \(\texttt{AVG}=\texttt{SUM}/\texttt{COUNT}\)), ReBound derives the candidate value by post-processing and propagates \(\beta\) from its inputs by ensuring the combined aggregate uses the appropriate derived parameters (e.g. sensitivity and error region). The \(\alpha\) bound is then enforced on the combined aggregate result as a single threshold test, not on individual sub-queries.

4.2 Cache Structure↩︎

To efficiently identify reuse opportunities, the cache organizes prior releases as a three-layer DAG (Figure 2) reflecting query anatomy.

Layer 1: Predicate Index. Column nodes represent GROUP BY attributes; predicate nodes store intervals (numeric) or value sets (categorical). A boundary registry enables predicate decomposition.

Layer 2: Scalar Aggregates. Each scalar node (e.g., \(a_1\), \(a_2\), \(a_3\)) corresponds to a (predicate, function) pair and maintains releases under different \((c, \beta, \alpha, \varepsilon)\) parameters. Derived nodes (e.g., \(a_4 = a_1 + a_2\)) store derivation expressions and source references.

Layer 3: Boolean Composition. Represents compound HAVING clauses (AND/OR), enabling reuse under composition changes.

4.3 Query Processing↩︎

Algorithm 3 outlines query processing. Given an incoming query \(Q\) with utility requirements \(U=(\alpha,\beta)\) and budget limit \(\varepsilon_{\max}\), ReBound first parses \(Q\) into a canonical form capturing the GROUP BY key, a predicate set \(\Phi=\{\phi_i\}\), and a set of aggregate atoms \(\mathcal{A}=\{(\phi_i,\mathcal{F},\tau)\}\) used in the HAVING clause (lines 1–2), where \(\phi_i\) is a (group-level) selection predicate, \(\mathcal{F}\) denotes an aggregate function (e.g., COUNT), and \(\tau\) is the corresponding threshold. It then selects a reuse strategy \(S^*\) by traversing the cache DAG layer-by-layer (line 3). At the predicate layer, for each \(\phi\in\Phi\), the strategy checks whether its record set can be expressed using cached predicate nodes \(\{P_i\}\) via set operations (e.g., union or set difference), and records a concrete decomposition when possible. At the scalar-aggregate layer, for each requested atom in \(\mathcal{A}\), the strategy checks whether the required noisy scalar can be derived from cached aggregate nodes \(\{A_i\}\) by post-processing (e.g., \(\texttt{AVG}=\texttt{SUM}/\texttt{COUNT}\)). If the traversal yields a complete derivation, ReBound returns the answer via post-processing at \(\varepsilon=0\) (lines 4–5); otherwise it executes PROBE [14] for only the unresolved components according to \(S^*\), returning the final answer and realized cost \(\varepsilon_{\text{actual}}\) (line 6).

Negotiation. If \(\varepsilon_{\text{actual}} > \varepsilon_{\max}\), negotiation is triggered: the system offers relaxed accuracy bounds (either through minimal relaxation of \(\beta\) or through an effective upper bound \(\alpha\)) yielding lower \(\varepsilon\), which the analyst can accept or deny. Negotiation may also handle partial reuse: queries not fully matching any reuse case but partially derivable from the cache. We leave the formalization of the negotiation mechanism to the full paper.

Guarantee. ReBound guarantees that every query answer satisfies \(\varepsilon_{\max}\)-DP with a \(\beta\)-bound on FNR and \(\alpha\)-bound on FPR when possible. When the requested bounds cannot be achieved under \(\varepsilon_{\max}\)-DP, the negotiation framework suggests next best bounds \(\beta\) and \(\alpha\).

5 Preliminary Results↩︎

3pt

To evaluate ReBound, we construct analyst sessions inspired by OLAP session templates [20], where each query incrementally refines the previous one (e.g., drill-down, slice, or measure change). We instantiate two 10-query session patterns over the NYC Taxi dataset [21] (\(\sim\)​3 million trips from March 2020), grouping by hashed pickup location and using COUNT and AVG aggregates under varying predicates, thresholds, and utility targets. Table 2 summarizes the patterns: Pattern A (Drill-and-Tighten) progressively tightens \((\alpha,\beta)\) and then adjusts thresholds, while Pattern B (Exploratory Branching) pivots across predicates, aggregates, and linear combinations. We compare cumulative privacy cost under ReBound against a cache-less baseline using sequential composition, averaging results over 10 runs to account for Laplace noise.

Privacy Savings. Figure 4 shows cumulative privacy loss over each query session. ReBound achieves substantial savings by reusing cached releases: 75% reduction for Pattern A and 70% for Pattern B. The gap widens as sessions progress, proving that later queries benefit from richer cache state built by earlier queries. More importantly, these savings translate into longer interactive analysis sessions under fixed privacy budgets: under fixed session budgets, the baseline answers only 4 and 3 queries, respectively, while ReBound completes all 10 in both cases.

4pt

Negotiation. We evaluate bound-based negotiation (relaxing \(\alpha\) or \(\beta\)); partial reuse negotiation is left for future work. Without negotiation, Pattern A resulted in 12 query denials across 10 runs: Q7 was denied in 9/10 runs and Q9 in 3/10 runs, both requesting tight bounds (\(\beta = 0.005\), \(\alpha = 0.05\)) with all denials happening due to the \(\alpha\) bound. With negotiation enabled, all queries succeeded. The system offered relaxed \(\alpha\) bounds of 0.063 (Q7) and 0.054 (Q9), suggesting minor relaxations from the requested 0.05, while \(\beta\) remained effectively unconstrained under a \(\varepsilon_{\max} = 9\) budget.

6 Concluding Remarks↩︎

We presented ReBound, a cache-aware framework for interactive differentially private decision support. ReBound maintains a structured cache of prior DP releases and applies formally defined reuse conditions to answer follow-on queries via post-processing when possible, reducing incremental privacy loss and enabling more queries under a fixed budget; when reuse is insufficient, it negotiates accuracy-budget tradeoffs to maximize the answered workload. In future work, ReBound will be implemented as a fully fledged system with complete formal proofs for all reuse cases, optimized cache operations, and a complete negotiation framework. We also plan to extend ReBound to richer forms of partial reuse and negotiation, and to extend it to support different query types.

References↩︎