Ambiguous structured search queries on online social networks

• US 9,514,218 B2
• Filed: 09/18/2014
• Issued: 12/06/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, Peiris, Keith L., Maschmeyer, William R., Rasmussen, Lars Eilstrup, Duck, Joshua Keith
• Primary Examiner(s): Casanova, Jorge A
• Application Number:
  US14/489,917
• Publication Number:
  US 20150006566A1
• Time in Patent Office: 810 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2423 Interactive query statement specification based on a database schema
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 10/101 Collaborative creation, e.g. joint development of products or services
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

In one embodiment, a method includes accessing a social graph that includes a plurality of nodes and edges, receiving an unstructured text query comprising an ambiguous n-gram, identifying nodes and edges that correspond to the ambiguous n-gram, generating a first set of structured queries corresponding to the identified second nodes and edges, receiving from the first user a selection of a first structured query form the first set, and generating a second set of structured queries based on the selected first structured query.

Claims

1. A method comprising, by a computing device:

receiving, from a client device of a first user of an online social network, an unstructured text query comprising an ambiguous n-gram, the online social network being associated with a plurality of objects;

identifying one or more objects corresponding to the ambiguous n-gram based on a calculated probability that the n-gram correspond to the identified objects;

generating a first set of structured queries, each structured query from the first set of structured queries corresponding to an identified object, the structured query comprising a reference to the corresponding identified object;

receiving, from the client device of the first user, a selection of a structured query corresponding to a first object of the identified objects; and

generating a second set of structured queries, each structured query of the second set of structured queries comprising a reference to the first 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 an object of the plurality of objects associated with the online social network.

3. The method of claim 2, wherein each structured query further comprises a reference to one or more edges of the plurality of edges.

4. The method of claim 2, wherein one or more of the structured queries of the second set of structured queries further comprises references to one or more second nodes of the plurality of second nodes and one or more edges of the plurality of edges.

5. 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 the client device enters the character string into a graphical user interface.

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

7. The method of claim 5, wherein the graphical user interface comprises a user interface of a native application associated with the online social network on the client system of the first user.

8. The method of claim 5, wherein the graphical user interface comprises a webpage of the online social network accessed by a browser client of the client system of the first user.

9. The method of claim 1, wherein for each structured query from the first set of structured queries, the reference to the identified object is highlighted to indicate the reference corresponds to the ambiguous n-gram.

10. The method of claim 1, wherein for each structured query from the first set of structured queries, the structured query further comprises a snippet comprising contextual information about the identified object corresponding to the structured query.

11. The method of claim 1, further comprising sending the first set of structured queries to the client device of the first user for display, wherein each structured query of the first set of structured queries is selectable by the first user to indicate that the identified object referenced in the structured query matches an intent of the user for the ambiguous n-gram.

12. The method of claim 1, further comprising sending the first set of structured queries for display to the first user as the first user enters the unstructured text query into a graphical user interface, the display of the first set of structured queries to the first user enabling the first user to select the first structured query from the first set of structured queries.

13. The method of claim 1, further comprising receiving from the first user a selection of a second structured query from the second set of structured queries.

14. The method of claim 13, further comprising:

generating one or more search results corresponding to the second structured query; and

sending a search-results page to the client device of the first user for display, the search-results page comprising one or more of the search results.

15. The method of claim 1, wherein identifying one or more objects corresponding to the ambiguous n-gram comprises:

calculating a probability for each n-gram that the n-gram corresponds to an object of the plurality of objects; and

identifying each object having a score greater than a threshold probability, wherein at least two objects have a probability greater than the threshold probability.

16. The method of claim 15, wherein calculating the probability that the n-gram corresponds to an object of the plurality of objects is based on the degree of separation between the first user and the object within the online social network.

17. The method of claim 15, wherein calculating the probability for each n-gram is based on a search history associated with the first user.

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

receive, from a client device of a first user of an online social network, an unstructured text query comprising an ambiguous n-gram, the online social network being associated with a plurality of objects;

identify one or more objects corresponding to the ambiguous n-gram based on a calculated probability that the n-gram correspond to the identified objects;

generate a first set of structured queries, each structured query from the first set of structured queries corresponding to an identified object, the structured query comprising a reference to the corresponding identified object;

receive, from the client device of the first user, a selection of a structured query corresponding to a first object of the identified objects; and

generate a second set of structured queries, each structured query of the second set of structured queries comprising a reference to the first object.

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 of a first user of an online social network, an unstructured text query comprising an ambiguous n-gram, the online social network being associated with a plurality of objects;

identify one or more objects corresponding to the ambiguous n-gram based on a calculated probability that the n-gram correspond to the identified objects;

generate a first set of structured queries, each structured query from the first set of structured queries corresponding to an identified object, the structured query comprising a reference to the corresponding identified object;

receive, from the client device of the first user, a selection of a structured query corresponding to a first object of the identified objects; and

generate a second set of structured queries, each structured query of the second set of structured queries comprising a reference to the first object.