CacheDiff: Fast Random Sampling

Dai Nguyen Bui

We present a sampling method called, CacheDiff, that has both time and space complexity of O(k) to randomly select k items from a pool of N items, in which N is known.