Succinct, compact, and compressed data structures for data-intensive applications
Project description
Succinct
Succinct, compact, and compressed data structures for data-intensive applications.
Notable features
-
State of the art broadword select implementation based on Sebastiano Vigna's fastutil library.
-
A full implementation of "Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Bit Sequences" that supports bit arrays with up to
2^64
bits. -
(Work in progress): An implementation of Elias-Fano representation of monotone sequences of natural numbers. Using this encoding, "an element occupies a number of bits bounded by two plus the logarithm of the average gap" (source).
-
(Coming soon): An implementation of "On Compressing Permutations and Adaptive Sorting" by Barbay and Navarro, which can be very useful for maintaining massive permutations in memory while allowing efficient inverse lookups.
Statement of public good
This project is made possible by The Mathematics and Informatics Institute of Ohio. The author gratefully acknowledges Root Insurance Company for providing 12 "hack days" per year for engineers to work on projects such as this one.
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.