  We study the problem of space and time efficient evaluation of a
nonparametric estimator that approximates an unknown density. In the regime
where consistent estimation is possible, we use a piecewise multivariate
polynomial interpolation scheme to give a computationally efficient
construction that converts the original estimator to a new estimator that can
be queried efficiently and has low space requirements, all without adversely
deteriorating the original approximation quality. Our result gives a new
statistical perspective on the problem of fast evaluation of kernel density
estimators in the presence of underlying smoothness. As a corollary, we give a
succinct derivation of a classical result of Kolmogorov---Tikhomirov on the
metric entropy of H\"{o}lder classes of smooth functions.
