Finding web pages relevant to multimedia streams

• US 8,868,543 B1
• Filed: 04/08/2003
• Issued: 10/21/2014
• Est. Priority Date: 11/20/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.), Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Inventors: Henzinger, Monika H., Chang, Bay-Wei, Brin, Sergey
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Black, Linh
• Application Number:
  US10/408,784
• Time in Patent Office: 4,214 Days
• Field of Search: 707 1-1041, 707/713, 707/721, 707765-768, 707748-751
• US Class Current: 707/713
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

A media stream, such as a news broadcast, is supplemented with documents that are relevant to the media stream. The documents may be web pages returned from a search engine. A search query generation component generates search queries for the search engine based on the media stream. A post processing component may re-rank and/or filter the documents to enhance the viewing experience for the user.

Claims

1. A method comprising:

automatically converting, using one or more processors, a portion of a multimedia stream to text;

generating, using one or more processors, search queries from one or more terms extracted from the text;

receiving, using one or more processors, ranked documents relevant to the multimedia stream based on the search queries;

computing, using one or more processors, weights for the ranked documents based on one or more additional terms extracted from the text that were not used to identify the ranked documents,

computing the weights for the ranked documents including;

calculating a value, for a particular ranked document of the ranked documents, using a mathematical calculation,

the mathematical calculation being based on a first function and a second function,

 

the first function being based on;

 

a frequency of occurrence of the one or more additional terms in the particular ranked document, and

 

an inverse document frequency of the one or more additional terms, and

 

the second function being based on the frequency of occurrence of the one or more additional terms in the particular ranked document, and

determining the weight for the particular ranked document using the calculated value;

re-ranking, using one or more processors, the ranked documents to obtain re-ranked documents,

where re-ranking the ranked documents comprises modifying rankings of the ranked documents based on the computed weights; and

providing the re-ranked documents and the multimedia stream for presentation to a user,

the re-ranked documents being provided with the multimedia stream for presentation to the user.

2. The method of claim 1, where the search queries are automatically and periodically generated.

3. The method of claim 1, further comprising:

transmitting the search queries to a search engine to identify the ranked documents relevant to the multimedia stream,

the identified ranked documents being ranked according to a relevance to the search queries.

4. The method of claim 3, where the ranked documents are web pages.

5. The method of claim 1, where re-ranking the ranked documents further comprises:

filtering the ranked documents to remove at least one of the ranked documents that is dissimilar to the text derived from the multimedia stream.

6. The method of claim 1, where re-ranking the ranked documents further comprises:

calculating a similarity value between the ranked documents.

7. The method of claim 1, where re-ranking the ranked documents further comprises:

calculating a similarity value between the text and the ranked documents.

8. The method of claim 1, where generating the search queries includes:

calculating, for each term in a segment of the text, a product tf·

idf,

where tf refers to a frequency of the term in the segment and idf refers to an inverse document frequency, and

selecting a predetermined number of terms, from the segment, with highest product values out of one or more product values for one or more other terms from the segment.

9. The method of claim 1, where generating search queries includes:

calculating, for each term in a segment of the text, a product tf·

idf²,

where tf refers to a frequency of the term in the segment and idf refers to an inverse document frequency, and

selecting a predetermined number of terms, from the segment, with highest product values out of one or more product values for one or more other terms from the segment.

10. The method of claim 1, where generating search queries includes:

assigning terms, in a segment of the text, to groups, and

selecting terms for the search queries based on the groups.

11. The method of claim 10, where the terms, in the segment of the text, is assigned to the groups based on stems of the terms in the segment of the text.

12. The method of claim 10, where generating search queries include:

using segments of the text, previous to the segment of text, when generating the search queries.

13. The method of claim 1, where the multimedia stream is a television signal.

14. A system comprising:

a user device to;

automatically convert a portion of a multimedia stream to text;

periodically generate search queries based on one or more terms from the text converted from the multimedia stream,

a set of ranked web documents, related to topics in the multimedia stream, being identified based on the search queries;

compute weights for the set of ranked web documents based on one or more additional terms from the text that were not used to generate the search queries,

when computing the weights for the ranked documents the user device to;

calculate a value, for a particular ranked web document of the set of ranked web documents, using a mathematical calculation,

 

the mathematical calculation being based on;

 

a first function that is based on a frequency of occurrence of the one or more additional terms in the particular ranked web document and an inverse document frequency of the one or more additional terms, and

 

a second function that is based on the frequency of occurrence of the one or more additional terms in the particular ranked web document, and

