Data Management

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

Date Added: Mar 2011
Format: PDF

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.