Home

Awesome

JavaFastPFOR: A simple integer compression library in Java

docs-badge Java CI

License

This code is released under the Apache License Version 2.0 http://www.apache.org/licenses/.

What does this do?

It is a library to compress and uncompress arrays of integers very fast. The assumption is that most (but not all) values in your array use much less than 32 bits, or that the gaps between the integers use much less than 32 bits. These sort of arrays often come up when using differential coding in databases and information retrieval (e.g., in inverted indexes or column stores).

Please note that random integers are not compressible, by this library or by any other means. If you ever had the means of systematically compressing random integers, you could compress any data source to nothing, by recursive application of your technique.

This library can decompress integers at a rate of over 1.2 billions per second (4.5 GB/s). It is significantly faster than generic codecs (such as Snappy, LZ4 and so on) when compressing arrays of integers.

The library is used in LinkedIn Pinot, a realtime distributed OLAP datastore. Part of this library has been integrated in Parquet (http://parquet.io/). A modified version of the library is included in the search engine Terrier (http://terrier.org/). This libary is used by ClueWeb Tools (https://github.com/lintool/clueweb). It is also used by Apache NiFi.

This library inspired a compression scheme used by Apache Lucene and Apache Lucene.NET (e.g., see http://lucene.apache.org/core/4_6_1/core/org/apache/lucene/util/PForDeltaDocIdSet.html ).

It is a java port of the fastpfor C++ library (https://github.com/lemire/FastPFor). There is also a Go port (https://github.com/reducedb/encoding). The C++ library is used by the zsearch engine (http://victorparmar.github.com/zsearch/) as well as in GMAP and GSNAP (http://research-pub.gene.com/gmap/).

Usage

Really simple usage:

        IntegratedIntCompressor iic = new IntegratedIntCompressor();
        int[] data = ... ; // to be compressed
        int[] compressed = iic.compress(data); // compressed array
        int[] recov = iic.uncompress(compressed); // equals to data

For more examples, see example.java or the examples folder.

JavaFastPFOR supports compressing and uncompressing data in chunks (e.g., see advancedExample in https://github.com/lemire/JavaFastPFOR/blob/master/example.java).

Some CODECs ("integrated codecs") assume that the integers are in sorted orders and use differential coding (they compress deltas). They can be found in the package me.lemire.integercompression.differential. Most others do not.

The Java Team at Intel (R) introduced the vector implementation for FastPFOR based on the Java Vector API that showed significant gains over the non-vectorized implementation. For an example usage, see examples/vector/Example.java. The feature requires JDK 19+ and is currently for advanced users.

Maven central repository

Using this code in your own project is easy with maven, just add the following code in your pom.xml file:

    <dependencies>
         <dependency>
	     <groupId>me.lemire.integercompression</groupId>
	     <artifactId>JavaFastPFOR</artifactId>
	     <version>[0.2,)</version>
         </dependency>
     </dependencies>

Naturally, you should replace "version" by the version you desire.

You can also download JavaFastPFOR from the Maven central repository: http://repo1.maven.org/maven2/me/lemire/integercompression/JavaFastPFOR/

Why?

We found no library that implemented state-of-the-art integer coding techniques such as Binary Packing, NewPFD, OptPFD, Variable Byte, Simple 9 and so on in Java. We wrote one.

Thread safety

Some codecs are thread-safe while others are not. For this reason, it is best to use one codec per thread. The memory usage of a codec instance is small in any case.

Nevertheless, if you want to reuse codec instances, note that by convention, unless the documentation of a codec specify that it is not thread-safe, then it can be assumed to be thread-safe.

Authors

Main contributors

with contributions by

How does it compare to the Kamikaze PForDelta library?

In our tests, Kamikaze PForDelta is slower than our implementations. See the benchmarkresults directory for some results.

https://github.com/lemire/JavaFastPFOR/blob/master/benchmarkresults/benchmarkresults_icore7_10may2013.txt

Reference: http://sna-projects.com/kamikaze/

Requirements

Releases up to 0.1.12 require Java 7 or better.

The current development versions assume JDK 11 or better.

How fast is it?

Compile the code and execute me.lemire.integercompression.benchmarktools.Benchmark.

Speed is always reported in millions of integers per second.

For Maven users

mvn compile
mvn exec:java

You may run our examples as follows:

mvn package
javac -cp target/classes/:. example.java
java -cp target/classes/:. example

For ant users (legacy, currently untested)

If you use Apache ant, please try this:

$ ant Benchmark

or:

$ ant Benchmark -Dbenchmark.target=BenchmarkBitPacking

API Documentation

http://www.javadoc.io/doc/me.lemire.integercompression/JavaFastPFOR/

Want to read more?

This library was a key ingredient in the best paper at ECIR 2014 :

Matteo Catena, Craig Macdonald, Iadh Ounis, On Inverted Index Compression for Search Engine Efficiency, Lecture Notes in Computer Science 8416 (ECIR 2014), 2014. http://dx.doi.org/10.1007/978-3-319-06028-6_30

We wrote several research papers documenting many of the CODECs implemented here:

Ikhtear Sharif wrote his M.Sc. thesis on this library:

Ikhtear Sharif, Performance Evaluation of Fast Integer Compression Techniques Over Tables, M.Sc. thesis, UNB 2013. https://unbscholar.lib.unb.ca/islandora/object/unbscholar%3A9399/datastream/PDF/view

He also posted his slides online: http://www.slideshare.net/ikhtearSharif/ikhtear-defense

Other recommended libraries

Funding

This work was supported by NSERC grant number 26143.