Information retrieval engine

US 7,162,482 B1
Filed: 06/11/2002
Issued: 01/09/2007
Est. Priority Date: 05/03/2000
Status: Expired due to Term

First Claim

Patent Images

1. The computer-implemented method comprising:

providing an index of one or more files, the index associating each file with information corresponding to the file and one or more documents, each document containing one or more associated words;

accepting a query containing a file;

quantizing the file to obtain letters;

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

weighting each word in the set of words, such that the weighting of each word in the set is determined using a local weighting factor and a global weighting factor;

searching the index for at least one document containing at least one of the words in the set;

scoring each document in the index containing at least one of the words in the set; and

identifying the file corresponding to the document with the highest score.

View all claims

10 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

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.

226 Citations

89 Claims

1. The computer-implemented method comprising:
- providing an index of one or more files, the index associating each file with information corresponding to the file and one or more documents, each document containing one or more associated words;
  
  accepting a query containing a file;
  
  quantizing the file to obtain letters;
  
  grouping the letters to form a set of words, the set being based on frequency of the occurrence of the grouped letters;
  
  weighting each word in the set of words, such that the weighting of each word in the set is determined using a local weighting factor and a global weighting factor;
  
  searching the index for at least one document containing at least one of the words in the set;
  
  scoring each document in the index containing at least one of the words in the set; and
  
  identifying the file corresponding to the document with the highest score.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
- - 2. The computer-implemented method of claim 1, further comprising separating the file into a plurality of documents.
  - 3. The computer-implemented method of claim 2, wherein each document is the same length as each document in the index.
  - 4. The computer-implemented method of claim 2, wherein each document is thirty seconds in length.
  - 5. The computer-implemented method of claim 4, wherein each document overlaps with an adjacent document.
  - 6. The computer-implemented method of claim 5, wherein the overlap is twenty five seconds long.
  - 7. The computer-implemented method of claim 5, wherein the overlap is fifteen seconds long.
  - 8. The computer-implemented method of claim 1, further comprising determining the weighting of each word using a normalization factor.
  - 9. The computer-implemented method of claim 8, wherein the normalization factor is $n_{c} = \frac{1}{\sqrt{\sum}}$
    - j ⁢
      
      ( l j ) 2 ⁢
      
      ( g ij ) 2 , where l_jrepresents the number of times a word appears in the query and g_ijrepresents the number of times a word appears in the documents in the index.
  - 10. The computer-implemented method of claim 1, wherein the local weighting factor is k_ij, where k_ijrepresents the number of words in the query.
  - 11. The computer-implemented method of claim 1, wherein the local weighting factor is log k_ij, where k_ijrepresents the number of words in the query.
  - 12. The computer-implemented method of claim 1, wherein the local weighting factor is one.
  - 13. The computer-implemented method of claim 1, wherein the global weighting factor is log $\frac{N + 1}{{DF}_{j} + 1},$ wherein N represents the total number of documents and DF represents the document frequency.
  - 14. The computer-implemented method of claim 1, wherein the global weighting factor is one.
  - 15. The computer-implemented method of claim 1, wherein scoring the documents comprising applying a local weighting factor and a global weighting factor.
  - 16. The computer-implemented method of claim 15 further comprising determining the weighting of each word using a normalization factor.
  - 17. The computer-implemented method of claim 16, wherein the normalization factor is $n_{c} = \frac{1}{\sqrt{\sum}}$
    - j ⁢
      
      ( l j ) 2 ⁢
      
      ( g ij ) 2 , where l_jrepresents the number of times a word appears in the query and g_ijrepresents the number of times a word appears in the documents in the index.
  - 18. The computer-implemented method of claim 15, wherein the local weighting factor is k_ij, where k_ijrepresents the number of words in the query.
  - 19. The computer-implemented method of claim 15, wherein the local weighting factor is log k_ij, where k_ijrepresents the number of words in the query.
  - 20. The computer-implemented method of claim 15, wherein the local weighting factor is one.
  - 21. The computer-implemented method of claim 15, wherein the global weighting factor is log $\frac{N + 1}{{DF}_{j} + 1},$ wherein N represents the total number of documents and DF represents the document frequency.
  - 22. The computer-implemented method of claim 15, wherein the global weighting factor is one.
  - 23. The computer-implemented method of claim 1, further comprising:
    - retrieving the information corresponding to the identified file.

