4 papers · 1 filter
Modular Rank and Linear-Complexity Tests for Pseudorandom Number Generators
Sebastiano Vigna
Standard batteries of tests for pseudorandom number generators (such as dieharder, the NIST suite, and TestU01) provide two empirical tests for linearity, the binary rank and linea…
Modern Minimal Perfect Hashing: A Survey
Hans-Peter Lehmann, Thomas Mueller, Rasmus Pagh +4
Given a set of keys, a perfect hash function for maps the keys in to the first integers without collisions. It may return an arbitrary result for any key…
It is high time we let go of the Mersenne Twister
Sebastiano Vigna
When the Mersenne Twister made his first appearance in 1997 it was a powerful example of how linear maps on could be used to generate pseudorandom numbers. In particu…
ε-Cost Sharding: Scaling Hypergraph-Based Static Functions and Filters to Trillions of Keys
Sebastiano Vigna
We describe a simple and yet very scalable implementation of static functions (VFunc) and of static filters (VFilter) based on hypergraphs. We introduce the idea of ε-cost shardin…