Mailing-List: contact java-dev-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: java-dev@lucene.apache.org
Message-ID: <1891616698.179551265811628083.JavaMail.jira@brutus.apache.org>
Date: Wed, 10 Feb 2010 14:20:28 +0000 (UTC)
From: "Uwe Schindler (JIRA)" <jira@apache.org>
To: java-dev@lucene.apache.org
Subject: [jira] Commented: (LUCENE-2230) Lucene Fuzzy Search: BK-Tree can
 improve performance 3-20 times.
In-Reply-To: <385144480.402931264105194406.JavaMail.jira@brutus.apache.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


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

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

Hi Fuad,

thanks for submitting your changed FuzzyQuery. After quickly looking through the classes I found the following problems:

- The cache is incorrectly synchronized: The cache is static but access is synchronized against the instance.
- The cache is not limited, maybe it should be a WeakHashMap. It can easily overflow the memory (as it consumes lots of memory).
- When you build the tree, you use a class from spellchecker: org.apache.lucene.search.spell.LuceneDictionary. This adds an additional memory consumption, esp. if the index has a large term dict. Why not simply iterate over the IndexReaders's TermEnum?
- The cache cannot work correctly with per segment search (since 2.9) or reopened IndexReaders, because it is only bound to the field name but not an index reader. To have a correct cache, do it like FieldCache and use a combined key from field name and IndexReader.getFieldCacheKey().

Else it looks like a good approach, but the memory consumption is immense for large term dicts. We currently develop a DFA-based FuzzyQuery, which will be provided, when the nex flex branch gets out: LUCENE-2089

If you fix the problems in your classes, we can add this patch to contrib.

> 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