The present disclosure is directed to systems, methods, and computer-readable storage media for sampling from distributed data streams. Data elements are received at site servers configured to collect and report data to a coordinator device. The site servers assign a binary string to each of the data elements. Each bit of the binary strings can be independently set to a 0 or a 1 with a probability of one half. The binary string is used to sample from the received data elements, and the data elements and/or the sampled data elements can be transmitted to a coordinator device. The coordinator device can examine one or more bits of the binary string to draw samples of the received data elements in accordance with desired probabilities.