Permanent URL to this publication: http://dx.doi.org/10.5167/uzh-8935
Karras, P; Mamoulis, N (2008). Lattice histograms: a resilient synopsis structure. In: 24th International Conference on Data Engineering (ICDE 2008), Cancun, Mexico, 7 April 2008 - 12 April 2008, 247-256.
PDF (Original publication)
Despite the surge of interest in data reduction techniques over the past years, no method has been proposed to date that can always achieve approximation quality preferable
to that of the optimal plain histogram for a target error metric. In this paper, we introduce the Lattice Histogram: a novel data reduction method that discovers and exploits any arbitrary hierarchy in the data, and achieves approximation quality provably at least as high as an optimal histogram for any data reduction problem. We formulate LH construction techniques with approximation guarantees for general error metrics. We show that the case of minimizing a maximum-error metric can be solved by a specialized, memory-sparing approach; we exploit this solution to design reduced-space heuristics for the generalerror case. We develop a mixed synopsis approach, applicable to the space-efficient high-quality summarization of very large data sets. We experimentally corroborate the superiority of LHs in approximation quality over previous techniques with representative error metrics and diverse data sets.
|Item Type:||Conference or Workshop Item (Paper), refereed, original work|
|Communities & Collections:||03 Faculty of Economics > Department of Informatics|
|DDC:||000 Computer science, knowledge & systems|
|Event End Date:||12 April 2008|
|Deposited On:||09 Jan 2009 07:39|
|Last Modified:||28 Nov 2013 01:14|
|Additional Information:||This paper was presented at the 24th International Conference on Data Engineering (ICDE 2008), Cancun, Mexico, April 7 - 12, 2008. © 2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.|
|Citations:||Web of Science®|
Scopus®. Citation Count: 2
Users (please log in): suggest update or correction for this item
Repository Staff Only: item control page