Detecting social graph elements for structured search queries

• US 8,782,080 B2
• Filed: 07/23/2012
• Issued: 07/15/2014
• Est. Priority Date: 04/19/2010
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Lee, Yofay Kari, Cohen, Michael Benjamin, Boucher, Maxime, Azzolini, Alisson Gusatti, Li, Xiao, Rasmussen, Lars Eilstrup
• Primary Examiner(s): Casanova, Jorge A
• Application Number:
  US13/556,072
• Publication Number:
  US 20130191416A1
• Time in Patent Office: 722 Days
• Field of Search: 707/722, 707/727, 707/728, 707/732, 707/769, 707/784, 707/798, 707/802, 707/771
• US Class Current: 707/771
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

In particular embodiments, a method includes receiving an unstructured text query, parsing the text query to identify n-grams; determining a score that the n-grams correspond to particular nodes and edges from a social graph, identifying those nodes and edges with a score greater than a threshold score, and then generating structured queries that include references to the identified nodes and edges.

Claims

1. A method comprising, by one or more computing devices:

accessing a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising;

a first-user node corresponding to a first user associated with an online social network; and

a plurality of second nodes that each correspond to a concept or a second user associated with the online social network;

receiving from the first user a substantially unstructured text query;

parsing the text query to identify one or more n-grams;

determining a score for each n-gram that the n-gram corresponds to an edge or a second node;

identifying one or more edges having a score greater than an edge-threshold score, each of the identified edges corresponding to at least one of the n-grams;

identifying one or more second nodes having a score greater than a node-threshold score, each of the identified second nodes being connected to at least one of the identified edges, each of the identified second nodes corresponding to at least one of the n-grams; and

generating one or more structured queries that each comprise references to one or more of the identified edges and one or more of the identified second nodes.

2. The method of claim 1, wherein the score for each n-gram is a probability that the n-gram corresponds to an edge or a second node.

3. The method of claim 1, wherein the score that an n-gram corresponds to a second node is based on the degree of separation between the first-user node and the second node.

4. The method of claim 1, wherein the score that an n-gram corresponds to a second node is based on the identified edges connected to the second node.

5. The method of claim 1, wherein the score that an n-gram corresponds to a second node is based on the number of edges connected to the second node.

6. The method of claim 1, wherein the score that an n-gram corresponds to a second node is based on the search history associate with the first user.

7. The method of claim 1, wherein determining the score is based on a language model.

8. The method of claim 1, wherein each n-gram comprises one or more characters of text entered by the first user.

9. The method of claim 1, wherein each n-gram comprises a contiguous sequence of n items from the text query.

10. A system comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to;

access a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising;

a first-user node corresponding to a first user associated with an online social network; and

a plurality of second nodes that each correspond to a concept or a second user associated with the online social network;

receiving from the first user a substantially unstructured text query;

parsing the text query to identify one or more n-grams;

determine a score for each n-gram that the n-gram corresponds to an edge or a second node;

identify one or more edges having a score greater than an edge-threshold score, each of the identified edges corresponding to at least one of the n-grams;

identify one or more second nodes having a score greater than a node-threshold score, each of the identified second nodes being connected to at least one of the identified edges, each of the identified second nodes corresponding to at least one of the n-grams; and

generate one or more structured queries that each comprise references to one or more of the identified edges and one or more of the identified second nodes.

11. The system of claim 10, wherein the score for each n-gram is a probability that the n-gram corresponds to an edge or a second node.

12. The system of claim 10, wherein the score that an n-gram corresponds to a second node is based on the degree of separation between the first-user node and the second node.

13. The system of claim 10, wherein the score that an n-gram corresponds to a second node is based on the identified edges connected to the second node.

14. The system of claim 10, wherein the score that an n-gram corresponds to a second node is based on the number of edges connected to the second node.

15. The system of claim 10, wherein the score that an n-gram corresponds to a second node is based on the search history associate with the first user.

16. The system of claim 10, wherein determining the score is based on a language model.

17. The system of claim 10, wherein each n-gram comprises one or more characters of text entered by the first user.

18. The system of claim 10, wherein each n-gram comprises a contiguous sequence of n items from the text query.

19. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

access a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising;

a first-user node corresponding to a first user associated with an online social network; and

a plurality of second nodes that each correspond to a concept or a second user associated with the online social network;

receiving from the first user a substantially unstructured text query;

parsing the text query to identify one or more n-grams;

determine a score for each n-gram that the n-gram corresponds to an edge or a second node;

identify one or more edges having a score greater than an edge-threshold score, each of the identified edges corresponding to at least one of the n-grams;

identify one or more second nodes having a score greater than a node-threshold score, each of the identified second nodes being connected to at least one of the identified edges, each of the identified second nodes corresponding to at least one of the n-grams; and

generate one or more structured queries that each comprise references to one or more of the identified edges and one or more of the identified second nodes.