Does lucene uses tries?

[Aman Tandon <am...@gmail.com>]

Hi,

I just have want know that does the lucene used the tries data structure to
store the
data.
With Regards
Aman Tandon

Re: Does lucene uses tries?

[Aman Tandon <am...@gmail.com>]

Thanks shawn for the explanation and for the example, that helps to
understand it quite easily.

With Regards
Aman Tandon


On Fri, Jun 6, 2014 at 3:48 AM, Shawn Heisey <so...@elyograg.org> wrote:

> On 6/5/2014 3:39 PM, Aman Tandon wrote:
> > Thanks to all.
> > And as Solr provides the field datatype as int as well as
> solr.TrieIntField
> > so which one is more better?
>
> The example has "int" and "tint" as two different types that both use
> TrieIntField.  The difference between the two is the precisionStep value.
>
> The "int" type has a precisionStep of zero, which basically turns off
> that feature and results in only one value (the actual number) in the
> index.  This is the most efficient in terms of space, and the type you
> should be using if you do not need range queries.
>
> The "tint" type has a precisionStep of 8, which means that it will store
> additional values in the index at lower precisions, in 8 bit
> increments.  This can greatly speed up range queries as described in the
> Javadoc for this Lucene class:
>
>
> https://lucene.apache.org/core/4_8_1/core/org/apache/lucene/search/NumericRangeQuery.html
>
> This javadoc is fairly technical and honestly doesn't explain it well.
> The following excerpt from the full paper by Uwe Schindler does a
> reasonably good job of explaining how it works.  This example has a
> base-10 precisionStep of one digit, whereas the Lucene implementation
> has a precisionStep defined in terms of base-2 digits (bits).
>
> https://www.dropbox.com/s/7996yacdxv56ehd/trie-explanation.png
>
> Thanks,
> Shawn
>
>

Re: Does lucene uses tries?

[Shawn Heisey <so...@elyograg.org>]

On 6/5/2014 3:39 PM, Aman Tandon wrote:
> Thanks to all.
> And as Solr provides the field datatype as int as well as solr.TrieIntField
> so which one is more better?

The example has "int" and "tint" as two different types that both use
TrieIntField.  The difference between the two is the precisionStep value.

The "int" type has a precisionStep of zero, which basically turns off
that feature and results in only one value (the actual number) in the
index.  This is the most efficient in terms of space, and the type you
should be using if you do not need range queries.

The "tint" type has a precisionStep of 8, which means that it will store
additional values in the index at lower precisions, in 8 bit
increments.  This can greatly speed up range queries as described in the
Javadoc for this Lucene class:

https://lucene.apache.org/core/4_8_1/core/org/apache/lucene/search/NumericRangeQuery.html

This javadoc is fairly technical and honestly doesn't explain it well. 
The following excerpt from the full paper by Uwe Schindler does a
reasonably good job of explaining how it works.  This example has a
base-10 precisionStep of one digit, whereas the Lucene implementation
has a precisionStep defined in terms of base-2 digits (bits).

https://www.dropbox.com/s/7996yacdxv56ehd/trie-explanation.png

Thanks,
Shawn

Re: Does lucene uses tries?

[Aman Tandon <am...@gmail.com>]

Thanks to all.
And as Solr provides the field datatype as int as well as solr.TrieIntField
so which one is more better?

With Regards
Aman Tandon


On Thu, Jun 5, 2014 at 11:23 PM, Michael McCandless <
lucene@mikemccandless.com> wrote:

> The default terms dictionary (BlockTree) also uses a trie index
> structure to locate the block on disk that may contain a target term.
>
> Mike McCandless
>
> http://blog.mikemccandless.com
>
>
> On Thu, Jun 5, 2014 at 12:11 PM, Shawn Heisey <so...@elyograg.org> wrote:
> >> I just have want know that does the lucene used the tries data structure
> >> to
> >> store the
> >> data.
> >
> > Lucene (and Solr) will use whatever you tell it when you create the
> field.
> >
> > If you indicate in your schema fieldType that you want to use a class of
> > solr.TrieIntField, then the field will use a Lucene trie type that holds
> > integers. Similar for TrieLongField, TrieFloatField, etc.
> >
> > Thanks,
> > Shawn
> >
> >
> >
>

Re: Does lucene uses tries?

[Michael McCandless <lu...@mikemccandless.com>]

The default terms dictionary (BlockTree) also uses a trie index
structure to locate the block on disk that may contain a target term.

Mike McCandless

http://blog.mikemccandless.com


On Thu, Jun 5, 2014 at 12:11 PM, Shawn Heisey <so...@elyograg.org> wrote:
>> I just have want know that does the lucene used the tries data structure
>> to
>> store the
>> data.
>
> Lucene (and Solr) will use whatever you tell it when you create the field.
>
> If you indicate in your schema fieldType that you want to use a class of
> solr.TrieIntField, then the field will use a Lucene trie type that holds
> integers. Similar for TrieLongField, TrieFloatField, etc.
>
> Thanks,
> Shawn
>
>
>

Re: Does lucene uses tries?

[Shawn Heisey <so...@elyograg.org>]

> I just have want know that does the lucene used the tries data structure
> to
> store the
> data.

Lucene (and Solr) will use whatever you tell it when you create the field.

If you indicate in your schema fieldType that you want to use a class of
solr.TrieIntField, then the field will use a Lucene trie type that holds
integers. Similar for TrieLongField, TrieFloatField, etc.

Thanks,
Shawn

Re: Does lucene uses tries?

[Jack Krupansky <ja...@basetechnology.com>]

Lucene uses trie for numeric and date fields:
http://lucene.apache.org/core/4_8_0/core/org/apache/lucene/search/NumericRangeQuery.html

-- Jack Krupansky

-----Original Message----- 
From: Aman Tandon
Sent: Thursday, June 5, 2014 5:32 AM
To: solr-user@lucene.apache.org
Subject: Does lucene uses tries?

Hi,

I just have want know that does the lucene used the tries data structure to
store the
data.
With Regards
Aman Tandon