Kamikaze

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.

Details

Kamikaze version 1.0.0 provides docset implementations on various underlying document id set representations for inverted lists in search engines. Currently the supported implementations include

1. Integer Array representation : Document set based on Dynamic Integer Arrays
2. OpenBitSet representation : Document Set based on OpenBitSet implementation from Lucene.
3. P4Delta representation : Document Set for sorted Integer segments compressed using a variation of the P4Delta compression algorithm.

Ref : http://homepages.cwi.nl/~heman/downloads/msthesis.pdf

Ref : http://www2008.org/papers/pdf/p387-zhangA.pdf

The library also provides elementary set (AND|OR|NOT) operations on DocSets without materializing the final document set, this is extremely useful for large sorted integer segments.

Performance Comparison

This is a very elementary performance comparison in terms of compression ratios and iteration speeds for the different supported DocSet implementations. For a more comprehensive evaluation watch the performance comparison page in the future.

NOTE :

1. These are numbers for iteration over the docidset using the iterator framework.
2. P4Delta numbers represent iterating over the docsets in COMPRESSED form. We never actually decompress the P4Delta sets, as our motivation is to use it for caching inverted lists and hence the missing patching phase in the implementation.
3. The size estimates are generated by employing the repeated GC with finalization technique and thus include Object Overheads with OpenBitSet and P4Delta implementations.(See class com.kamikaze.performance.TestSizeEstimates.java on the BR_DEV_1_0_4 branch)
4. All Tests are run with the following VM args : -d64 -Xms2G -Xmx4G

Skip Performance : (Skipping to every value incrementally in the set)