[Xapian-devel] Project: Posting list encoding improvements

[Weixian Zhou]

Hi Olly,

Thanks for pointing out my misunderstanding of posting list encoding. I
have some further questions.

*1) How many encoding method are we required to implement? *

I digged into more literature and found some interesting ideas. I think
there are 3 encoding methods are worth a try:

a) optPFD. The fastest decompression speed with large index size. Although
the speed looks good but we should also aware that the experiments in most
literature put whole index in memory, so the fetching from disk time is
simply ingored in them.

b). Simple 16. This is an improved version on simple 9. It's slower than
optPFD while with smaller index size.

c). VSEnocding [1]. This is the new discovery. It reports in [1] that
VSEncoding outperforms PFD and Simple 16 in both index size and
decompression speed. The general idea that differs from previous methods is
that VSEncoding use dynamic programming to optimally partition the lists in
blocks.



*2) What's your opinion of implementing docID reordering?*

I think it's a good option because its significant reduction in index size
(14% and grows as the size increase). Also the query processing speed is
more valuable than index compression speed.



*3) Are we going to compress term positions?*

Although the size of term positions in posting lists is much larger than
docID and frequencies, there are few literature give pretty thoughts on
compressing them. The method proposed in [2] involves much page-wise and
context information and makes it complex and less feasible in real
engineering.



*Reference:*

[1] VSEncoding: efficient coding and fast decoding of integer lists via
dynamic programming, 2010

[2] Compressing term positions in web indexes, 2009



On Thu, Apr 5, 2012 at 5:56 PM, Weixian Zhou <ideazwx at gmail.com> wrote:

> I've submitted my proposal for posting list improvement. Please check and
> reply suggestions.
> Sorry for the late submission. I'm reviewing papers on posting list
> compression in recently years.
>
>
> On Tue, Apr 3, 2012 at 12:47 AM, Olly Betts <olly at survex.com> wrote:
>
>> On Sat, Mar 31, 2012 at 01:25:31AM -0400, Weixian Zhou wrote:
>> > My name is Weixian Zhou, Computer Science student of University at
>> Buffalo,
>> > State University of New York. I am interested in the project of posting
>> > list encoding improvements and weighting schemes. I have some questions
>> > toward them.
>>
>> If you're equally interested in both, I'd probably steer you towards the
>> posting list encoding project - we've had quite a lot of interest in the
>> weighting schemes project already.
>>
>> > 1) After read the comments in brass_postlist.cc, I am still not very
>> clear
>> > about the detailed structure of postings list. If you can provide some
>> > simple examples/graphs will be very straightforward.
>>
>> Each term's posting list is stored in one or more chunks.  Each chunk is
>> up to about 2KB of encoded data, and is stored in a B-tree, with a key
>> built from the term name and the first docid in the chunk.  This allows
>> us to skip ahead in a posting list efficiently - we just look up the
>> key for the docid we want which puts us on the right chunk (or the one
>> before it if that docid is in a gap between chunks).
>>
>> Within each chunk, there's a simple header and then the docids and wdfs
>> are encoding in a fairly simple way using variable length integers, with
>> 7 bits of each byte used for data and the most significant bit used to
>> indicate if there are more bytes for this integer, so 0 to 127 are
>> encoded in one byte, 128 to 16383 in two bytes, etc.  We store the
>> (docid delta - 1) and the wdf in this way.
>>
>> This isn't the most compact encoding by any means, but it is reasonably
>> compact and easy to update - you can splice in new entries without
>> having to re-encode a whole chunk, or do a lot of bit shifts.
>>
>> However, for users not worried about efficiency of updating existing
>> documents, a more compact encoding would be good.
>>
>> > 2) My instant idea to make list smaller: use gamma codes to encode the
>> gap
>> > between docids instead of docids.
>>
>> Why gamma codes?
>>
>> I've not done comparisons myself, but Managing Gigabytes suggests
>> interpolative coding is the best choice for encoding posting lists (of
>> those it considers, which includes gamma).  Interpolative coding comes
>> up as the most compact and similar time to encode and decode.  If you
>> have access to the second edition, the table is on page 129.  Or you
>> may be able to see it in the preview link here:
>>
>>
>> https://www.google.com/search?tbm=bks&q=%22either+the+appropriate+model+must+be+read+off+disk%22
>>
>> I've not done experiments, but we use interpolative coding for
>> positional data so we already have a well tested implementation.
>>
>> > Last question towards the project of weighting schemes: Do we need only
>> to
>> > implement existing weighting scheme instead of coming up with new ideas?
>>
>> Yes, we're more interested there in implementing proven approaches than
>> trying to do original research.
>>
>> > And our mission is to find a weighting scheme that could replace the
>> > default BM25 in Xapian?
>>
>> I'm not sure that's the mission exactly.  The idea is to implement more
>> schemes which are likely to be useful to users.  They might be a better
>> in some situations, or give faster results, or be useful a baseline for
>> researchers, or be useful for some other reason.
>>
>> If there's a good argument for changing the default from BM25, that's
>> definitely an option.  We wouldn't remove BM25 though.
>>
>> Cheers,
>>    Olly
>>
>
>
>
> --
> Weixian Zhou
> Department of Computer Science and Engineering
> University at Buffalo, SUNY
>
>


-- 
Weixian Zhou
Department of Computer Science and Engineering
University at Buffalo, SUNY
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.xapian.org/pipermail/xapian-devel/attachments/20120408/9ed44c29/attachment.htm>