[Colloq] PhD Thesis Proposal: Eric 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


_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq