[Colloq] PhD Thesis Defense: Erick Robinson, Thursday, Nov. 30

[Rachel Kalweit]

College of Computer and Information Science
presents a PhD Thesis Proposal by:
Eric Robinson

Title:
Large Search Space Generation:  Overcoming Memory and Disk
Limitations

Thursday, November, 30  2006
9:00am
366 West Village H

Abstract

With bandwidth of both memory and disk increasing and latency stagnating 
or even becoming worse, the assumption that memory is faster than disk 
is no longer applicable when the access to memory is random and disk is 
streaming.

We look at the real-world problem of search space enumeration and review 
existing solution techniques where the search space being enumerated is 
too large for memory.  These techniques fall into a space-time search 
hierarchy where there is a natural tradeoff between the space used and 
the number of computations required for the search space enumeration 
technique.

One common characteristic of these existing techniques is that all of 
them emphasize using strictly either memory or disk in their solution 
and do not take advantage of of the other resource.  We offer a new 
approach that is able to outperform these methods in many instances by 
using both memory and disk.

Finally, we demonstrate the effectiveness of our method by showing 
real-world problems that were previously unsolved due to either lack of 
space or an infeasible run time.  Using our technique, we are able to 
enumerate these search spaces in a reasonable time.  In addition, we 
argue that given information about the enumeration to be performed and 
the resources available, one can directly determine the best enumeration 
technique to use.

Committee Members:
Gene Cooperman – advisor
Ron Williams
Ravi Sundaram
Jiri Schindler