Detecting social graph elements for structured search queries

• US 10,282,354 B2
• Filed: 09/07/2016
• Issued: 05/07/2019
• 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:
  US15/258,772
• Publication Number:
  US 20160378825A1
• Time in Patent Office: 972 Days
• 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, from a client device associated with a first user of an online social network, an unstructured text query, parsing the text query to identify one or more n-grams, determining a score for each n-gram, wherein the score for each n-gram is a probability that the n-gram corresponds to a particular data object of a plurality of data objects associated with the online social network, identifying one or more data objects based on the scores of their corresponding n-grams, each identified data object 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 data objects.

Claims

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

receiving, from a client device associated with a first user of an online social network, an unstructured text query;

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

determining a score for each n-gram, wherein the score for each n-gram is a probability that the n-gram corresponds to a particular unique data object of a plurality of unique data objects associated with the online social network;

identifying one or more unique data objects based on the scores of their corresponding n-grams, each identified data object 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 data objects, wherein each reference to one of the identified data objects in one of the structured queries comprises a name string corresponding to the respective identified data object.

2. The method of claim 1, further comprising:

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 the first user; and

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

3. The method of claim 2, wherein determining the score for each n-gram comprises:

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.

4. The method of claim 3, wherein identifying one or more unique data objects based on the scores of their corresponding n-grams comprises:

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.

5. The method of claim 4, wherein generating the one or more structured queries that each comprise references to one or more of the identified data objects comprises:

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.

6. The method of claim 1, wherein probability that the n-gram corresponds to a particular unique data object is based on the degree of separation between a first user and the data object within a social graph of the online social network.

7. The method of claim 1, wherein probability that the n-gram corresponds to a particular unique data object is based on one or more relationships associated with the data object.

8. The method of claim 1, wherein probability that the n-gram corresponds to a particular unique data object is based on a number of relationships associated with the data object.

9. The method of claim 1, wherein probability that the n-gram corresponds to a particular unique data object is based on a search history associated with the first user.

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

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

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

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

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

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

16. The method of claim 1, further comprising:

sending, to the client device responsive to receiving the unstructured text query, one or more of the structured queries for presentation to the first user, each structured query being a suggested query selectable by the first user.

17. The method of claim 16, 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.

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

19. 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 client device associated with a first user of an online social network, an unstructured text query;

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

determine a score for each n-gram, wherein the score for each n-gram is a probability that the n-gram corresponds to a particular unique data object of a plurality of unique data objects associated with the online social network;

identify one or more unique data objects based on the scores of their corresponding n-grams, each identified data object 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 data objects, wherein each reference to one of the identified data objects in one of the structured queries comprises a name string corresponding to the respective identified data object.

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

receive, from a client device associated with a first user of an online social network, an unstructured text query;

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

determine a score for each n-gram, wherein the score for each n-gram is a probability that the n-gram corresponds to a particular unique data object of a plurality of unique data objects associated with the online social network;

identify one or more unique data objects based on the scores of their corresponding n-grams, each identified data object 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 data objects, wherein each reference to one of the identified data objects in one of the structured queries comprises a name string corresponding to the respective identified data object.