File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Lattice histograms: A resilient synopsis structure

TitleLattice histograms: A resilient synopsis structure
Authors
Issue Date2008
Citation
Proceedings - International Conference On Data Engineering, 2008, p. 247-256 How to Cite?
AbstractDespite 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 general-error 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. © 2008 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/151928
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorKarras, Pen_US
dc.contributor.authorMamoulis, Nen_US
dc.date.accessioned2012-06-26T06:30:57Z-
dc.date.available2012-06-26T06:30:57Z-
dc.date.issued2008en_US
dc.identifier.citationProceedings - International Conference On Data Engineering, 2008, p. 247-256en_US
dc.identifier.issn1084-4627en_US
dc.identifier.urihttp://hdl.handle.net/10722/151928-
dc.description.abstractDespite 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 general-error 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. © 2008 IEEE.en_US
dc.languageengen_US
dc.relation.ispartofProceedings - International Conference on Data Engineeringen_US
dc.titleLattice histograms: A resilient synopsis structureen_US
dc.typeConference_Paperen_US
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_US
dc.identifier.authorityMamoulis, N=rp00155en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1109/ICDE.2008.4497433en_US
dc.identifier.scopuseid_2-s2.0-52649100982en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-52649100982&selection=ref&src=s&origin=recordpageen_US
dc.identifier.spage247en_US
dc.identifier.epage256en_US
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridKarras, P=14028488200en_US
dc.identifier.scopusauthoridMamoulis, N=6701782749en_US
dc.identifier.citeulike4621723-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats