A robust hashing method is applied to media data (e.g., video, image, and/or audio data), producing a hash output that is robust with respect to at least one attribute of the media data. A histogram is generated for the media data and the histogram is hashed using a weighted hashing procedure. The histogram can be derived from a plurality of randomized versions of the media file, each randomized version of the media file altered to a random extent with respect to the attribute. The histogram can also be derived from a plurality of feature descriptors computed for the media data that are coarsely encoded with respect to the attribute. The weighted hashing procedure includes assigning a weight to components of the histogram and applying a plurality of hash functions to a number of versions of each component, the number of versions based on the assigned weight.