To identify a media item from a database of media items that have common content, a region of interest is defined to include a plurality of frames of a test fingerprint that correspond to different segments of a media item. A media identification system queries a database of reference fingerprints to identify candidate reference fingerprints that contain a frame that matches a frame of the test fingerprint. When a candidate reference fingerprint is found, additional matching frames are determined and the region of interest is reduced to eliminate the matched frames of the test fingerprint. This continues until the region of interest is empty or there are no further matching candidates. Once the set of candidate reference fingerprints are identified, the media identification system compares the test fingerprint to the candidates to determine a closest match, thereby identifying the media item associated with the test fingerprint.