  Differentially-private (DP) databases allow for privacy-preserving analytics
over sensitive datasets or data streams. In these systems, user privacy is a
limited resource that must be conserved with each query. We propose Turbo, a
novel, state-of-the-art caching layer for linear query workloads over DP
databases. Turbo builds upon private multiplicative weights (PMW), a DP
mechanism that is powerful in theory but ineffective in practice, and
transforms it into a highly-effective caching mechanism, PMW-Bypass, that uses
prior query results obtained through an external DP mechanism to train a PMW to
answer arbitrary future linear queries accurately and "for free" from a privacy
perspective. Our experiments on public Covid19 and CitiBike datasets show that
Turbo with PMW-Bypass conserves 1.7-15.9x more budget compared to vanilla PMW
and simpler cache designs, a significant improvement. Moreover, Turbo provides
support for range query workloads, such as timeseries or streams, where
opportunities exist to further conserve privacy budget through DP parallel
composition and warm-starting of PMW state. Our work provides a theoretical
foundation and general system design for effective caching in DP databases.
