Histograms Revisited: When are histograms the best approximation method for aggregates over Alin Dobra   View Paper (PDF)   Return to Research Session 6: Complexity and Performance Evaluation / Data Stream Abstract The traditional statistical assumption for interpreting histograms and justifying approximate query processing methods based on them is that all elements in a bucket have the same frequency - the so called uniform distribution assumption. In this paper we show that a significantly less restrictive statistical assumption - the elements within a bucket are randomly arranged even though they might have different frequencies - leads to identical formulae for approximating aggregate queries using histograms. This observation allows us to identify scenarios in which histograms are well suited as approximation methods - in fact we show that in these situations sampling and sketching are significantly worse - and provide tight error guarantees for the quality of approximations. At the same time we show that, on average, histograms are rather poor approximators outside these scenarios. ©2006 Association for Computing Machinery