lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Uwe Schindler (JIRA)" <j...@apache.org>
Subject [jira] Commented: (LUCENE-2230) Lucene Fuzzy Search: BK-Tree can improve performance 3-20 times.
Date Wed, 10 Feb 2010 16:37:28 GMT

    [ https://issues.apache.org/jira/browse/LUCENE-2230?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12832055#action_12832055
] 

Uwe Schindler commented on LUCENE-2230:
---------------------------------------

Hi Fuad,

Ok thanks for the explanation about the cache. But there should still be some eviction algorithm
or at least a WeakHashmap so the JVM can cleanup the cache for unused fields. My problem with
IndexReaders missing in the cache logic was that if you reopen the index, the BKTree contains
terms no longer available and the FuzzyTermEnum enumerates terms that are no longer available.
This is bad parctise and should not be done in query rewrite. So enumerating terms with no
relation to a real term dict is not really supported by MultiTermQuery, but works for fuzzy,
because it does not use the low level segment-based term enumeration and linkage to TermDocs.

The new LUCENE-2258 issue needs no warmup, as it uses a different algorithm for the Levenstein
algorithm and also does not scan the whole term dict. By the way, in flex also RegEx queries
and Wildcard queries are speed up. The problem with trunk not having this automaton package
used for that is the problem, that the AutomatonTermsEnum used for that needs to do lots of
seeking in the TermsEnum, which is improved in flex and we do not want to do the work twice.

Flex has a completely different API on the enum side, so TermEnumerations work different and
so on.

> Lucene Fuzzy Search: BK-Tree can improve performance 3-20 times.
> ----------------------------------------------------------------
>
>                 Key: LUCENE-2230
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2230
>             Project: Lucene - Java
>          Issue Type: Improvement
>    Affects Versions: 3.0
>         Environment: Lucene currently uses brute force full-terms scanner and calculates
distance for each term. New BKTree structure improves performance in average 20 times when
distance is 1, and 3 times when distance is 3. I tested with index size several millions docs,
and 250,000 terms. 
> New algo uses integer distances between objects.
>            Reporter: Fuad Efendi
>         Attachments: BKTree.java, Distance.java, DistanceImpl.java, FuzzyTermEnumNEW.java,
FuzzyTermEnumNEW.java
>
>   Original Estimate: 0.02h
>  Remaining Estimate: 0.02h
>
> W. Burkhard and R. Keller. Some approaches to best-match file searching, CACM, 1973
> http://portal.acm.org/citation.cfm?doid=362003.362025
> I was inspired by http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
(Nick Johnson, Google).
> Additionally, simplified algorythm at http://www.catalysoft.com/articles/StrikeAMatch.html
seems to be much more logically correct than Levenstein distance, and it is 3-5 times faster
(isolated tests).
> Big list od distance implementations:
> http://www.dcs.shef.ac.uk/~sam/stringmetrics.htm

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Mime
View raw message