Paper Info
Title
The Haar+ Tree: A Refined Synopsis Data Structure
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 synop- sis 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 de- limitation 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 his- togram and Haar wavelet methods in both construction time and achieved quality for representative error metrics.
Year
DOI
Venue
2007
10.1109/ICDE.2007.367889
Istanbul
Keywords
Field
DocType
Haar transforms,tree data structures,tree searching,wavelet transforms,Haar wavelet technique,Haar+ synopsis construction,Haar+ tree,refined synopsis data structure,search space delimitation capacity
Data structure,Histogram,Data set,Pattern recognition,Haar,Computer science,Tree (data structure),Algorithm,Artificial intelligence,Discrete wavelet transform,Haar wavelet,Wavelet transform
Conference
ISSN
ISBN
Citations 
1084-4627
1-4244-0802-4
12
PageRank 
References 
Authors
0.52
29
2
Name
Order
Citations
PageRank
Panagiotis Karras182451.33
Nikos Mamoulis24621263.82