Not Logged In

A Space-Time Tradeoff for Memory-Based Heuristics

A memory­based heuristic is a function, h(s), stored in the form of a lookup table (pattern database): h(s) is computed by mapping s to an index and then retrieving the appropriate entry in the table. (Korf 1997) conjectures for search using memory­based heuristics that m Delta t is a constant, where m is the size of the heuristic's lookup ta­ ble and t is search time. In this paper we present a method for automatically generating memory­ based heuristics and use this to test Korf's con­ jecture in a large­scale experiment. Our results confirm that there is a direct relationship between m and t.

Citation

R. Holte, I. Hernadvolgyi. "A Space-Time Tradeoff for Memory-Based Heuristics". National Conference on Artificial Intelligence (AAAI), Orlando, Florida, pp 704-709, January 1999.

Keywords: space-time, tradeoff, machine learning
Category: In Conference

BibTeX

@incollection{Holte+Hernadvolgyi:AAAI99,
  author = {Robert Holte and Istvan Hernadvolgyi},
  title = {A Space-Time Tradeoff for Memory-Based Heuristics},
  Pages = {704-709},
  booktitle = {National Conference on Artificial Intelligence (AAAI)},
  year = 1999,
}

Last Updated: June 18, 2007
Submitted by Staurt H. Johnson

University of Alberta Logo AICML Logo