1. A method of storing fingerprints identifying audio-visual media signals in a database, the method comprising, for each audio-visual signal: dividing said audio-visual media signal into a sequence of frames; sub-sampling said sequence of frames by a factor M to obtain a sub-sampled sequence of frames, each frame of the sub-sampled sequence of frames overlapping in time with an adjacent frame of the sub-sampled sequence of frames, and the factor M being a positive integer; extracting, for each frame of said sub-sampled sequence of frames, a hash word derived from a perceptually essential property of the signal within said frame, to obtain a respective sub-sampled sequence of hash words, each hash word of the sub-sampled sequence of hash words being nonrandomly positioned within the sub-sampled sequence of hash words; and storing said sub-sampled sequence of hash words as a fingerprint in said database, the fingerprint being a digital summary of the audio visual media signal.