Detecting social graph elements for structured search queries

• US 9,465,848 B2
• Filed: 04/11/2014
• Issued: 10/11/2016
• 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, Boucher, Maxime, Azzolini, Alisson Gusatti, Li, Xiao, Cohen, Michael Benjamin, Rasmussen, Lars Eilstrup
• Primary Examiner(s): Casanova, Jorge A
• Application Number:
  US14/251,114
• Publication Number:
  US 20140222835A1
• Time in Patent Office: 914 Days
• US Class Current: 1/1
• 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:

receiving from a first user of an online social network an unstructured text query, the online social network being associated with a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes;

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 node, wherein the score for each n-gram is a probability that the n-gram corresponds to an edge or a node;

identifying one or more edges and one or more nodes based on their scores, each identified node and identified edge corresponding to at least one of the n-grams, each of the identified nodes being connected to at least one of the identified edges; 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 nodes.

2. The method of claim 1, further comprising:

accessing the social graph comprising the plurality of nodes and the 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 the first user associated with the 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.

3. The method of claim 1, wherein identifying one or more edges and one or more nodes based on their scores comprises:

identifying one or more edges having a score greater than an edge-threshold score; and

identifying one or more nodes having a score greater than a node-threshold score.

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

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

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

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

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

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

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

11. 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 comprising a query field, and wherein the character string is entered by the first user into the query field.

12. The method of claim 11, wherein the graphical user interface is displayed on a user interface of a native application associated with the online social network.

13. The method of claim 11, wherein the graphical user interface is displayed on a webpage associated with the online social network accessed by a browser client.

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

15. The method of claim 14, 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 node or an identified edge.

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

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

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

receive from a first user of an online social network an unstructured text query, the online social network being associated with a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes;

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

determine a score for each n-gram that then-gram corresponds to an edge or a node, wherein the score for each n-gram is a probability that the n-gram corresponds to an edge or a node;

identify one or more edges and one or more nodes based on their scores, each identified node and identified edge corresponding to at least one of the n-grams, each of the identified nodes being connected to at least one of the identified edges; 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 nodes.

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

receive from a first user of an online social network an unstructured text query, the online social network being associated with a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes;

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

determine a score for each n-gram that then-gram corresponds to an edge or a node, wherein the score for each n-gram is a probability that the n-gram corresponds to an edge or a node;

identify one or more edges and one or more nodes based on their scores, each identified node and identified edge corresponding to at least one of the n-grams, each of the identified nodes being connected to at least one of the identified edges; 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 nodes.