Compressing Pattern Databases
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Ram Meshulam, Computer Science, Bar-Ilan University, Israel
- Robert Holte, Department of Computing Science, University of Alberta
- Richard E. Korf, Computer Science Department, University of California
A pattern database is a heuristic function stored as a lookup table which stores the lengths of optimal solu tions for instances of subproblems. All previous pat tern databases had a distinct entry in the table for each subproblem instance. In this paper we investigate com pressing pattern databases by merging several adjacent entries into one, thereby allowing the use of pattern databases that exceed available memory in their uncom pressed form. We show that since adjacent entries are highly correlated, much of the information is preserved. Experiments on the sliding tile puzzles and the 4peg Towers of Hanoi puzzle show that, for a given amount of memory, search time is reduced by up to 3 orders of magnitude by using compressed pattern databases.
Citation
A. Felner, R. Meshulam, R. Holte, R. Korf. "Compressing Pattern Databases". National Conference on Artificial Intelligence (AAAI), San Jose, California, USA, pp 638-643, March 2004.Keywords: | compressing, databases |
Category: | In Conference |
BibTeX
@incollection{Felner+al:AAAI04, author = {Ariel Felner and Ram Meshulam and Robert Holte and Richard E. Korf}, title = {Compressing Pattern Databases}, Pages = {638-643}, booktitle = {National Conference on Artificial Intelligence (AAAI)}, year = 2004, }Last Updated: June 04, 2007
Submitted by Staurt H. Johnson