lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Dawid Weiss (JIRA)" <>
Subject [jira] Commented: (LUCENE-2948) Make var gap terms index a partial prefix trie
Date Sat, 05 Mar 2011 20:23:46 GMT


Dawid Weiss commented on LUCENE-2948:

I reviewed the (second) patch. It seems all right, even if the logic of keeping those paths
is a bit complex at first (but I think I got it). I've been thinking about the questions stated
in the comments -- would it be possible to create a "better" pruning/ path keeping method.
I honestly don't think it is possible if you add terms incrementally to the FST because some
of the information required to keep or prune states is not available until the very end. 

One method I was thinking of was to determine "deep" subtrees of states with an approximately
equal size (and prune them entirely, or at least part of them). These "deep" subtrees (or
precalculated frozen states if you want to think of them this way) can be computed by sorting
reversed input sequences and calculating their LCP (longest common prefix) table -- then the
shared prefixes are actually suffixes of the input sequences... You can then linearly scan
such a reversed table and you'd know immediately how large a given subtree of suffixes is.
One problem is that this is exact only in state representation of the FST (in the edge/LAST
representation an input suffix can be integrated with a longer suffix, as you recall).

Since we're using edge-based representation I don't think the above idea helps much. Also,
it would require sorting the reversed terms and calculating an LCP table... this may be even
more costly than what is mentioned in the code comment -- use two passes, build an FSA  first,
determine nodes to prune and then build the final FST.

> Make var gap terms index a partial prefix trie
> ----------------------------------------------
>                 Key: LUCENE-2948
>                 URL:
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Index
>            Reporter: Michael McCandless
>            Assignee: Michael McCandless
>             Fix For: 4.0
>         Attachments: LUCENE-2948.patch, LUCENE-2948.patch, LUCENE-2948.patch, LUCENE-2948_automaton.patch
> Var gap stores (in an FST) the indexed terms (every 32nd term, by
> default), minus their non-distinguishing suffixes.
> However, often times the resulting FST is "close" to a prefix trie in
> some portion of the terms space.
> By allowing some nodes of the FST to store all outgoing edges,
> including ones that do not lead to an indexed term, and by recording
> that this node is then "authoritative" as to what terms exist in the
> terms dict from that prefix, we can get some important benefits:
>   * It becomes possible to know that a certain term prefix cannot
>     exist in the terms index, which means we can save a disk seek in
>     some cases (like PK lookup, docFreq, etc.)
>   * We can query for the next possible prefix in the index, allowing
>     some MTQs (eg FuzzyQuery) to save disk seeks.
> Basically, the terms index is able to answer questions that previously
> required seeking/scanning in the terms dict file.

This message is automatically generated by JIRA.
For more information on JIRA, see:


To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message