Please use this identifier to cite or link to this item:
|Title:||Local search in histogram construction|
|Authors:||Halim, F. |
|Source:||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 (www.aaai.org). All rights reserved.|
|Source Title:||Proceedings of the National Conference on Artificial Intelligence|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 9, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.