Please use this identifier to cite or link to this item:
Title: Fast and effective histogram construction
Authors: Halim, F. 
Karras, P. 
Yap, R.H.C. 
Keywords: Efficiency
Issue Date: 2009
Citation: 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.
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
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.


checked on Oct 11, 2019

Page view(s)

checked on Oct 14, 2019

Google ScholarTM



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