You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Adrien Grand (JIRA)" <ji...@apache.org> on 2014/10/01 16:19:33 UTC

[jira] [Updated] (LUCENE-5983) RoaringDocIdSet

     [ https://issues.apache.org/jira/browse/LUCENE-5983?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Adrien Grand updated LUCENE-5983:
---------------------------------
    Attachment: LUCENE-5983.patch

Here are a patch and the results of the benchmark on this new DocIdSet: http://people.apache.org/~jpountz/doc_id_sets4.html

Compared to the paper, I also optimized the super-dense case in order to encode the negation of the set to save space (like WAH8DocIdSet does). I like the fact that this set is overall very fast, especially to build, which is an interesting characteristic for caching, so I replaced WAH8DocIdSet with this new DocIdSet in CachingWrapperFilter. Another nice property is that it is naturally indexed, it doesn't need a side-car data-structure like the WAH8 and PFOR doc id sets: in the array case, you can just perform a binary search, and in the FixedBitSet case you already have random-access.

In order to avoid the profusion of doc id sets, I'm thinking of removing the WAH8 and PFOR doc id sets since this one looks better to me in most areas.

> RoaringDocIdSet
> ---------------
>
>                 Key: LUCENE-5983
>                 URL: https://issues.apache.org/jira/browse/LUCENE-5983
>             Project: Lucene - Core
>          Issue Type: Improvement
>            Reporter: Adrien Grand
>            Assignee: Adrien Grand
>            Priority: Minor
>         Attachments: LUCENE-5983.patch
>
>
> Robert pointed me to this paper: http://arxiv.org/pdf/1402.6407v4 that describes an interesting way to build doc id sets: The bit space is divided into blocks of 2^16 bits so that you can store the bits which are set either in a short[] (2 bytes per doc ID) or in a FixedBitSet. The choice is easy, if less than 2^12 bits are set, then the short[] representation is more compact otherwise a FixedBitSet would be more compact. It's quite similar to the way that Solr builds DocSets in {{SolrIndexSearcher.getDocSet(DocsEnumState)}}.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

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