Information retrieval engine

• US 20060242193A1
• Filed: 06/22/2006
• Published: 10/26/2006
• Est. Priority Date: 05/03/2000
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Ted E. Dunning
• Inventors: Dunning, Ted E.
• Granted Patent: US 7,720,852 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/634 Query by example, e.g. query by humming
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: Y10S 707/916 Audio
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system, method, and computer program product retrieve information associated with the signals. The information retrieval can be performed on a signal by quantizing the signal, forming words, and indexing based on weights of the words. The words are formed by grouping letters together to form a number of words within predetermined threshold values. The weights of the words are determined using a binomial log likelihood ratio analysis. The present invention may be applied to identification of an unknown song.

Claims

1. A computer-implemented method comprising:

accepting a file and information corresponding to the file;

associating the file and the information corresponding to the file;

organizing the file into at least one document comprising at least a portion of the file;

associating the file and the document corresponding to the file;

quantizing the document to obtain letters;

grouping the letters to form a set of words, the set being based on a predetermined frequency of occurrence of the grouped letters;

associating each document and the corresponding set of words in an index of documents;

obtaining a set of query words;

identifying one or more documents in the index, each of the identified documents containing at least one query word in the set of query words; and

scoring each of the identified documents, a score for each identified document being based at least in part on a weighting of each query word found in the identified document, the weighting being determined using a local weighting factor and a global weighting factor.

2. The computer-implemented method of claim 1, wherein the file is an audio file.

3. The computer-implemented method of claim 2, wherein the audio file is a song.

4. The computer implemented method of claim 2, wherein the audio file is a compressed song.

5. The computer-implemented method of claim 2, wherein the audio file is a portion of a song.

6. The computer-implemented method of claim 1, wherein grouping the letters comprises:

searching for frequently appearing letters; and

searching for frequently appearing n-grams, where n is any integer.

7. The computer-implemented method of claim 6, wherein frequently is determined by predetermined threshold limits.

8. The computer-implemented method of claim 1, wherein the quantization is performed using an EM algorithm.

9. The computer-implemented method of claim 1, wherein the quantization is performed using an incremental algorithm.

10. The computer-implemented method of claim 1, wherein the quantization is performed using a Gaussian mixture algorithm.

28. The computer-implemented method of claim 1, wherein scoring each of the identified documents further comprises scoring each of the identified documents using a normalization factor.

29. The computer-implemented method of claim 28, wherein the normalization factor is

$n_c=\frac{1}{\sqrt{\sum _{}}}$

j ⁢

( l j ) 2 ⁢

( g ij ) 2 ,

where l_j represents the number of times a word appears in the query and g_ij represents the number of times a word appears in the documents in the index.

30. The computer-implemented method of any one of claims 1, 28 and 29, wherein the local weighting factor is k_ij, where k_ij represents the number of query words in the set of query words.

31. The computer-implemented method of any one of claims 1, 28 and 29, wherein the local weighting factor is log k_ij, where k_ij represents the number of query words in the query.

32. The computer-implemented method of any one of claims 1, 28 and 29, wherein the local weighting factor is one.

33. The computer-implemented method of any one of claims 1, 28 and 29, wherein the global weighting factor is

$\log$

N + 1 DF j + 1 ,

wherein N represents the total number of documents and DF represents the document frequency.

34. The computer-implemented method of any one of claims 1, 28 and 29, wherein the global weighting factor is one.

35. The computer-implemented method claim 1, wherein the at least one document into which the file is organized comprises multiple documents having the same length.

37. The computer-implemented method of claim 35, wherein the length comprises thirty seconds.

38. The computer-implemented method of claim 35, wherein the at least one document comprises multiple documents each one of the multiple documents overlapping with another one of the multiple documents.

39. The computer-implemented method of claim 38, wherein the overlap comprises a twenty-five second overlap.

11. (canceled)

12. The computer-implemented method of claim 11 wherein obtaining a set of query words comprises:

receiving a query;

quantizing the query to output a series of letters;

grouping the letters to form a set of query words, the set of query words being based on a predetermined frequency of the occurrence of the grouped letters;

13. The computer-implemented method of claim 12, further comprising separating the received query to form a plurality of documents.

14. The computer-implemented method of claim 13, wherein each of the plurality of formed documents and each document in the index is the same length.

15. The computer-implemented method of claim 13, wherein the length is thirty seconds.

16. The computer-implemented method of claim 15, wherein each one of the formed documents overlaps with an adjacent one of the formed documents.

17. The computer-implemented method of claim 16, wherein the overlap comprises a twenty-five second overlap.

18. The computer-implemented method of claim 16, wherein the overlap comprises a fifteen-second overlap.

19. The computer-implemented method of claim 12, wherein a query weighting is determined using a local weighting factor and a global weighting factor.

20. The computer-implemented method of claim 12, wherein a query weighting is determined using a local weighting factor, a global weighting factor, and a normalization factor.

21. The computer-implemented method of claim 20, wherein the normalization factor is

$n_c=\frac{1}{\sqrt{\sum _{}}}$

j ⁢

( l j ) 2 ⁢

( g ij ) 2 ,

where l_j represents the number of times a word appears in the query and g_ij represents the number of times a word appears in the documents in the index.

22. The computer-implemented method of any of claims 19 to 21, wherein the local weighting factor is k_ij, where k_ij represents the number of query words in the set of query words.

23. The computer-implemented method of any of claims 19 to 21, wherein the local weighting factor is log k_ij, where k_ij represents the number of query words in the set of query words.

24. The computer-implemented method of any of claims 19 to 21, wherein the local weighting factor is one.

25. The computer-implemented method of any of claims 19 to 21, wherein the global weighting factor is

$\log$

N + 1 DF j + 1 ,

wherein N represents the total number of documents and DF represents the document frequency.

26. The computer-implemented method of any of claims 19 to 21, wherein the global weighting factor is one.

27. (canceled)

36. (canceled)

40-112. -112. (canceled)