24. A computer-implemented method of retrieving information from a signal quantized into clusters of data comprising:
- accepting a query including at least a subset of the clusters of data;
  
  organizing the clusters into words based on frequency of occurrence of the clusters;
  
  searching an index for the words in query, the index comprising;
  
  a plurality of known signals;
  
  a plurality of known information corresponding to the known signals;
  
  a plurality of corresponding clusters of data;
  
  a plurality of corresponding documents organized into words;
  
  weighting the words in the query, such that the weighting of each word in the query is determined using a local weighting factor and a global weighting factor;
  
  scoring the documents in the index containing the words in the query; and
  
  retrieving information associated with the known document having the highest score.
- View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44)
- - 25. The computer-implemented method of claim 24, wherein organizing the clusters into words comprises:
    - searching for frequently occurring letters; and
      
      adding adjacent letters to for frequently occurring n-grams.
  - 26. The computer-implemented method of claim 25, wherein searching for frequently occurring letters comprises comparing letter frequency with at least one predetermined threshold value.
  - 27. The computer-implemented method of claim 24, wherein the information retrieval is applied to retrieve tag information of a music track.
  - 28. The computer-implemented method of claim 27, wherein the music track is a trimmed song.
  - 29. The computer-implemented method of claim 27, wherein the music track is a compressed song.
  - 30. The computer-implemented method of claim 24, further comprising determining the weighting of each word using a normalization factor.
  - 31. The computer-implemented method of claim 30, wherein the normalization factor is $n_{c} = \frac{1}{\sqrt{\sum}}$
    - j ⁢
      
      ( l j ) 2 ⁢
      
      ( g ij ) 2 , where l_jrepresents the number of times a word appears in the query and g_ijrepresents the number of times a word appears in the documents in the index.
  - 32. The computer-implemented method of claim 24, wherein the local weighting factor is k_ij, where k_ijrepresents the number of words in the query.
  - 33. The computer-implemented method of claim 24, wherein the local weighting factor is log k_ij, where k_ijrepresents the number of words in the query.
  - 34. The computer-implemented method of claim 24, wherein the local weighting factor is one.
  - 35. The computer-implemented method of claim 24, wherein the global weighting factor is log $\frac{N + 1}{{DF}_{j} + 1},$ wherein N represents the total number of documents and DF represents the document frequency.
  - 36. The computer-implemented method of claim 24, wherein the global weighting factor is one.
  - 37. The computer-implemented method of claim 24, wherein scoring the documents comprises applying a local weighting factor and a global weighting factor.
  - 38. The computer-implemented method of claim 37, further comprising determining the weighting of each word using a normalization factor.
  - 39. The computer-implemented method of claim 38, wherein the normalization factor is $n_{c} = \frac{1}{\sqrt{\sum}}$
    - j ⁢
      
      ( l j ) 2 ⁢
      
      ( g ij ) 2 , where l_jrepresents the number of times a word appears in the query and g_ijrepresents the number of times a word appears in the documents in the index.
  - 40. The computer-implemented method of claim 37, wherein the local weighting factor is k_ij, where k_ijrepresents the number of words in the query.
  - 41. The computer-implemented method of claim 37, wherein the local weighting factor is log k_ij, where k_ijrepresents the number of words in the query.
  - 42. The computer-implemented method of claim 37, wherein the local weighting factor is one.
  - 43. The computer-implemented method of claim 37, wherein the global weighting factor is log $\frac{N + 1}{{DF}_{j} + 1},$ wherein N represents the total number of documents and DF represents the document frequency.
  - 44. The computer-implemented method of claim 37, wherein the global weighting factor is one.

