Rust implementation of Sebastiano Vigna's elias fano.
Our goal is not to achieve best compression possible, instead we seek a good tradeoff between speed and memory.
We differ from the paper's implementation because we don't use a bitvector with skipping quantums for the high-bits but currently we use a Fully Indexable Dictionary.
This seems a reasonable idea because in SUX implementation of Elias Fano (SUX is one of Vigna's projects) he use simple select to store the high-bits.
Currently we only need select_0 and select_1 so better structures, to support select on the high-bits, might be explored in the futures.
For this reason one of the next steps is to implement simple_select as presented by Vigna in Broadword Implementation of Rank/Select Queries.
We benchmark our library against all the data structures we found that supports rank and select.
The benchmark is done on a sorted vector of 1000000 values between 0 and 2000000. For each run the select / rank is repeated 1_000 times with random inputs. These are the results on my Ryzen 9 3900x 4Ghz 12c 24t.
test bio::rank ... bench: 17,488 ns/iter (+/- 526)
test bio::select ... bench: 151,620 ns/iter (+/- 6,668)
test ef::rank ... bench: 81,228 ns/iter (+/- 3,542)
test ef::select ... bench: 49,509 ns/iter (+/- 1,761)
test fid::rank ... bench: 35,865 ns/iter (+/- 1,213)
test fid::select ... bench: 143,085 ns/iter (+/- 4,942)
test hashmap::select ... bench: 78,803 ns/iter (+/- 6,984)
test indexed_bitvec::rank ... bench: 52,563 ns/iter (+/- 1,369)
test indexed_bitvec::select ... bench: 116,231 ns/iter (+/- 3,741)
test rsdict::rank ... bench: 21,915 ns/iter (+/- 623)
test rsdict::select ... bench: 45,674 ns/iter (+/- 317)
test succint::jacobson_rank ... bench: 17,966 ns/iter (+/- 223)
test succint::jacobson_select ... bench: 509,892 ns/iter (+/- 6,706)
test succint::rank9_rank ... bench: 9,068 ns/iter (+/- 245)
test succint::rank9_select ... bench: 324,839 ns/iter (+/- 1,784)
test vec::rank ... bench: 123,351 ns/iter (+/- 760)
test vec::select ... bench: 3,880 ns/iter (+/- 61)
TODO!