Please use this identifier to cite or link to this item:
|dc.title||Fast and effective histogram construction|
|dc.identifier.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. https://doi.org/10.1145/1645953.1646101|
|dc.description.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.|
|dc.description.sourcetitle||International Conference on Information and Knowledge Management, Proceedings|
|Appears in Collections:||Staff Publications|
Show simple item record
Files in This Item:
There are no files associated with this item.
checked on Oct 11, 2019
checked on Oct 14, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.