45. A system comprising:
- a query input device for accepting a query including clusters of data representing an unknown signal;
  
  an organization module, coupled to the query input device, for receiving letters as input and organizing the clusters into a set of words based on frequency of occurrence of the words;
  
  an index, coupled to the organization module, comprising;
  
  a plurality of known signals;
  
  a plurality of known information corresponding to the known signals;
  
  a plurality of corresponding clusters of data organized into words;
  
  a plurality of corresponding documents;
  
  a search module, coupled to the index, for searching the index for a document containing a word in the query;
  
  a weight module, coupled to the organization module, for receiving one word in the set of words as input and determining a weight associated with the word, such that the weight module uses a local weighting factor and a global weighting factor to determine the weight associated with the word;
  
  a score module, coupled to the search module, for receiving the document containing the word in the query as input and determining a score associated with the document; and
  
  an information retrieval engine coupled to the score module for retrieving the information corresponding to the known document with the highest score determined by the score module.
- View Dependent Claims (46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67)
- - 46. The system of claim 45, wherein the information retrieval is applied to retrieve tag information of a music track.
  - 47. The system of claim 46, wherein the music track is a compressed song.
  - 48. The system of claim 45, wherein the music track is a trimmed song.
  - 49. The system of claim 45, wherein the documents are thirty seconds in length.
  - 50. The system of claim 49, wherein each document overlaps with an adjacent document.
  - 51. The system of claim 49, wherein the overlap is twenty five seconds in length.
  - 52. The system of claim 49, wherein the overlap is fifteen seconds in length.
  - 53. The system of claim 45, wherein the weight module further uses a normalization factor to determine the weight associated with each word.
  - 54. The system of claim 53, wherein the normalization factor is $n_{c} = \frac{1}{\sqrt{\sum}}$
    - j ⁢
      
      ( l j ) 2 ⁢
      
      ( g ij ) 2 , where l_jrepresents the number of times a word appears in the query and g_ijrepresents the number of times a word appears in the documents in the index.
  - 55. The system of claim 45, wherein the local weighting factor is k_ij, where k_ijrepresents the number of words in the query.
  - 56. The system of claim 45, wherein the local weighting factor is log k_ij, where k_ijrepresents the number of words in the query.
  - 57. The system of claim 45, wherein the local weighting factor is one.
  - 58. The system of claim 45, wherein the global weighting factor is log $\frac{N + 1}{{DF}_{j} + 1},$ wherein N represents the total number of documents and DF represents the document frequency.
  - 59. The system of claim 45, wherein the global weighting factor is one.
  - 60. The system of claim 45, wherein the wherein the score module uses a local weighting factor and a global weighting factor to generate the score associated with the document.
  - 61. The system of claim 60 further comprising determining the weighting of each word using a normalization factor.
  - 62. The system of claim 61, wherein the normalization factor is $n_{c} = \frac{1}{\sqrt{\sum}}$
    - j ⁢
      
      ( l j ) 2 ⁢
      
      ( g ij ) 2 , where l_jrepresents the number of times a word appears in the query and g_ijrepresents the number of times a word appears in the documents in the index.
  - 63. The system of claim 60, wherein the local weighting factor is k_ij, where k_ijrepresents the number of words in the query.
  - 64. The system of claim 60, wherein the local weighting factor is log k_ij, where k_ijrepresents the number of words in the query.
  - 65. The system of claim 60, wherein the local weighting factor is one.
  - 66. The system of claim 60, wherein the global weighting factor is log $\frac{N + 1}{{DF}_{j} + 1},$ wherein N represents the total number of documents and DF represents the document frequency.
  - 67. The system of claim 60, wherein the global weighting factor is one.

68. A computer-readable medium comprising computer-readable code, comprising:
- computer-readable code adapted to accept a query including at least a subset of the clusters of data;
  
  computer-readable code adapted to organize the clusters of data into words based on frequency of occurrence of the words;
  
  computer-readable code adapted to search an index for the words in the query, the index comprising;
  
  a plurality of known signals;
  
  a plurality of known information corresponding to the known signals;
  
  a plurality of corresponding clusters of data organized into words;
  
  a plurality of corresponding documents;
  
  computer-readable code adapted to weight the words in the query and to score the documents in the index which contain the words in the query, such that a local weighting factor and a global weighting factor are used to weight the words in the query, to score the documents in the index, or both; and
  
  computer-readable code adapted to retrieve information associated with the known document with the highest score.
