Patent ID: 7769708

Claim:
A computer-implemented method for identifying a test sequence by matching the test sequence to a substream within a repository of standard streams, wherein the test sequence is obtained from a series of samples of an event or content item, a substream comprising at least a portion of a standard stream in the repository, the method comprising: accessing an index of a plurality of substreams indexed according to a plurality of templates, each template specifying a number of bit positions, wherein a given template is associated with a plurality of buckets, each bucket referencing a group of substreams that have the same values at the bit positions specified by the template; selecting a first subsequence of the test sequence, wherein the first subsequence has a length equal to a test length and the test sequence has a length greater than the test length; searching the repository for the first subsequence by: for a plurality of buckets, marking the buckets for which the bits in the first subsequence match the bits in the substreams of the bucket at the bit positions specified by the template associated with the bucket, identifying a candidate set of substreams based on the occurrence in the marked buckets of each substream, and testing the substreams of the candidate set to determine whether one or more of the substreams match the first subsequence within an error tolerance; for any substreams that match the first subsequence within the error tolerance, determining whether the test sequence matches a corresponding substream of the repository; if the test sequence does not match any substreams in the repository, selecting a second subsequence of the test sequence having a length equal to the test length; searching the repository for the second subsequence by: for a plurality of buckets, marking the buckets for which the bits in the second subsequence match the bits in the substreams of the bucket at the bit positions specified by the template associated with the bucket, identifying a candidate set of substreams based on the occurrence in the marked buckets of each substream, and testing the substreams of the candidate set to determine whether one or more of the substreams match the second subsequence within an error tolerance; for any substreams that match the second subsequence within the error tolerance, determining whether the test sequence matches a corresponding substream of the repository; and presenting a result of the testing.