We propose a randomized version of the non-local means (NLM) algorithm for large-scale image filtering. When applied to denoising images using an external database containing ten billion patches, our algorithm returns a randomized solution that is within 0.2 dB of the full NLM solution while reducing the runtime by three orders of magnitude. See our paper for more details.