Efficient matching of data

Abstract

Technologies are disclosed for enabling users to comprehensively determine their exposures to media and to receive services based thereon. For example, an application can be executed on a computing device associated with a user. The application can continuously monitor audio data that the computing device is exposed to and can generate digital signatures thereof. The digital signatures can be transmitted to a server that comprises a database of reference digital signatures and circuitry configured to compare and match the received digital signatures and the reference digital signatures. When a match is found, the server retrieves information associated with the matched reference digital signature and returns, to the device, the retrieved information. The server can also concatenate matches associated with data received from a plurality of computing devices and provide the concatenated data to a third party, who in turn, returns services to the users based on the received data.

What is claimed: 
     
         1 . A system comprising electronic circuitry configured to:
 compare a first window comprising a first set of fingerprints to a second window comprising a second set of fingerprints;   compute, based on the comparison, a first weight associated with the compared windows;   determine that the first and second windows are a match based on a comparison of the first weight and a first threshold;   select, based on the determination, a fingerprint from the first or second window;   compute a time associated with when the fingerprint was generated;   insert the first weight and the time into a matrix;   determine a number associated with a frequency of occurrences of the time in the matrix;   determine a depth associated with a previous occurrence of the time in the matrix;   determine based on the number and the depth a second threshold;   sum first weights associated with the occurrences of the time in the matrix; and   determine that the fingerprint is matched based on a comparison between the sum and the second threshold.   
     
     
         2 . The system of  claim 1 , further comprising circuitry to:
 divide a first list of fingerprints into a first set of windows, each window comprising a number of the fingerprints from the first list, wherein the first list of fingerprints is derived from data received from a remote device, wherein the data is associated with audio files detected at the remote device, and wherein a fingerprint from the first list is associated with an audio file from the audio files detected at the remote device;   divide a second list of fingerprints into a second set of windows, each window comprising a number of fingerprints from the second list, wherein the second list of fingerprints is derived from reference audio files, and wherein a fingerprint from the second list is associated with an audio file of the reference audio files;   compute an indicator for each fingerprint in each window, the indicator being associated with a location of the fingerprint in the window and being indicative of the time the fingerprint was generated; and   select the first window from the first set and the second window from the second set for comparison.   
     
     
         3 . The system of  claim 2 , wherein comparing fingerprints from the first window to fingerprints from the second window comprises:
 computing a number of bits that are different between a first fingerprint from the first window and a second fingerprint from the second window;   determining a third weight associated with the number of bits that are different;   comparing the third weight to a third threshold;   adding the third weight to a table based on the comparison, wherein the third weight is added at a location associated with the indicator of the first fingerprint and the indicator of the second fingerprint, and wherein the table comprises third weights associated with a comparison of fingerprints from the first and second windows; and   setting a largest weight in the table as the first weight.   
     
     
         4 . The system of  claim 3 , wherein the location is associated with a difference between the indicator of the first fingerprint and the indicator of the second fingerprint; and wherein selecting a fingerprint from the first or second window is based on a correlation between the largest weight and the fingerprint. 
     
     
         5 . The system of  claim 1 , wherein the circuitry comprises a field-programmable gate array. 
     
     
         6 . The system of  claim 1 , wherein the second threshold is retrieved from a look-up table that defines thresholds as a function of depths or as a function of depths and number of occurrences. 
     
     
         7 . The system of  claim 1 , further comprising circuitry configured to transmit information related to the matched fingerprint to a remote device in communication with the system over a network, wherein the transmission is in response to receiving fingerprints from the remote device. 
     
     
         8 . A method executed on a device, comprising:
 receiving, from a remote device, digital signatures associated with data;   deriving first fingerprints from the received digital signatures;   grouping the first fingerprints into meter groups, each meter group comprising a set of the first fingerprints;   comparing a first meter group from the meter groups to a reference group comprising second fingerprints to determine a similarity value associated with similarities between the first fingerprints in the first meter group and second fingerprints; and   determining that there is a match between at least a first fingerprint from the first meter group and a second fingerprint from the reference group based on the similarity value and similarity values generated by comparing other meter groups from the meter groups to the reference group.