💻 computer science

ReBound: Reuse-Aware Privacy For Interactive Decision Support

ReBound is a differentially private framework for interactive decision support that reduces or eliminates additional privacy costs by reusing cached results from previous queries through a novel cache graph structure and negotiation mechanism, while maintaining formal utility guarantees.

Original authors: Nada Lahjouji, Shufan Zhang, Xi He, Sharad Mehrotra

Published 2026-07-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nada Lahjouji, Shufan Zhang, Xi He, Sharad Mehrotra

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery using a very special, magical notebook. This notebook contains secrets about a city's population, but there's a catch: every time you write down a clue or ask a question about the data, the notebook adds a tiny bit of "static" or noise to the answer to protect the privacy of the people involved. This is the world of Differential Privacy, a method used by scientists and data analysts to learn from sensitive information without ever revealing who specifically is in the data. Think of it like asking a crowd of people, "How many of you like pizza?" but having everyone shout their answer at the same time so you can't tell who said what.

However, there's a problem with how we usually use these magical notebooks. Every time a detective asks a new question, even if it's just a tiny tweak to the last one, the notebook treats it as a brand-new, totally separate event. It adds a fresh layer of static and charges a "privacy fee" every single time. If a detective asks ten questions in a row, they might run out of their privacy budget (the total amount of static they are allowed to add) before they can finish their investigation. This makes interactive analysis—where you ask a question, look at the answer, and then ask a follow-up question—very expensive and inefficient. The big question is: Can we be smarter? Can we look at our previous answers and reuse them to answer new questions without paying the full price again?

This is exactly what the paper ReBound: Reuse-Aware Privacy For Interactive Decision Support explores. The authors, Nada Lahjouji, Shufan Zhang, Xi He, and Sharad Mehrotra, propose a new framework called ReBound. Instead of treating every question as a fresh start, ReBound acts like a super-smart librarian who remembers exactly what you asked before. It stores previous answers in a special "cache" (a memory bank) and figures out how to combine those old answers to solve new, related puzzles.

Here is how ReBound works in the real world of data:
Imagine you asked the notebook, "How many people have the flu?" and it gave you a noisy answer. Later, you want to ask, "How many people have the flu and a fever?" or "How many people have the flu if the threshold is 100 instead of 101?" In the old way, the system would ignore your first answer and start from scratch, adding more noise and charging more privacy fees. ReBound, however, looks at its memory. It sees that it already has the answer for "people with the flu." It can mathematically adjust that old answer to fit your new question without needing to look at the raw data again. This is called post-processing, and the best part is that it costs zero additional privacy fees.

The paper introduces a clever structure called a Cache Graph. Think of this as a multi-layered map.

Layer 1 is the map of the data itself (like "Age" or "City").
Layer 2 holds the specific numbers the notebook calculated (like "Count of people in NYC").
Layer 3 connects these numbers with logic (like "AND" or "OR").
When a new question arrives, ReBound doesn't just look for an exact match; it scans this map to see if the new question can be built out of the pieces it already has. It can handle changes in thresholds (changing the number you're comparing against), tightening the rules (asking for a more precise answer), or even combining different types of data (like adding two counts together).

But what if the new question is too hard to answer with just the old pieces? That's where the Negotiation feature comes in. Instead of just saying "No, I can't answer that because I'm out of privacy money," ReBound acts like a friendly negotiator. It says, "I can't give you that super-precise answer right now, but I can give you a slightly less precise one that fits within your budget." This allows the analyst to keep working rather than hitting a dead end.

The researchers tested this idea using a dataset of NYC Taxi trips (about 3 million trips). They created two types of detective sessions:

Drill-and-Tighten: Asking the same question but making the rules stricter and stricter.
Exploratory Branching: Asking questions that branch out into new areas or combine different metrics.

The results were quite promising. In their simulations, ReBound reduced the total privacy cost by 75% for the "Drill-and-Tighten" sessions and 70% for the "Branching" sessions compared to the old method. To put that in perspective: with a fixed privacy budget, the old method could only answer 4 out of 10 questions in one scenario and 3 out of 10 in another. ReBound, however, managed to answer all 10 questions in both cases.

The paper also looked at what happens when the budget is tight. Without the negotiation feature, the system had to deny about 12 queries across 10 test runs because the requested precision was too high for the remaining budget. But when ReBound was allowed to negotiate and suggest slightly relaxed rules, all queries succeeded.

In short, ReBound suggests that we don't have to waste our privacy budget on questions we've already almost answered. By remembering the past and reusing it smartly, we can ask more questions, get deeper insights, and keep our data safe for longer. While the paper presents these findings as strong simulation results and a proposed framework, it notes that a fully implemented system with all the formal proofs is still a work in progress. But the core idea is clear: in the world of privacy-preserving data analysis, memory is power, and reusing what you know is the key to unlocking more answers.

Technical Summary: ReBound – Reuse-Aware Privacy for Interactive Decision Support

Problem Statement

Complex decision support (DS) queries, which involve multiple aggregate conditions (e.g., "COUNT(Flu) > 100 AND AVG(Temp) > 101"), are fundamental to applications in clinical diagnosis, building management, and KPI evaluation. These queries often operate on sensitive data, necessitating Differential Privacy (DP) to prevent information leakage. However, standard DP mechanisms introduce noise that can degrade decision quality, leading to False Positives (FP) and False Negatives (FN).

Existing "utility-first" frameworks (e.g., APEx, MIDE, ProBE) provide formal guarantees on False Negative Rates (FNR) and False Positive Rates (FPR) by optimizing privacy budgets to meet specific utility targets. However, a critical limitation of these systems is that they treat every query as an independent event. In practice, analysts work interactively, issuing sequences of related queries to refine bounds, adjust thresholds, or derive new functions. Under current paradigms, each refinement incurs a full privacy cost, causing the cumulative privacy budget to deplete linearly with the number of interactions, even when successive queries share significant overlap.

The core problem addressed is how to systematically reuse cached results from previous differentially private queries to answer new, related queries with reduced or zero additional privacy cost, while maintaining formal FNR and FPR guarantees.

Methodology: The ReBound Framework

ReBound is a framework designed to bridge the gap between static DP mechanisms and interactive analyst workflows. It operates on three core principles: post-processing reuse, utility propagation, and budget-aware negotiation.

1. Reuse Strategies

ReBound identifies four distinct types of query refinements and applies specific derivation strategies for each, ensuring that the derived answers satisfy the requested utility bounds ( $\alpha$ for FPR, $\beta$ for FNR):

Exact Match: If the cache contains a release for the exact same atomic query, the system reuses the noisy scalar value. The $\beta$ bound is inherited directly. The system then checks if the induced $\alpha$ (FPR) meets the request; if not, it runs a minimal $\alpha$ -tightening step (using the ProBE mechanism) incurring only incremental cost.
Threshold Change: For the same query with a different threshold, ReBound reuses the cached noisy scalar and recomputes the decision via post-processing. The $\beta$ bound transfers because it depends on the uncertainty region, not the threshold. The $\alpha$ bound is re-verified; if it fails, an incremental cost is incurred to tighten the region.
Predicate Decomposition: If a requested predicate can be expressed as a set operation (union, intersection, difference) of cached predicates, ReBound combines the relevant cached scalars. For additive functions (COUNT, SUM), this involves linear combinations of noisy scalars. The system conservatively propagates $\beta$ and verifies $\alpha$ .
Linear Combination: For aggregates expressible as deterministic functions of cached scalars (e.g., $AVG = SUM/COUNT$ or $COUNT(x) + COUNT(y)$), ReBound derives the candidate value via post-processing. The $\beta$ bound is propagated based on the sensitivity and error regions of the inputs, and the final $\alpha$ is enforced on the combined result.

2. Cache Structure

To facilitate efficient lookup and derivation, ReBound employs a three-layer Directed Acyclic Graph (DAG) cache:

Layer 1 (Predicate Index): Stores column nodes and predicate nodes (intervals for numeric, value sets for categorical). This layer supports predicate decomposition.
Layer 2 (Scalar Aggregates): Stores nodes corresponding to (predicate, function) pairs. Each node maintains releases under various parameters ( $c, \beta, \alpha, \epsilon$ ) and supports derived nodes (e.g., $a_4 = a_1 + a_2$ ) that store derivation expressions.
Layer 3 (Boolean Composition): Represents compound HAVING clauses (AND/OR), enabling reuse when the logical structure of a query changes.

3. Query Processing and Negotiation

When a new query arrives, ReBound parses it into a canonical form and traverses the cache DAG to select a reuse strategy.

If a complete derivation is found, the answer is returned with $\Delta\epsilon = 0$ .
If only partial reuse is possible, the system executes the ProBE mechanism only for the unresolved components.
Negotiation Mechanism: If the required utility bounds cannot be met within the remaining privacy budget ( $\epsilon_{max}$ ), the system does not simply deny the query. Instead, it proposes a counteroffer with relaxed bounds (e.g., a slightly higher $\alpha$ or $\beta$ ) that can be satisfied within the budget, allowing the analyst to accept a meaningful trade-off.

Key Contributions

Reuse Framework for DS Queries: Unlike prior work focused on numerical error bounds or linear workloads, ReBound introduces a framework specifically for threshold-classification queries where utility is defined by predicate-wise FNR/FPR. It supports multiple refinement types (thresholds, bounds, logical structure, linear combinations).
Hierarchical Cache Design: The paper proposes a novel three-layer DAG structure that stores not just final answers but also intermediate results and composed sub-expressions. This maximizes reuse opportunities even when the overall query structure changes.
Privacy Negotiation: The system introduces a mechanism to handle infeasible requests by offering minimal relaxations of accuracy bounds, preventing outright query denial and maximizing the workload under fixed budgets.

Preliminary Results

The authors evaluated ReBound using analyst session patterns over the NYC Taxi dataset (approx. 3 million trips). Two patterns were tested:

Pattern A (Drill-and-Tighten): Progressively tightening accuracy bounds and adjusting thresholds.
Pattern B (Exploratory Branching): Pivoting across predicates, aggregates, and linear combinations.

Findings:

Privacy Savings: ReBound achieved a 75% reduction in cumulative privacy loss for Pattern A and 70% for Pattern B compared to a baseline with no reuse.
Query Throughput: Under fixed privacy budgets, the baseline system could only answer 4 out of 10 queries (Pattern A) and 3 out of 10 (Pattern B). ReBound successfully answered all 10 queries in both patterns.
Negotiation Efficacy: In scenarios where strict bounds led to query denials (e.g., 12 denials across 10 runs for Pattern A without negotiation), enabling negotiation allowed all queries to succeed by offering minor relaxations (e.g., adjusting $\alpha$ from 0.05 to 0.063).

Significance and Claims

The paper claims that ReBound addresses the inefficiency of treating interactive decision support queries as independent events. By systematically reusing cached results, ReBound enables significantly longer and more complex interactive analysis sessions under fixed privacy budgets. The framework maintains formal utility guarantees (FNR/FPR) while minimizing incremental privacy loss.

The authors note that the current work presents the framework and preliminary results, with formal proofs for all reuse cases, optimized cache operations, and a complete negotiation framework reserved for future implementation in a fully fledged system. They also plan to extend the system to support richer forms of partial reuse and additional query types.