Please use this identifier to cite or link to this item: https://doi.org/10.1145/1645953.1646101
Title: Fast and effective histogram construction
Authors: Halim, F. 
Karras, P. 
Yap, R.H.C. 
Keywords: Efficiency
Histograms
Segmentation
Issue Date: 2009
Source: Halim, F.,Karras, P.,Yap, R.H.C. (2009). Fast and effective histogram construction. International Conference on Information and Knowledge Management, Proceedings : 1167-1176. ScholarBank@NUS Repository. https://doi.org/10.1145/1645953.1646101
Abstract: Histogram construction or sequence segmentation is a basic task with applications in database systems, information retrieval, and knowledge management. Its aim is to approximate a sequence by line segments. Unfortunately, the quadratic algorithm that derives an optimal histogram for Euclidean error lacks the desired scalability. Therefore, sophisticated approximation algorithms have been recently proposed, while several simple heuristics are used in practice. Still, these solutions fail to resolve the efficiency-quality tradeoff in a satisfactory manner. In this paper we take a fresh view on the problem. We propose conceptually clear and scalable algorithms that efficiently derive high-quality histograms. We experimentally demonstrate that existing approximation schemes fail to deliver the desired efficiency and conventional heuristics do not fare well on the side of quality. On the other hand, our schemes match or exceed the quality of the former and the efficiency of the latter. Copyright 2009 ACM.
Source Title: International Conference on Information and Knowledge Management, Proceedings
URI: http://scholarbank.nus.edu.sg/handle/10635/40707
ISBN: 9781605585123
DOI: 10.1145/1645953.1646101
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

5
checked on Dec 11, 2017

Page view(s)

51
checked on Dec 16, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.