The Haar+ Tree: A Refined Synopsis Data Structure
Panagiotis Karras, Nikos Mamoulis · 2007
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.