determine the weight for the particular ranked document using the calculated value,

modify rankings of the set of ranked web documents based on the computed weights to obtain a set of re-ranked web documents; and

concurrently present information regarding the multimedia stream and the set of re-ranked web documents.

15. The system of claim 14, where the multimedia stream is a television signal.

16. The system of claim 14, where the user device includes at least one of:

a computer monitor, or

a television set.

17. The system of claim 14, where the user device, when modifying the rankings of the set of ranked web documents, is further to:

filter the set of ranked web documents to remove web documents, in the set of ranked web documents, that are dissimilar to the text.

18. The system of claim 14, where the user device, when modifying the rankings of the set of ranked web documents, is further to:

calculate a similarity value between the text and the set of ranked web documents.

19. The system of claim 14, where, when periodically generating the search queries, the user device is further to:

calculate, for each term in a segment of the text, a product tf·

idf,

where tf refers to a frequency of the term in the segment and idf refers to an inverse document frequency, and

select a predetermined number of terms, from the segment, with highest product values.

20. The system of claim 14, where, when periodically generating the search queries, the user device is further to:

calculate, for each term in a segment of the text, a product tf·

idf²,

where tf refers to a frequency of the term in the segment and idf refers to an inverse document frequency; and

select a predetermined number of terms, from the segment, with highest product values out of one or more product values for one or more other terms from the segment.

21. The system of claim 14, where the user device is further to:

assign terms in a segment of the text to groups, and

select terms for the search queries based on the groups.

22. The system of claim 21, where the terms, in the segment of the text, are assigned to the groups based on stems of the terms.

23. The system of claim 21, where, when periodically generating the search queries, the user device is further to:

use segments of the text, previous to the segment of text, when generating the search queries.

24. A device comprising:

a processor to execute instructions to;

automatically convert a portion of a multimedia stream to text;

generate one or more search queries using one or more terms from the text;

receive a set of ranked documents relevant to the multimedia stream based on the one or more search queries;

compute weights for the set of ranked documents based on one or more additional terms from the text that were not used to identify the set of ranked documents

when computing the weights for the set of ranked documents, the processor is to;

calculate a value, for a particular ranked document of the set of ranked documents, using a mathematical calculation,

 

the mathematical calculation being based on a first function and a second function,

 

the first function being based on;

 

a frequency of occurrence of the one or more additional terms in the particular ranked document, and

 

an inverse document frequency of the one or more additional terms, and

 

the second function being based on the frequency of occurrence of the one or more additional terms in the particular ranked document, and

determine the weight for the particular ranked document using the calculated value; and

modify rankings of the set of ranked documents, based on the computed weights, to obtain a set of re-ranked documents,

the set of re-ranked documents being provided with the multimedia stream for presentation.

28. The device of claim 24, where, when receiving the set of ranked documents, the processor is further to:

filter the received documents to remove at least one of the set of ranked documents that is dissimilar to the text converted from the multimedia stream.

29. The device of claim 24, where, when receiving the set of ranked documents, the processor is further to:

calculate a similarity value between the set of ranked documents.

30. The device of claim 24, where the first function is further based on a frequency of occurrence of the one or more additional terms in a title of the particular ranked document.

25. A computer-readable medium storing instructions, the instructions comprising:

a plurality of instructions that when executed by a processor, cause the processor to;

automatically convert a portion of a multimedia stream to text;

generate one or more search queries from the text;

receive ranked documents relevant to the multimedia stream based on the one or more search queries;

compute weights for the ranked documents based on one or more additional terms, from the text, that were not used to identify the ranked documents,

one or more instructions, of the plurality of instructions, to compute the weights for the ranked documents including;

one or more instructions to calculate a value, for a particular ranked document of the ranked documents, using a mathematical calculation,

 

the mathematical calculation being based on;

 

a first function that is based on a frequency of occurrence of the one or more additional terms in the particular ranked document and an inverse document frequency of the one or more additional terms, and

 

a second function that is based on the frequency of occurrence of the one or more additional terms in the particular ranked document, and

one or more instructions to determine the weight for the particular ranked document using the calculated value;

modify rankings of the ranked documents, based on the computed weights, to obtain re-ranked documents; and

present the re-ranked documents to a user simultaneously with the multimedia stream.

26. The computer-readable medium of claim 25, where the one or more search queries are periodically generated.

27. The computer-readable medium of claim 25, the instructions further comprising:

one or more instructions to remove at least one search term from the one or more search queries to form one or more new search queries when no documents can be identified based on the one or more search queries.