Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40709
Title: Local search in histogram construction
Authors: Halim, F. 
Karras, P. 
Yap, R.H.C. 
Issue Date: 2010
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
URI: http://scholarbank.nus.edu.sg/handle/10635/40709
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)

74
checked on Dec 9, 2017

Google ScholarTM

Check


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