Not logged in.

Quick Search - Contribution

Contribution Details

Type Conference or Workshop Paper
Scope Discipline-based scholarship
Published in Proceedings Yes
Title Lattice histograms: a resilient synopsis structure
Organization Unit
Authors
  • P Karras
  • N Mamoulis
Editors
  • IEEE
Presentation Type paper
Item Subtype Original Work
Refereed Yes
Status Published in final form
Language
  • English
ISBN 978-1-4244-1836-7
Page Range 247 - 256
Event Title 24th International Conference on Data Engineering (ICDE 2008)
Event Type other
Event Location Cancun, Mexico
Event Start Date April 7 - 2008
Event End Date April 12 - 2008
Place of Publication Los Alamitos
Publisher IEEE
Abstract Text 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.
Related URLs
Digital Object Identifier 10.1109/ICDE.2008.4497433
Other Identification Number merlin-id:362
PDF File Download from ZORA
Export BibTeX
EP3 XML (ZORA)
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.