Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Home

hyan edited this page · 23 revisions
Clone this wiki locally

Kamikaze is a utility package wrapping set implementations on document lists. It also implements P4Delta compression algorithm for sorted integer segments to enable Inverted List compression for search engines like Lucene.

PForDelta is a compression method that is originally proposed by S. Heman 1. It is then used by WestLab (Web Exploration and Search Technology Lab) at Polytechnic Institute of New York University to compress inverted indexes of search engines 2. Recently, WestLab 3proposed several new optimizations on PForDelta and claimed that PForDelta can achieve a better tradeoff between the compressed size and the decompression speed than other inverted index compression methods.

The beauty of PForDelta is it supports extremely fast decompression while also achieving a small compressed size. The basic idea is as follows 3: in order to compress a block of k numbers, say, 128 numbers, it first determines a value b such that most of the 128 values to be encoded (say, 90%) are less than 2^b and thus fit into a fixed bit field of b bits each. The remaining values, called exceptions, are coded separately. If we apply PForDelta to blocks containing some multiple of 32 values, then decompression involves extracting groups of 32 b-bit values, and finally patching the result by decoding a smaller number of exceptions. This process can be implemented extremely efficiently by providing, for each value of b, an optimized method for extracting 32 b-bit values from b memory words. PForDelta can be modified and tuned in various ways by choosing different thresholds for the number of exceptions allowed, and by encoding the exceptions in different ways.

For details about PForDelta and its several optimized variations, please refer to:

1 http://homepages.cwi.nl/~heman/downloads/msthesis.pdf (The original PForDelta, which was proposed in the thesis of S. Heman) 2 http://www2008.org/papers/pdf/p387-zhangA.pdf (A variation of the original PForDelta, which is implemented by the Web Exploration and Search Technology Lab, WestLab, at Polytechnic Institute of New York University, and used to compress inverted indexes of search engines). 3 http://www2009.org/proceedings/pdf/p401.pdf (Several other further optimized PForDelta, for example, NewPFD and OptPFD, which are also implemented by WestLab, and used to compress inverted indexes of search engines).
Something went wrong with that request. Please try again.