US Patent 8625033 Large-scale matching of audio and video

Large-scale matching of videos is performed by matching a set of probe videos against a set of reference videos to determine if they are visually and/or aurally similar. The visual and audio fingerprints of all probe videos and reference videos are divided into subfingerprints, which are divided into LSH bands. The LSH bands of the probe videos are sorted in one list, and the LSH bands of the reference videos are sorted in another list. Then, the two sorted lists are linearly scanned for matching LSH bands. The matching LSH bands are sorted by probe video ID, and each probe video ID is searched to find matches between probe videos and reference videos. Further, an incremental matching process identifies matches as groups of new probe videos and/or new reference videos are added, without unnecessary repetition of matching old probe videos against old reference videos.