Abstract | ||
---|---|---|
The constructions of Haar wavelet synopses for large data sets have proven to be useful tools for data approximation. Recently, research on constructing wavelet synopses with a guaranteed maximum error has gained attention. Two relevant problems have been proposed: One is the size bounded problem that requires the construction of a synopsis of a given size to minimize the maximum error. Another is the error bounded problem that requires a minimum sized synopsis be built to satisfy a given error bound. The optimum algorithms for these two problems take O(N2) time complexity. In this paper, we provide new algorithms for building error-bounded synopses. We first provide several property-based pruning techniques, which can greatly improve the performance of optimal error bounded synopses construction. We then demonstrate the efficiencies and effectiveness of our techniques through extensive experiments. |
Year | Venue | Keywords |
---|---|---|
2007 | APWeb/WAIM | size bounded problem,building data synopsis,maximum error,large data set,optimal error,synopses construction,error bounded problem,data approximation,haar wavelet synopsis,error-bounded synopsis,guaranteed maximum error,time complexity,satisfiability |
Field | DocType | Volume |
Data mining,Data set,Computer science,Maximum error,Data approximation,Artificial intelligence,Time complexity,Wavelet,Tree (data structure),Algorithm,Haar wavelet,Machine learning,Bounded function | Conference | 4505 |
ISSN | Citations | PageRank |
0302-9743 | 4 | 0.45 |
References | Authors | |
13 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Chaoyi Pang | 1 | 316 | 43.45 |
Qing Zhang | 2 | 567 | 25.85 |
David Hansen | 3 | 26 | 2.97 |
Anthony Maeder | 4 | 24 | 3.23 |