Sux is a set of high-performance utilities of basic and advanced succinct data structures in C++ and Java.
Here are some key features of "Sux":
· a novel, broadword-based implementation of rank/select queries for up to 264 bits that is highly competitive with known 32-bit implementations on 64-bit architectures (additional space required is 25% for ranking and 12.5%-37.5% for selection);
· sparse rank/select structures for storing pointers, variable-length bit arrays, etc.;
· Java code implementing minimal perfect hash using around 3 bits per string (also using some broadword ideas).
Why C++?
C++ sucks. No, that's not the reason. The problem is that if you want to compare experimentally your rank/select implementations you need a language that puts you in control-every single computational aspect, including cache misses, perturbs the result.
The C++ code in Sux just uses C++ for namespace handling. No object-oriented or otherwise bizarre feature of the language is used.
Why Java?
Writing in Java code that (essentially) has to roll bits over and over may seem a Bad Thing. However, one should take into consideration the following points:
· Improvements in JVMs makes low-level code written in Java faster and faster; often, the performance penalty w.r.t. an equivalent C/C++ application is relatively small.
· Succinct techniques can be mixed in several different ways, and an object-oriented language makes it very easy to play with different implementations of the same interface.
· An object-oriented language make it possible to write interfaces such as BitVector, which provide a wide range of accesses and methods that can be made efficient in suitable classes (e.g., LongArrayBitVector).
· When you're convinced your data structure works, you can easily rewrite it in C/C++.
What's New in This Release:
· This release provides a new monotone minimal perfect hash function that uses log log l bits per string, where l is the string length in bits.
Product's homepage
Find us on Google+
