Please use this identifier to cite or link to this item:
Title: Local search in histogram construction
Authors: Halim, F. 
Karras, P. 
Yap, R.H.C. 
Issue Date: 2010
Citation: Halim, F., Karras, P., Yap, R.H.C. (2010). Local search in histogram construction. Proceedings of the National Conference on Artificial Intelligence 3 : 1680-1685. ScholarBank@NUS Repository.
Abstract: The problem of dividing a sequence of values into segments occurs in database systems, information retrieval, and knowl edge management. The challenge is to select a finite number of boundaries for the segments so as to optimize an objective error function defined over those segments. Although this optimization problem can be solved in polynomial time, the algorithm which achieves the minimum error does not scale well, hence it is not practical for applications with massive data sets. There is considerable research with numerous approximation and heuristic algorithms. Still, none of those approaches has resolved the quality-efficiency tradeoff in a satisfactory manner. In (Halim, Karras, and Yap 2009), we obtain near linear time algorithms which achieve both the desired scalability and near-optimal quality, thus dominating earlier approaches. In this paper, we show how two ideas from artificial intelligence, an efficient local search and recombination of multiple solutions reminiscent of genetic algorithms, are combined in a novel way to obtain state of the art histogram construction algorithms. Copyright © 2010, Association for the Advancement of Artificial Intelligence ( All rights reserved.
Source Title: Proceedings of the National Conference on Artificial Intelligence
ISBN: 9781577354666
Appears in Collections:Staff Publications

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

Page view(s)

checked on Sep 9, 2019

Google ScholarTM



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