DAQ: A New Paradigm for Approximate Query Processing
Outline
Approximate Query Processing
SAQ Sampling-based Approximate Querying
Confidence Intervals
SAQ: Shortcomings
DAQ Deterministic Approximate Querying
SAQ vs DAQ (at a glance)
Conceptual DAQ Scheme
Interval Algebra
Formal Definition
Bitwise DAQ Scheme
Bitwise DAQ Scheme Algorithms
Bitwise DAQ vs. Baseline
Bitwise DAQ Summary
Future Work

SAQ Sampling-based Approximate Querying

Run query on a small random subset of data

Error in estimate presented as confidence intervalAvg revenue = $12.3 ± 0.1 million with 95% confidence

Can be “online”
error eventually shrinks to zero => exact estimate