You are viewing a plain text version of this content. The canonical link for it is here.
Posted to java-user@lucene.apache.org by First Last <va...@gmail.com> on 2011/01/07 20:55:09 UTC
is OpenBitSet / SortedVIntList compressed bit map index?
Hi,
is OpenBitSet / SortedVIntList a compressed bit map index? Which one is
better if memory usage is the primary concern ?
Our filters are sparse. So is SortedVIntList better in that case?
Are there any other compressed bitmap index implementations which offer bit
map compression at a decent performance assuming filters are sparse?
I'd appreciate any help on this.Thanks.
- Raavan
Re: is OpenBitSet / SortedVIntList compressed bit map index?
Posted by Federico Fissore <fe...@fissore.org>.
Raavan, il 08/01/2011 19:17, ha scritto:
> Thanks Ryan. I will test this to see if it uses much less memory than
> SortedVIntList.
>
> -Raavan
Hello Raavan,
have you tested those implementations? How do they look?
federico
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: is OpenBitSet / SortedVIntList compressed bit map index?
Posted by Raavan <va...@gmail.com>.
Thanks Ryan. I will test this to see if it uses much less memory than
SortedVIntList.
-Raavan
On Fri, Jan 7, 2011 at 4:05 PM, Ryan Aylward <ry...@glassdoor.com> wrote:
> I don't recall how we decided to use it, but we are using
> http://code.google.com/p/compressedbitset/ and it seems to be pretty
> efficient in terms of memory.
>
> -----Original Message-----
> From: Federico Fissore [mailto:federico@fissore.org]
> Sent: Friday, January 07, 2011 3:12 PM
> To: java-user@lucene.apache.org
> Subject: Re: is OpenBitSet / SortedVIntList compressed bit map index?
>
> First Last, il 07/01/2011 20:55, ha scritto:
> > Hi,
> >
> > is OpenBitSet / SortedVIntList a compressed bit map index? Which one is
> > better if memory usage is the primary concern ?
> >
>
> SortedVIntList is compressed, OpenBitSet is not
>
>
> > Our filters are sparse. So is SortedVIntList better in that case?
> >
>
> Yes
>
>
> > Are there any other compressed bitmap index implementations which offer
> bit
> > map compression at a decent performance assuming filters are sparse?
> >
>
> I'm too looking for alternative implementations of compressed bitsets,
> so I'm too really interested in everybody experience: my primary concern
> at the moment is serializing bitsets to recover searcher warmup time
>
> I've tried some and roughly tested them: my conclusion was that we
> (lucene users) already stand on the rolls royce of bitset implementations.
>
> federico
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
>
>
RE: is OpenBitSet / SortedVIntList compressed bit map index?
Posted by Ryan Aylward <ry...@glassdoor.com>.
I don't recall how we decided to use it, but we are using http://code.google.com/p/compressedbitset/ and it seems to be pretty efficient in terms of memory.
-----Original Message-----
From: Federico Fissore [mailto:federico@fissore.org]
Sent: Friday, January 07, 2011 3:12 PM
To: java-user@lucene.apache.org
Subject: Re: is OpenBitSet / SortedVIntList compressed bit map index?
First Last, il 07/01/2011 20:55, ha scritto:
> Hi,
>
> is OpenBitSet / SortedVIntList a compressed bit map index? Which one is
> better if memory usage is the primary concern ?
>
SortedVIntList is compressed, OpenBitSet is not
> Our filters are sparse. So is SortedVIntList better in that case?
>
Yes
> Are there any other compressed bitmap index implementations which offer bit
> map compression at a decent performance assuming filters are sparse?
>
I'm too looking for alternative implementations of compressed bitsets,
so I'm too really interested in everybody experience: my primary concern
at the moment is serializing bitsets to recover searcher warmup time
I've tried some and roughly tested them: my conclusion was that we
(lucene users) already stand on the rolls royce of bitset implementations.
federico
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: is OpenBitSet / SortedVIntList compressed bit map index?
Posted by Raavan <va...@gmail.com>.
Thanks Raf.
On Sun, Jan 9, 2011 at 1:20 AM, Raf <r....@gmail.com> wrote:
> On Sat, Jan 8, 2011 at 7:24 PM, Raavan <va...@gmail.com> wrote:
>
> > Also, just for my understanding, is SortedVIntList able to perform some
> > operations such as AND/OR without decompression ?
> >
>
> No, not natively:
>
> http://lucene.apache.org/java/3_0_2/api/core/org/apache/lucene/util/SortedVIntList.html
>
> But the *iterator* returns the *docIds* by order and there is a
> *constructor
> *that accepts a *DocIdSetIterator*.
>
> So it's quite easy to implement the AND/OR operations by creating a *
> DocIdSetIterator *that receives the two iterators from the original *
> SortedVIntLists* and scans them in parallel, implementing *nextDoc* and *
> advance* methods accordingly to AND/OR semantic.
>
> We use something like that and, for very sparse bitsets, it is more
> efficient than to convert them in *OpenBitSets* in order to perform AND/OR
> operations.
>
> Bye
> *Raf*
>
Re: is OpenBitSet / SortedVIntList compressed bit map index?
Posted by Raf <r....@gmail.com>.
On Sat, Jan 8, 2011 at 7:24 PM, Raavan <va...@gmail.com> wrote:
> Also, just for my understanding, is SortedVIntList able to perform some
> operations such as AND/OR without decompression ?
>
No, not natively:
http://lucene.apache.org/java/3_0_2/api/core/org/apache/lucene/util/SortedVIntList.html
But the *iterator* returns the *docIds* by order and there is a *constructor
*that accepts a *DocIdSetIterator*.
So it's quite easy to implement the AND/OR operations by creating a *
DocIdSetIterator *that receives the two iterators from the original *
SortedVIntLists* and scans them in parallel, implementing *nextDoc* and *
advance* methods accordingly to AND/OR semantic.
We use something like that and, for very sparse bitsets, it is more
efficient than to convert them in *OpenBitSets* in order to perform AND/OR
operations.
Bye
*Raf*
Re: is OpenBitSet / SortedVIntList compressed bit map index?
Posted by Raavan <va...@gmail.com>.
Also, just for my understanding, is SortedVIntList able to perform some
operations such as AND/OR without decompression ?
Some of the algorithms mentioned below claim to do that. But I understand
that there are patent issues surrounding these algorithms.
http://en.wikipedia.org/wiki/Bitmap_index
-Raavan
On Sat, Jan 8, 2011 at 10:14 AM, Raavan <va...@gmail.com> wrote:
> Thanks Federico.
>
> >> my primary concern at the moment is serializing bitsets to recover
> searcher warmup time
>
> I am also considering doing the same to reduce warmup time during restarts.
>
> It seems one of the disadvantages of SortedVIntList is the performance
> skipTo() as per Paul Elschot since it does not support random access like
> OpenBitSet.
> https://issues.apache.org/jira/browse/LUCENE-1296
>
> Our primary concern is memory usage since we have hundreds of filters and
> large number of documents. So if the performance is decent, I am thinking of
> using SortedVIntList for all our sparse filters.
>
> -Raavan
>
>
> On Fri, Jan 7, 2011 at 3:11 PM, Federico Fissore <fe...@fissore.org>wrote:
>
>> First Last, il 07/01/2011 20:55, ha scritto:
>>
>> Hi,
>>>
>>> is OpenBitSet / SortedVIntList a compressed bit map index? Which one is
>>> better if memory usage is the primary concern ?
>>>
>>>
>> SortedVIntList is compressed, OpenBitSet is not
>>
>>
>>
>> Our filters are sparse. So is SortedVIntList better in that case?
>>>
>>>
>> Yes
>>
>>
>>
>> Are there any other compressed bitmap index implementations which offer
>>> bit
>>> map compression at a decent performance assuming filters are sparse?
>>>
>>>
>> I'm too looking for alternative implementations of compressed bitsets, so
>> I'm too really interested in everybody experience: my primary concern at the
>> moment is serializing bitsets to recover searcher warmup time
>>
>> I've tried some and roughly tested them: my conclusion was that we (lucene
>> users) already stand on the rolls royce of bitset implementations.
>>
>> federico
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
>> For additional commands, e-mail: java-user-help@lucene.apache.org
>>
>>
>
Re: is OpenBitSet / SortedVIntList compressed bit map index?
Posted by Raavan <va...@gmail.com>.
Thanks Federico.
>> my primary concern at the moment is serializing bitsets to recover
searcher warmup time
I am also considering doing the same to reduce warmup time during restarts.
It seems one of the disadvantages of SortedVIntList is the performance
skipTo() as per Paul Elschot since it does not support random access like
OpenBitSet.
https://issues.apache.org/jira/browse/LUCENE-1296
Our primary concern is memory usage since we have hundreds of filters and
large number of documents. So if the performance is decent, I am thinking of
using SortedVIntList for all our sparse filters.
-Raavan
On Fri, Jan 7, 2011 at 3:11 PM, Federico Fissore <fe...@fissore.org>wrote:
> First Last, il 07/01/2011 20:55, ha scritto:
>
> Hi,
>>
>> is OpenBitSet / SortedVIntList a compressed bit map index? Which one is
>> better if memory usage is the primary concern ?
>>
>>
> SortedVIntList is compressed, OpenBitSet is not
>
>
>
> Our filters are sparse. So is SortedVIntList better in that case?
>>
>>
> Yes
>
>
>
> Are there any other compressed bitmap index implementations which offer
>> bit
>> map compression at a decent performance assuming filters are sparse?
>>
>>
> I'm too looking for alternative implementations of compressed bitsets, so
> I'm too really interested in everybody experience: my primary concern at the
> moment is serializing bitsets to recover searcher warmup time
>
> I've tried some and roughly tested them: my conclusion was that we (lucene
> users) already stand on the rolls royce of bitset implementations.
>
> federico
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
>
>
Re: is OpenBitSet / SortedVIntList compressed bit map index?
Posted by Federico Fissore <fe...@fissore.org>.
First Last, il 07/01/2011 20:55, ha scritto:
> Hi,
>
> is OpenBitSet / SortedVIntList a compressed bit map index? Which one is
> better if memory usage is the primary concern ?
>
SortedVIntList is compressed, OpenBitSet is not
> Our filters are sparse. So is SortedVIntList better in that case?
>
Yes
> Are there any other compressed bitmap index implementations which offer bit
> map compression at a decent performance assuming filters are sparse?
>
I'm too looking for alternative implementations of compressed bitsets,
so I'm too really interested in everybody experience: my primary concern
at the moment is serializing bitsets to recover searcher warmup time
I've tried some and roughly tested them: my conclusion was that we
(lucene users) already stand on the rolls royce of bitset implementations.
federico
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: is OpenBitSet / SortedVIntList compressed bit map index?
Posted by ai114 <ga...@googlemail.com>.
First Last wrote:
>
> Are there any other compressed bitmap index implementations which offer
> bit
> map compression at a decent performance assuming filters are sparse?
>
Have a look at EWAH by Daniel Lemire
google: http://code.google.com/p/javaewah/
http://code.google.com/p/javaewah/
research paper: http://arxiv.org/abs/0901.3751
http://arxiv.org/abs/0901.3751
code: https://github.com/lemire/javaewah/tree/
https://github.com/lemire/javaewah/tree/
Gabriel
--
View this message in context: http://lucene.472066.n3.nabble.com/is-OpenBitSet-SortedVIntList-compressed-bit-map-index-tp2213863p2983908.html
Sent from the Lucene - Java Users mailing list archive at Nabble.com.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org