Bruce D'Ambrosio wrote:
> Finally, there is always Adnan Darwiche's space-time tradeoff algorithm
> that will compute an exact answer to almost anything if you have
> enough time - although I don't know if there are good implementations (Adnan?),
> and no-one has enough time to compensate for a bad factoring
> (elimination order)
I received a number of questions about the algorithm that Bruce
mentioned above, so here is a summary:
The algorithm is called "Recursive Conditioning (RC)." It appeared
recently (February) in the AIJ special issue on Computational
Tradeoffs under Bounded Resources:
http://research.microsoft.com/~horvitz/AIJ_editorial.htm
The techincal report is available at
http://www.cs.ucla.edu/~darwiche/rc-aij.ps
The algorithm allows one to use less space than that needed by
classical algorithms, such as jointree, but at the expense of taking
more time. It is "anyspace" in the sense that it can run under any
amount of space you make available to it. It allows "smooth"
time-space tradeoff as you can trade space at the increment of
X-bytes, where X is the number of bytes needed to store a floating
point number in a cache. One can also predict the running time of the
algorithm under different amounts of space. The algorithm is then
helpful if "space" is the bottleneck instead of "time."
There is no publically available implementation at this stage, but I
am planning to make one available later this summer.
Adnan
This archive was generated by hypermail 2b29 : Tue May 15 2001 - 12:48:25 PDT