Abstract
Differential Privacy (DP) is the gold standard for protecting individual privacy in data analysis, yet its adoption is hindered by the complexity of tuning the privacy budget ($\epsilon$). We present APEx, a system that allows data analysts to specify desired accuracy $(\alpha, \beta)$ rather than privacy parameters. APEx automatically selects the most privacy-efficient algorithm to meet these bounds across various primitives, including Iceberg and Top-k queries. Our evaluation on real-world datasets like NYTaxi and US Census data demonstrates that APEx can reduce privacy budget consumption by over 90% compared to standard baselines, making private data exploration accessible to non-experts.
Introduction
Data scientists frequently explore sensitive datasets to identify distributions, frequent patterns (Iceberg queries), or top records (Top-k queries). While Differential Privacy provides rigorous guarantees, it presents a significant usability hurdle: analysts must decide how to "spend" a mathematical privacy budget. Spending too little leads to noisy, useless results, while spending too much exhausts the budget prematurely. APEx addresses this by providing an "accuracy-aware" interface where the system handles the complex translation from accuracy requirements to privacy parameters.
The APEx Architecture
APEx introduces a novel architecture consisting of three core components designed to simplify the DP workflow:
- Declarative Query Language: A SQL-like syntax supporting Workload Counting (WCQ), Iceberg Counting (ICQ), and Top-k Counting (TCQ). Every query includes an accuracy requirement $(\alpha, \beta)$, where the error is guaranteed to be less than $\alpha$ with a confidence level of $1-\beta$.
- Accuracy Translator: This engine takes the accuracy request and calculates the required $\epsilon$ for various candidate DP mechanisms, selecting the one with the least privacy loss. It utilizes standard Laplace mechanisms, advanced strategy-based (Matrix) mechanisms, and a novel Multi-Poking (ICQ-MPM) approach.
- Privacy Analyzer: This component tracks the cumulative privacy budget across adaptive queries, ensuring that the global privacy guarantee defined by the data owner is never violated.
Query Primitives and Error Semantics
To support data cleaning and exploration, APEx focuses on three primary counting primitives. The accuracy bounds $(\alpha, \beta)$ are interpreted specifically for each query type to ensure results are useful for downstream tasks.
As shown in the figure above, for an Iceberg Counting Query (ICQ), the system ensures that items significantly above or below the threshold $c$ are correctly labeled with high probability. For Top-k Counting Queries (TCQ), the bounds ensure that the returned set correctly includes items that are truly in the top-k, within the specified margin $\alpha$.
Key Mechanisms and Insights
A central innovation in APEx is the Multi-Poking mechanism (ICQ-MPM). This data-dependent approach "pokes" the data with a minimal privacy budget to determine if a count is far from the threshold. If the value is clearly distant, the system can return a high-confidence answer very cheaply. This "privacy for cheap" approach is particularly effective when data is not "on the edge" of a threshold.
Furthermore, APEx demonstrates that no single DP algorithm is optimal for every query. By dynamically choosing between Laplace, Matrix, and Multi-Poking mechanisms, APEx often saves over 90% of the privacy budget compared to a one-size-fits-all approach.
Evaluation and Results
The authors evaluated APEx using the Adult Dataset (US Census), the NYTaxi Dataset (9.7 million records), and a Citations Dataset for entity resolution case studies.
- Efficiency: On the NYTaxi dataset, APEx answered queries with high accuracy while consuming a negligible privacy budget ($\epsilon < 0.001$).
- Optimization: For cumulative histogram queries, specialized strategy-based mechanisms were 20x more efficient than the Laplace baseline.
- Utility: In data cleaning scenarios, APEx enabled analysts to build high-quality models (high F1 scores) while remaining within strict total privacy budgets.
Limitations and Future Work
While APEx significantly lowers the barrier to entry for DP, it currently focuses primarily on COUNT-based queries. Future extensions could deepen support for SUM, AVG, and MEDIAN. Additionally, the current error analysis relies on conservative union bounds, which may occasionally over-estimate the required $\epsilon$. Future iterations may include a "recommender" system to suggest follow-up queries and an "inferencer" to reuse previous results, further stretching the privacy budget.
Summary updated