lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Michael McCandless <luc...@mikemccandless.com>
Subject Re: TrieRangeQuery for contrib?
Date Tue, 25 Nov 2008 19:47:11 GMT

Uwe Schindler wrote:

> Hi Mike, hi Paul,
>
> Mike: You are right, the algorithm has one advantage and one  
> disadvantage:
>
> - There is not only a logarithmic bound, there is a hard upper  
> bound. In my
> algorithm with 8 precisions (so from 1 to 8 bytes length of keys) the
> maximum numbers of terms to be visited is limited to 3825 terms (see  
> the
> java docs or the cited paper). The upper limit only applies, if you  
> make a
> very big range and have a lot of different homogenous distributed  
> terms
> inside the range (without the optimization). Testing with a 500,000  
> document
> index (6 GB) with numeric values (doubles) has shown, that even with  
> large
> ranges the maximum number of terms, you mostly only get about 300  
> terms to
> be visited. This is not related to index size!

Awesome!

> - The index size is bigger: You store for each numeric field not  
> only one
> term in index, but eight, so index size increases. But this is  
> neglectible
> in my opinion and for large indexes the speed increase is great.

I agree this should be a very small cost, especially because it's only  
the range-tokens, often one per doc per ranged-field, that have  
increased storage.  I would imagine in practice it's quite low.

> - Inside Luke, the values of such "Trie" fields are not human readable
> (because of the encoding). Even when stored, the current  
> implementation uses
> the special encoding to store the field. For displaying the field  
> you have
> to use the decoder from the TrieUtils class. But this is the same with
> current DateUtils from Lucene (but they are more readable :-) )

These seems OK, for starters.  Eventually maybe such a "range field"  
could provide an interface that knows how to "subdivide" intervals on  
its space of all terms, assigning more human readable labels to these  
subdivisions, instead of always casting to unsigned long.

> Comparisions with the above 500,000 doc index showed that the old  
> RangeQuery
> (with raised BooleanQuery clause count) took about 30-40 secs to  
> complete,
> ConstantScoreRangeQuery took 5 secs and TrieRangeQuery took <100ms to
> complete (on an Opteron64 machine, Java 1.5). You can test a little  
> bit on
> http://www.pangaea.de/advanced/advsearch.php by entering something  
> into the
> geographic bounding box or temporal coverage). As you can see, the  
> usage of
> this range query type is optimal for geographic searches using  
> doubles (not
> fixed decimals!), longs or dates as keys.

Wow it's very fast!  I first searched for "water", which returned  
~428K docs, then bounded it roughly around Africa and it returned ~78K  
docs, very quickly.  Now I'd really love to get this into Lucene!

> I have no problem with including it into Lucene contrib. I just have  
> some
> questions/comments:
>
> - Code is Apache 2.0 licensed, so it is simple to include. I would  
> change
> the package prefix, update the JavaDocs and create a contrib patch  
> out of
> it. References to commons logging can be removed (they are just for
> debugging). Code is Java 1.5 (using StringBuilder), but this could  
> easily be
> changed.

Contrib code can be Java 1.5.

> - I want to be able to develop the code further once in contrib, is  
> this
> possible? How would be the best to handle this? Let the code stay in  
> my SVN
> and you update it or let me commit to the contrib folder in Lucene?
> Currently the code is in SVN of panFMP (www.panfmp.org) that uses  
> it. When
> donated to Apache, I would put a dependency into panFMP to the contrib
> Package, once released and remove it from my tree. I do not want to  
> get the
> code into a dead end or start a fork of it inside contrib, because I  
> want to
> actively maintain it.

I think for starters open an issue, attach a patch, and then we  
iterate from there?  Probably having the code in Apache's SVN, with  
the eventual goal of giving you commit rights to contrib, is what we  
should aim for?

> My intentions for giving the code to Lucene were some questions from  
> other
> projects (from geographic information systems), to also use the  
> optimized
> range queries for such type of geo queries, e.g. GeoNetwork  
> Opensource, also
> using Lucene, is interested. Maybe Solr wants to make use of it (using
> another field data type). Instead of distributing the code to  
> different
> projects, I wanted to make it available as plugin for everybody from  
> Lucene
> itself.

I agree, this should be in Lucene.

> I would start an issue in JIRA and attach the patch.

Excellent!

Mike


---------------------------------------------------------------------
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