Hacker News new | past | comments | ask | show | jobs | submit login

Comparing a static data structure to two well-known dynamic structures is disingenuous, to say the least. And for a static structure you can do better than just a minimal perfect hash table of fingerprints. You can use a succinct data structure to compress the fingerprints in a form that is still efficiently queryable (unlike say Golomb-compressed sequences): https://www.antoniomallia.it/sorted-integers-compression-wit...



Elias-fano are overestimated without any proof or comparison benchmarks.

Like other integer compression methods, you still need offsets to small blocks for efficient random access.

Getting a single value in a block is done with slow branchy bit ops like ctz and bit shifting. That's decoding

The fastest elias-fano implementation is in https://github.com/powturbo/TurboPFor and is partially using SIMD




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: