The Haar+ Tree: a Refined Synopsis Data Structure

Speaker: Panagiotis Karras

Abstract

We introduce the Haar+ tree: a refined, wavelet-inspired data structure for synopsis construction. The advantages of this structure are twofold: First, it achieves higher synopsis quality at the task of summarizing data sets with sharp discontinuities than state-of-the-art histogram and Haar wavelet techniques. Second, thanks to its search space delimitation capacity, Haar+ synopsis construction operates in time _linear_ to the size of the data set for any monotonic distributive error metric. Through experimentation, we demonstrate the superiority of Haar+ synopses over histogram and Haar wavelet methods in both construction time and achieved quality for representative error metrics.