University:
Boston University
Course:
MET CS 201 | Introduction to Programming
Academic year:

2022
Views:

280

Pages:

21
Author:

Patricia West

Related Work Data Aware Take advantage of the distribution of the bin values Data Oblivious Oblivious to the bin values 8 Related Work Data Aware Data Oblivious Smoothing 8 Related Work Data Aware Data Oblivious Smoothing Group and average consecutive bins before the LPA • Reduces the sensitivity of the grouped bins • Reduces the required noise • Introduces approximation error 8 Related Work Data Aware Data Oblivious Smoothing Group and average consecutive bins before the Find the best way to merge the bins LPA • Explore all possible groups (count: O(n2)) • Reduces the sensitivity of the grouped bins • Choose the groups that minimize the total error of the approximation and the • Reduces the required noise noise addition • Introduces approximation error 8 Related Work Data Aware Smoothing Data Oblivious Hierarchical Build an aggregate tree over the bins – each node holds the sum of its children • Sensitivity: logn • Compute range using the sub-‐trees that contain the query 8 Related Work Data Aware Smoothing Data Oblivious Hierarchical Workload Aware Given the range queries • Add noise with different scale to each query answer • Combine query answers that have overlaps to get more accurate results Applies to our setting by fixing all possible range queries 8 Modular Approach: Motivation • Every method can be decomposed into primitive components/modules • Benefits – Better understanding of each technique – Easy to discover performance bottlenecks and apply optimizations – Easy to combine different components to design new methods that benefit from the merits of different approaches 9 Modules Data Aware Smoothing Data Oblivious Hierarchical Workload Aware 10 Modules Smoothing Hierarchical Workload Aware Every existing method can be reproduced from these modules by parameterizing them 10 New Scheme: Subtree Smoothing • Combine the merits of Hierarchical and Smoothing Fast (O(n)); accurate for large ranges Slow (O(n2)); accurate for small ranges 11 New Scheme: Subtree Smoothing 12 New Scheme: Subtree Smoothing • Prune subtrees with similar values 12 New Scheme: Subtree Smoothing • Approximate the pruned nodes from the subtree root 12 New Scheme: Subtree Smoothing queries Smoothing Hierarchical Query Processor answers • Very fast method (O(n)) • Data-‐aware (applies smoothing) • Accurate for large ranges (utilizes tree structure) 13 New Scheme: Smoothed Prefix Sums • Combine the merits of Smoothing and Workload Aware Workload Aware Accurate for small ranges Very accurate; very slow (O(n3logn)) 14 New Scheme: Smoothed Prefix Sums • Setting all possible queries (O(n2)) as input to Workload Aware schemes, their running time is prohibitive • Instead, use the prefix sums – P[1]=h[1], P[2]=h[1]+h[2], …, P[n]=h[1]+…+h[n] – O(n) possible queries – Any range can be computed by subtracting two prefix sums 15 New Scheme: Smoothed Prefix Sums P Smoothing queries Workload Aware Query Processor answers Running time of Workload Aware drops by an n factor (O(n2logn)) 15 Experiments • Compare all new methods and previous ones that are not subsumed by others Scheme Abv. Time Laplace Perturbation Algorithm LPA O(n) Hierarchical H O(n) Smoothing S1, S2, So, Ŝ O(n2logn), O(n2), O(n2), O(nlog2n) Subtree Smoothing SUB O(n) Smoothed Prefix Sums SPS O(n2logn) 16 Net (64K bins) Error vs range Skyline – small ranges Skyline – large ranges 17 Rome (14K bins) Error vs range Skyline – small ranges Skyline – large ranges 18 Challenges • Modularize differentially private methods for other settings • Is it possible to combine differentially private modules with cryptographic modules? • Differential Privacy + Cryptography = ? 19