Elias Revisited
Andrew Trotman, Kat Lilly · 2018
The prior belief that the Elias gamma and delta coding are slow because of the bit-wise manipulations is examined in the light of new CPU instructions that perform those manipulations. It is shown that despite using those instructions, Elias gamma and Elias delta remain slow compared to SIMD codecs such as QMX. We provide a theoretical basis on which to bit-wise encode data, and show that it is equivalent to SIMD extensions to Elias gamma that others have already introduced. Extending this we introduce a new SIMD Elias delta variant. Experiments comparing these two codecs to QMX on public data, and in the JASSv2 search engine show that although the index is slightly larger than QMX, search throughput is increased and latency is decreased.