Re: [Seqan-dev] Best index for task

[John Reid <j.reid@mail.cryst.bbk.ac.uk>]

On 24/03/11 11:00, seqan-dev-request@lists.fu-berlin.de wrote:
> Hi John,
>
> you descend in the suffix tree using a TopDown iterator? IndexEsa, IndexWotd and IndexDfi  are the only indices that supports the suffix tree interface. IndexDfi is certainly not what you want, except you are mining strings with a certain frequency. In our applications it turned out that using the Wotd-Index for iterating only parts of the suffix array is much faster than constructing the whole enhanced suffix array (SA,LCP,ChildTab) as the ESA-Index does. So without knowing the details of your problem I would recommend the IndexWotd. The q-gram Index only supports searching for occurrences of certain q-grams without providing a suffix tree interface. However, a q-gram Index is the fastest index to retrieve occurrences of substring up to length q.
>
> Hope that helps,
> David

Hi David,

Your response (and the other 2) certainly help. I'm going to try the 
WOTD index. In any given execution my application does traverse the 
entire tree to a certain depth but it makes many top-down descents and 
each of these may only visit parts of the tree. In any case I think it 
is always worth testing data structures to see which is quickest in 
practice so I'll do that.

Thanks,
John.