  Differential privacy (DP) allows data analysts to query databases that
contain users' sensitive information while providing a quantifiable privacy
guarantee to users. Recent interactive DP systems such as APEx provide accuracy
guarantees over the query responses, but fail to support a large number of
queries with a limited total privacy budget, as they process incoming queries
independently from past queries. We present an interactive, accuracy-aware DP
query engine, CacheDP, which utilizes a differentially private cache of past
responses, to answer the current workload at a lower privacy budget, while
meeting strict accuracy guarantees. We integrate complex DP mechanisms with our
structured cache, through novel cache-aware DP cost optimization. Our thorough
evaluation illustrates that CacheDP can accurately answer various workload
sequences, while lowering the privacy loss as compared to related work.
