Expanding a query to include terms associated through visual content

• US 7,882,124 B2
• Filed: 12/28/2007
• Issued: 02/01/2011
• Est. Priority Date: 12/20/2007
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Slaney, Malcolm, Sengamedu, Srinivasan H.
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Allen; Nicholas E
• Application Number:
  US11/966,704
• Publication Number:
  US 20090164456A1
• Time in Patent Office: 1,131 Days
• Field of Search: 707/765
• US Class Current: 707/765
• CPC Class Codes: G06F 16/5866 using information manually generated, e.g. tags, keywords, comments, manually generated location and time information

Abstract

A method for expanding a query to include additional terms associated through visual content is provided. A bipartite graph is constructed based on a database of visual content and associated textual content. One partition of the bipartite graph contains visual content and the other partition of the bipartite graph contains textual content. Weighted edges between nodes in the two partitions represent associations between the visual content and textual content in the database. Random walks on the bipartite graph are performed to derive probabilistic association scores between textual content that are indirectly associated with each other through visual content. The query is expanded to include additional terms whose equivalent textual content is highly associated with the query'"'"'s equivalent textual content.

Claims

1. A method for expanding a query, comprising the steps of:

storing a bipartite representation;

wherein the bipartite representation comprises a first set of nodes;

wherein each node in the first set of nodes represents a linguistic word;

wherein the bipartite representation comprises a second set of nodes;

wherein each node in the second set of nodes represents visual content;

receiving the query;

for at least one query term of the query, performing the steps of;

determining whether the at least one query term is associated with one or more other query terms through visual content;

wherein determining whether the at least one query term is associated with one or more other query terms through visual content comprises;

determining, based on the bipartite representation, an association score between (a) a first node of the bipartite representation, which represents a linguistic word associated with the at least one query term, and (b) a second node of the bipartite representation, which represents one or more other linguistic words associated with one or more other query terms;

determining, based on the association score, that the at least one query term is associated with the one or more other query terms through visual content;

in response to determining that the at least one query term is associated with one or more other query terms through visual content, creating an expanded query by adding at least one of the one or more other query terms to the query;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, further comprising:

performing a search based on the expanded query; and

returning results of the search as results for the query.

3. The method of claim 1, wherein the step of determining whether the at least one query term is associated with one or more other query terms through visual content is performed based on whether linguistic words that are equivalent to the at least one query term are associated, through the visual content, with linguistic words that are equivalent to the one or more other query terms.

4. The method of claim 1, further comprising:

accessing a set of data from the bipartite representation, wherein the set of data comprises a set of visual words representing visual content, a set of linguistic words, and a set of associations between the set of visual words and the set of linguistic words;

based on the set of associations between the set of visual words and the set of linguistic words, generating association scores between linguistic words;

wherein the step of determining, based on the bipartite representation, an association score is performed based at least in part on the association scores.

5. The method of claim 4, wherein the step of determining whether the at least one query term is associated with one or more other query terms through visual content further comprises:

identifying association scores between a linguistic word that is equivalent to the at least one query term and one or more other linguistic words in the set of linguistic words;

comparing the association scores between the linguistic word that is equivalent to the at least one query term and one or more other linguistic words in the set of linguistic words with a preset threshold to determine which of the one or more other linguistic words have association scores higher than the preset threshold;

wherein the step of determining, based on the association score, that the at least one query term is associated with the one or more other query terms through visual content comprises;

determining that the at least one query term is associated with query terms which are equivalent to linguistic words which have association scores higher than the preset threshold.

6. The method of claim 5, wherein the preset threshold is zero.

7. The method of claim 5, further comprising:

constructing, based on a set of data, the bipartite representation;

wherein the bipartite representation represents a bipartite graph that includes a first partition and a second partition;

wherein the first partition comprises the first set of nodes;

wherein the second partition comprises the second set of nodes;

wherein each node in the second set of nodes represents a visual word representing visual content in the set of visual words;

wherein the step of identifying association scores between a linguistic word that is equivalent to the at least one query term and one or more other linguistic words in the set of linguistic words, further comprises;

