System and method for fingerprinting datasets

• US 10,552,457 B2
• Filed: 01/19/2018
• Issued: 02/04/2020
• Est. Priority Date: 03/28/2012
• Status: Active Grant

• Current Assignee: Genesys Telecommunications Laboratories Incorporated (Genesys Cloud Services Incorporated)
• Original Assignee: Interactive Intelligence Group Incorporated (Genesys Cloud Services Incorporated)
• Inventors: Vlack, Kevin, Wyss, Felix Immanuel
• Primary Examiner(s): Elahee, Md S
• Application Number:
  US15/876,050
• Publication Number:
  US 20180144040A1
• Time in Patent Office: 746 Days
• Field of Search: 704270, 704219, 380255, 380257, 386260, 726 26, 703176, 711216, 713176
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G10L 19/018 Audio watermarking, i.e. embedding inaudible data in the audio signal
• CPC Class Codes: G10L 25/54 for retrieval
• CPC Class Codes: H03M 7/3059 Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression
• CPC Class Codes: H03M 7/3066 by means of a mask or a bit-map
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H04M 2203/2027 Live party detection
• CPC Class Codes: H04M 3/5158 in combination with automated outdialling systems devices for signalling identity of wanted subscriber H04M1/26

Abstract

Systems and methods for the matching of datasets, such as input audio segments, with known datasets in a database are disclosed. In an illustrative embodiment, the use of the presently disclosed systems and methods is described in conjunction with recognizing known network message recordings encountered during an outbound telephone call. The methodologies include creation of a ternary fingerprint bitmap to make the comparison process more efficient. Also disclosed are automated methodologies for creating the database of known datasets from a larger collection of datasets.

Claims

1. A method for matching an audio stream comprising the steps of:

a. generating a collection of ternary acoustic fingerprint bitmaps;

b. subdividing each ternary acoustic fingerprint bitmap into a plurality of segments;

c. obtaining a hash key from each segment; and

d. aggregating obtained hash keys from the ternary acoustic fingerprint bitmaps into a lookup table.

2. The method of claim 1, wherein said ternary acoustic fingerprint bitmap is generated for an audio object to detect.

3. The method of claim 1, wherein the generating of step (a) further comprises the step of generating a number of ternary values per frame of audio.

4. The method of claim 1, wherein the plurality of segments are equal in length.

5. The method of claim 1, wherein the plurality of segments comprises four equal segments.

6. A method for matching an audio stream comprising the steps of:

a. generating a collection of ternary acoustic fingerprint bitmaps;

b. subdividing each ternary acoustic fingerprint bitmap into a plurality of segments;

c. obtaining a hash key from each segment; and

d. aggregating obtained hash keys from the ternary acoustic fingerprint bitmaps into a lookup table,

wherein the hash key of step (c) is obtained by extracting a number of ternary values from ternary values of a number of frames from each segment.

7. The method of claim 6, wherein the number of frames of each segment evenly divides the number of ternary values.

8. The method of claim 7, wherein said number of ternary values is 128.

9. A method for matching an audio stream comprising the steps of:

a. generating a collection of ternary acoustic fingerprint bitmaps;

b. subdividing each ternary acoustic fingerprint bitmap into a plurality of segments;

c. obtaining a hash key from each segment;

d. aggregating obtained hash keys from the ternary acoustic fingerprint bitmaps into a lookup table,

e. generating a number of bit vectors from a number of input audio frames;

f. combining the bit vectors into a binary hash key;

g. comparing the binary hash key from step (f) against all obtained hash keys in the lookup table; and

h. identifying audio fingerprints corresponding to matching hash keys, wherein, if a match is not found, repeating the method from step (e).

10. The method of claim 9, wherein the binary hash key comprises a number of bits.

11. The method of claim 10, wherein the number of input audio frames evenly divides the number of bits.

12. The method of claim 11, wherein the number of bits is 128.

13. The method of claim 9, wherein said comparing of step (g) is performed by computing a masked Hamming distance.

14. The method of claim 13, wherein said computing is parallelized and optimized with at least one of:

Single-Instruction-Multiple Data Instructions and population count instruction.

15. The method of claim 13, wherein said hash keys in the lookup table match with a low masked Hamming distance.

16. The method of claim 9, wherein step (h) further comprises the steps of:

a. performing a first match with a first criteria;

b. identifying fingerprints matching said first criteria as candidate matches;

c. performing a second match on said candidate matches with a second criteria; and

d. declaring candidate matches meeting the second criteria a match.

17. The method of claim 16, wherein the first criteria and the second criteria are derived from a bit error rate.

18. The method of claim 17, wherein at least one of:

said first criteria comprises a lower number of standard deviations and said second criteria comprises a higher number of standard deviations.

19. The method of claim 18, wherein at least one of:

said lower number is 3 and said higher number is 9.