Rejection inversion is a sampling method for discrete monotone distributions. Here is how to use it to benchmark and test software.
Generating Zipfian Distributions Using Rejection Inversion
Rejection inversion is a sampling method for discrete monotone distributions. Here is how to use it to benchmark and test software.
Rejection inversion is a sampling method for discrete monotone distributions. It is useful when you need realistic skew in benchmarks, simulations or tests.
Real workloads are rarely uniform. A small number of keys attract most requests, while the long tail is accessed rarely. Zipfian sampling lets you reproduce that shape instead of guessing.
A benchmark with uniform keys will flatter almost every cache.
Cache Eviction Policies in Storage Engines
Caching stores frequently accessed items in fast volatile storage. The interesting part is deciding what to evict, and when.
Read articleUnderstanding Rejection–Inversion Sampling for Zipf Distributions
The theory behind sampling from Zipfian distributions, and why the inverse CDF is not always enough.
Read articleCumulative Distribution Function and Inverse CDF
What CDF and inverse CDF mean, and how they turn a uniform random number into a sample from any distribution.
Read article