for each linguistic word in the one or more other linguistic words in the set of linguistic words,

for the first node of the bipartite graph that represents the linguistic word, which is associated with the at least one query term and the second node of the bipartite graph, which represents one or more other linguistic words associated with one or more other query terms, deriving, based on the bipartite graph, the association score between the first node and the second node.

8. The method of claim 7 wherein the step of deriving the association score between the first node and the second node includes:

generating a first set of scores based on a random walk through the bipartite graph;

generating a second set of scores based on a random walk, with restart from the first node, through the bipartite graph; and

deriving the association score based on the first set of scores and the second set of scores.

9. The method of claim 8, further comprising:

constructing a set of connections between the first set of nodes and the second set of nodes;

wherein each connection in the set of connections connects a node in the first set of nodes and a node in the second set of nodes if there is an association between the linguistic word represented by the node in the first set of nodes and the visual word represented by the node in the second set of nodes;

wherein each connection in the set of connections comprises a first directed edge and a second directed edge;

wherein the first directed edge is directed from the node in the first set of nodes to the node in the second set of nodes;

wherein the second directed edge is directed from the node in the second set of nodes to the node in the first set of nodes;

wherein the first directed edge is labeled with a first probability;

wherein the first probability indicates a probability that the visual word represented by the node in the second set of nodes occurs in an image in the set of images described by the linguistic word represented by the node in the first set of nodes;

wherein the second directed edge is labeled with a second probability;

wherein the second probability indicates a probability that the linguistic word represented by the node in the first set of nodes describes an image in the set of images in which the visual word represented by the node in the second set of nodes occurs;

wherein the random walk through the bipartite graph is performed based on probabilities labeled on directed edges in connections between nodes in the first set of nodes and nodes in the second set of nodes; and

wherein the random walk, with restart from the first node, through the bipartite graph is performed based on probabilities labeled on directed edges in connections between nodes in the first set of nodes and nodes in the second set of nodes, with restarts at the first node based on a restart probability.

10. The method of claim 4, wherein the set of data comprises a set of images;

and

wherein a visual word in the set of visual words is associated with a linguistic word in the set of linguistic words if the visual word occurs in an image described by the linguistic word.

11. The method of claim 1, wherein adding at least one of the one or more other query terms to the query comprises substituting the at least one query term of the query with at least one of the one or more other query terms to the query.

12. A non-transitory computer-readable storage medium storing instructions for expanding a query, the instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of:

storing a bipartite representation;

wherein the bipartite representation comprises a first set of nodes;

wherein each node in the first set of nodes represents a linguistic word;

wherein the bipartite representation comprises a second set of nodes;

wherein each node in the second set of nodes represents visual content;

receiving the query;

for at least one query term of the query, performing the steps of;

determining whether the at least one query term is associated with one or more other query terms through visual content;

wherein determining whether the at least one query term is associated with one or more other query terms through visual content comprises;

determining, based on the bipartite representation, an association score between (a) a first node of the bipartite representation, which represents a linguistic word associated with the at least one query term, and (b) a second node of the bipartite representation, which represents one or more other linguistic words associated with one or more other query terms;

determining, based on the association score, that the at least one query term is associated with the one or more other query terms through visual content;

in response to determining that the at least one query term is associated with one or more other query terms through visual content, creating an expanded query by adding at least one of the one or more other query terms to the query.

13. The non-transitory computer-readable storage medium of claim 12, further comprising instructions for;

performing a search based on the expanded query; and

returning results of the search as results for the query.

14. The non-transitory computer-readable storage medium of claim 12, wherein the instructions for determining whether the at least one query term is associated with one or more other query terms through visual content are performed based on whether linguistic words that are equivalent to the at least one query term are associated, through the visual content, with linguistic words that are equivalent to the one or more other query terms.

15. The non-transitory computer-readable storage medium of claim 14, further comprising instructions for:

accessing a set of data from the bipartite representation, wherein the set of data comprises a set of visual words representing visual content, a set of linguistic words, and a set of associations between the set of visual words and the set of linguistic words;

