Fast and Accurate Computation of Equi-Depth Histograms Over Data Streams

Equi-depth histograms represent a fundamental synopsis widely used in both database and data stream applications, as they provide the cornerstone of many techniques such as query optimization, approximate query answering, distribution fitting, and parallel database partitioning. Equi-depth histograms try to partition a sequence of data in a way that every part has the same number of data items. In this paper, the authors present a new algorithm to estimate equi-depth histograms for high speed data streams over sliding windows.

Provided by: Association for Computing Machinery Topic: Data Management Date Added: Mar 2011 Format: PDF

Find By Topic