Structured search queries based on social-graph information

• US 8,732,208 B2
• Filed: 07/23/2012
• Issued: 05/20/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,060
• Publication Number:
  US 20130124538A1
• Time in Patent Office: 666 Days
• Field of Search: 707/722, 707/727, 707/728, 707/732, 707/769, 707/784, 707/798, 707/802
• US Class Current: 707/798
• CPC Class Codes: G06F 16/2423 Interactive query statement specification based on a database schema
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: H04L 63/105 Multiple levels of security

Abstract

In particular embodiments, a method includes receiving an unstructured text query, identifying nodes and edges from a social graph that correspond to n-grams in the text query, 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 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 an unstructured text query comprising one or more n-grams;

identifying one or more of the second nodes, each of the identified second nodes corresponding to one or more of the n-grams;

identifying one or more of the edges, each of the identified edges being connected to at least one of the identified second nodes, each of the identified edges corresponding to one or more of the n-grams; and

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

2. The method of claim 1, further comprising receiving from the first user a selection of one of the structured queries.

3. The method of claim 2, further comprising generating search results corresponding to the selection of one of the structured queries, the search results comprising references to one or more of the second nodes that are connected to at least one of the identified second nodes by at least one of the identified edges.

4. The method of claim 3, wherein each of the second nodes of the search results is within a threshold degree of separation from the first node.

5. The method of claim 2, further comprising generating search results corresponding to the selection of one of the structured queries, the search results comprising references to one or more of the identified second nodes.

6. The method of claim 1, further comprising ranking each of the structured queries based on the degree of separation between the first node and at least one of the identified second nodes referenced in the structured query.

7. The method of claim 1, further comprising ranking each of the structured queries based on a search history associated with the first user.

8. The method of claim 1, further comprising ranking each of the structured queries based on a social relevance of the identified second nodes or the identified edges referenced in the structured query.

9. The method of claim 1, further comprising ranking each of the structured queries based on a textual relevance of the structured query.

10. The method of claim 1, wherein each of the identified second nodes is within a threshold degree of separation from the first node.

11. The method of claim 10, wherein the threshold degree of separation is one, two, three, or all.

12. The method of claim 1, wherein identifying one or more of the second nodes comprises, for each n-gram:

determining a probability for each second node that the second node corresponds to the n-gram; and

identifying each second node with a probability greater than a threshold probability.

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

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

15. The method of claim 1, wherein, for each structured query, one or more of the references is highlighted to indicate the reference corresponds to an identified second node or an identified edge.

16. The method of claim 1, wherein receiving from the first user the unstructured text query comprises receiving one or more characters of a character string as the first user at a client system enters the character string into a graphical user interface.

17. The method of claim 16, wherein the graphical user interface comprises a query field, and wherein the character string is entered by the first user into the query field.

18. The method of claim 1, further comprising sending one or more of the structured queries for presentation to the first user.

19. The method of claim 18, further comprising presenting the one or more sent structured queries to the first user, wherein, for each sent structured query, one or more of the references of the sent structured query is highlighted as presented to indicate the reference corresponds to an identified second node or an identified edge.

20. The method of claim 1, wherein the unstructured text query is received from a client system associated with the first user.

21. The method of claim 1, wherein the unstructured text query is received from a third-party system via a first call through an application programming interface associated with the online social network.

22. The method of claim 21, further comprising sending one or more of the structure queries to the third-party system in response to the first call.

23. The method of claim 22, further comprising receiving a selection of one of the structured queries from the third-party system via a second call through the application programming interface.

24. The method of claim 23, further comprising sending search results corresponding to the selection of one of the structured queries to the third-party system in response to the second call.

25. The method of claim 1, further comprising sending, to a third-party system, search results corresponding to one of the structured queries in response to receiving from the third-party system a call through an application programming interface associated with the online social network.

26. The method of claim 1, wherein the unstructured text query is received from a third-party system via a communication channel associated with the online social network.

27. 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 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;

receive from the first user an unstructured text query comprising one or more n-grams;

identify one or more of the second nodes, each of the identified second nodes corresponding to one or more of the n-grams;

identify one or more of the edges, each of the identified edges being connected to at least one of the identified second nodes, each of the identified edges corresponding to one or more of the n-grams; and

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

28. 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 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;

receive from the first user an unstructured text query comprising one or more n-grams;

identify one or more of the second nodes, each of the identified second nodes corresponding to one or more of the n-grams;

identify one or more of the edges, each of the identified edges being connected to at least one of the identified second nodes, each of the identified edges corresponding to one or more of the n-grams; and

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