based on the set of associations between the set of visual words and the set of linguistic words, generating association scores between linguistic words;

wherein the instructions for determining, based on the bipartite representation, an association score are performed based at least in part on the association scores.

16. The non-transitory computer-readable storage medium of claim 15, wherein the instructions for determining whether the at least one query term is associated with one or more other query terms through visual content further comprises instructions for:

identifying association scores between a linguistic word that is equivalent to the at least one query term and one or more other linguistic words in the set of linguistic words;

comparing the association scores between the linguistic word that is equivalent to the at least one query term and one or more other linguistic words in the set of linguistic words with a preset threshold to determine which of the one or more other linguistic words have association scores higher than the preset threshold;

wherein the instructions for determining, based on the association score, that the at least one query term is associated with the one or more other query terms through visual content comprise instructions for;

determining that the at least one query term is associated with query terms which are equivalent to linguistic words which have association scores higher than the preset threshold.

17. The non-transitory computer-readable storage medium of claim 16, wherein the preset threshold is zero.

18. The non-transitory computer-readable storage medium of claim 16, further comprising instructions for:

constructing, based on a set of data, the bipartite representation;

wherein the bipartite representation represents a bipartite graph including a first partition and a second partition;

wherein the first partition comprises the first set of nodes;

wherein the second partition comprises a second set of nodes;

wherein each node in the second set of nodes represents a visual word representing visual content in the set of visual words;

wherein the instructions for identifying association scores between a linguistic word that is equivalent to the at least one query term and one or more other linguistic words in the set of linguistic words, further comprises instructions for;

for each linguistic word in the one or more other linguistic words in the set of linguistic words,

for the first node of the bipartite graph that represents the linguistic word, which is associated with the at least one query term and the second node of the bipartite graph, which represents one or more other linguistic words associated with one or more other query terms, deriving, based on the bipartite graph, the association score between the first node and the second node.

19. The non-transitory computer-readable storage medium of claim 18 wherein the instructions for deriving the association score between the first node and the second node includes:

generating a first set of scores based on a random walk through the bipartite graph;

generating a second set of scores based on a random walk, with restart from the first node, through the bipartite graph; and

deriving the association score based on the first set of scores and the second set of scores.

20. The non-transitory computer-readable storage medium of claim 19, further comprising instructions for:

constructing a set of connections between the first set of nodes and the second set of nodes;

wherein each connection in the set of connections connects a node in the first set of nodes and a node in the second set of nodes if there is an association between the linguistic word represented by the node in the first set of nodes and the visual word represented by the node in the second set of nodes;

wherein each connection in the set of connections comprises a first directed edge and a second directed edge;

wherein the first directed edge is directed from the node in the first set of nodes to the node in the second set of nodes;

wherein the second directed edge is directed from the node in the second set of nodes to the node in the first set of nodes;

wherein the first directed edge is labeled with a first probability;

wherein the first probability indicates a probability that the visual word represented by the node in the second set of nodes occurs in an image in the set of images described by the linguistic word represented by the node in the first set of nodes;

wherein the second directed edge is labeled with a second probability;

wherein the second probability indicates a probability that the linguistic word represented by the node in the first set of nodes describes an image in the set of images in which the visual word represented by the node in the second set of nodes occurs;

wherein the random walk through the bipartite graph is performed based on probabilities labeled on directed edges in connections between nodes in the first set of nodes and nodes in the second set of nodes; and

wherein the random walk, with restart from the first node, through the bipartite graph is performed based on probabilities labeled on directed edges in connections between nodes in the first set of nodes and nodes in the second set of nodes, with restarts at the first node based on a restart probability.

21. The non-transitory computer-readable storage medium of claim 15, wherein the set of data comprises a set of images;

and

wherein a visual word in the set of visual words is associated with a linguistic word in the set of linguistic words if the visual word occurs in an image described by the linguistic word.

22. The non-transitory computer-readable storage medium of claim 12, wherein instructions for adding at least one of the one or more other query terms to the query comprises instructions for substituting the at least one query term of the query with at least one of the one or more other query terms to the query.