• Description of LCA
• The use of LCA
• Trivial solution n^2
• Better solutions
• This Project

• Brief overview
• more info here

• Brief overview
• more info here

• Perl for Bender
• C++ for vishkin
• Library with sample drivers
• To do: mpich

With some simple dynamic programming we can turn the O(n^3) into an O(n^2) but that is still not good enough.

We want the fastest solution possible, in fact, a solution that runs in linear time would be best. Our goal is to preprocess our dataset in O(n) to provide O(1) lookups.
This is the underlying reason behind this project. A tool which allows us to process data, and run queries against it, all as fast as possible.

[previous slide]   [next slide]