- View Dependent Claims (69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89)
- - 69. The computer-readable medium of claim 68, wherein the information retrieval is applied to retrieve tag information of a music track.
  - 70. The computer-readable medium of claim 69, wherein the music track is a trimmed song.
  - 71. The computer-readable medium of claim 69, wherein the music track is a compressed song.
  - 72. The computer-readable medium of claim 68, wherein each document is thirty seconds in length.
  - 73. The computer-readable medium of claim 68, wherein each document overlaps with an adjacent document.
  - 74. The computer-readable medium of claim 73, wherein the overlap is twenty five seconds in length.
  - 75. The computer-readable medium of claim 73, wherein the overlap is fifteen seconds in length.
  - 76. The computer-readable medium of claim 68, further comprising computer-readable code adapted to determine the weighting of each word using a normalization factor.
  - 77. The computer-readable medium of claim 76, wherein the normalization factor is $n_{c} = \frac{1}{\sqrt{\sum}}$
    - j ⁢
      
      ( l j ) 2 ⁢
      
      ( g ij ) 2 , where l_jrepresents the number of times a word appears in the query and g_ijrepresents the number of times a word appears in the known documents.
  - 78. The computer-readable medium of claim 68, wherein the local weighting factor is k_ij, where k_ijrepresents the number of words in the query.
  - 79. The computer-readable medium of claim 68, wherein the local weighting factor is log k_ij, where k_ijrepresents the number of words in the query.
  - 80. The computer-readable medium of claim 68, wherein the local weighting factor is one.
  - 81. The computer-readable medium of claim 68, wherein the global weighting factor is log $\frac{N + 1}{{DF}_{j} + 1},$ wherein N represents the total number of documents and DF represents the document frequency.
  - 82. The computer-readable medium of claim 68, wherein the global weighting factor is one.
  - 83. The computer-readable medium of claim 68, further comprising computer-readable code adapted to determine the weighting of each word using a normalization factor.
  - 84. The computer-readable medium of claim 83, wherein the normalization factor is $n_{c} = \frac{1}{\sqrt{\sum}}$
    - j ⁢
      
      ( l j ) 2 ⁢
      
      ( g ij ) 2 , where l_jrepresents the number of times a word appears in the query and g_ijrepresents the number of times a word appears in the known documents.
  - 85. The computer-readable medium of claim 68, wherein the local weighting factor is k_ij, where k_ijrepresents the number of words in the query.
  - 86. The computer-readable medium of claim 68, wherein the local weighting factor is log k_ij, where k_ijrepresents the number of words in the query.
  - 87. The computer-readable medium of claim 68, wherein the local weighting factor is one.
  - 88. The computer-readable medium of claim 68, wherein the global weighting factor is log $\frac{N + 1}{{DF}_{j} + 1},$ wherein N represents the total number of documents and DF represents the document frequency.
  - 89. The computer-readable medium of claim 68, wherein the global weighting factor is one.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
R2 Solutions LLC (Acacia Research Corporation)
Original Assignee
MusicMatch Incorporated (Apollo Global Management, Inc.)
Inventors
Dunning, Ted E.
Primary Examiner(s)
Gaffin; Jeffrey
Assistant Examiner(s)
Hicks; Michael J.

Application Number

US10/167,807
Time in Patent Office

1,673 Days
Field of Search

707/102, 846/45
US Class Current

707/737
CPC Class Codes

G06F 16/3334   Selection or weighting of t...

G06F 16/634   Query by example, e.g. quer...

G06F 16/683   using metadata automaticall...

Y10S 707/916   Audio

Y10S 707/99943   Generating database or data...

Information retrieval engine

First Claim

10 Assignments

0 Petitions

Accused Products

Abstract

226 Citations

89 Claims

Specification

Solutions

Use Cases

Quick Links

Information retrieval engine

First Claim

10 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

226 Citations

89 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links