Design

Kamikaze is a utility package wrapping set implementations on document lists. It is designed for serving compact set representation and fast set operations. The architecture of Kamikaze (which is similar for Version 1.0.0, Verison 2.0.0 and Version 3.0.0) is shown in the following figure.

Architecture in Version 3.0.0:

In particular,

PForDelta in Version 3.0.0

History

PForDelta is a compression method that was originally proposed by S. Heman. It was not originally designed to compress inverted indexes of search engines. It was first used in 2008 by WestLab (Web Exploration and Search Technology Lab at Polytechnic Institute of New York University) to compress inverted indexes of search engines. Recently, WestLab proposed several other optimizations on PForDelta and claimed that the optimized PForDelta can achieve a better tradeoff between the compressed size and the decompression speed than other inverted index compression methods, for example, Rice coding, Variable-byte coding, Gamma coding, Interpolative coding, etc.The beauty of PForDelta is that it supports extremely fast decompression while also achieving a small compressed size.

Basic Idea

The basic idea of PForDelta is as follows: in order to compress a block of k numbers, say, 256 numbers, it first determines a value b such that most of the 256 values to be encoded (say, 90%) are less than 2^b and thus fit into a fixed bit field of b bit s each. The remaining values, called exceptions (please note this has nothing to do with Java run time exceptions), are coded separately. The data structure of PForDelta is shown in the following figure.

In the above figure, a block of 256 integers is compressed as a block of 256 b-bit slots plus some additional data appended to those slots. Most of the integers in the above block can fit into b=5 bits except two exceptions, 55 and 70. The two exceptions are coded in the same way as follows: we append their offsets within the block (expPos), that is, where the two exceptions occur, to the end of the 256 b-bit slots. We store the lower b bits of the exceptions into their corresponding slots(Lo55 and Lo70) and append their higher 32-b bits(Hi55 and Hi70) to the end of expPos, that is, expHighBits. ExpPos and expHighBits are concatenated together and compressed by another compression methods called Simple 16.

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.