Efficient fuzzy matching of a test item to items in a database
View Patent ↗A database includes a repository of data segments to be searched, called standard streams. But rather than searching all possible segments of each standard stream, the database includes a set of index files that reference a number of different segments in the repository. Each index file provides information about whether various data segments in the repository are likely to match a given test stream, although in the presence of noise there may be multiple possible matches. By consulting a number of the index files, a searching algorithm identifies a set of candidate data segments to test and thus reduces the number of streams that must be tested.
1. 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.
2. A computer program product for identifying a test stream by matching the test stream to a substream within a repository of standard streams, a substream comprising at least a portion of a standard stream in the repository, wherein the test stream is obtained from a series of samples of an event or a content item, the computer program product comprising a computer-readable storage medium containing computer program code for performing the operations:
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.
3. The computer program product of claim 2 , wherein testing each of the substreams comprises:
determining a distance between the test stream and the substream; and
identifying the substream as a match if the distance is within the error tolerance.
4. The computer program product of claim 3 , wherein the distance is computed based on a fraction of the corresponding bits in the test stream and the substream that are not the same, the error tolerance defined as a predetermined fraction of bits that are allowed to be different between the test stream and a matching substream.
5. The computer program product of claim 2 , wherein each bucket references one or more substreams using an identifier of a standard stream in the repository and an offset within that standard stream for locating the substream within the standard stream.
6. The computer program product of claim 2 , wherein each standard stream comprises a plurality of frames, each frame containing characteristic information related to a sample of an audio item.
7. The computer program product of claim 2 , wherein the test stream comprises a plurality of frames, each frame having a number of bits describing characteristic information about a sampled audio item.
8. The computer program product of claim 2 , wherein the test stream is obtained from a series of samples over a time period from an event or content item.