Ambiguous Structured Search Queries on Online Social Networks

• US 20130144899A1
• Filed: 12/31/2012
• Published: 06/06/2013
• Est. Priority Date: 04/19/2010
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Kari Lee Yofay, Lars Eilstrup Rasmussen
• Inventors: Lee, Yofay Kari, Peiris, Keith L., Maschmeyer, William R., Rasmussen, Lars Eilstrup, Duck, Joshua Keith
• Granted Patent: US 8,868,603 B2
• Time in Patent Office: Days
• US Class Current: 707/759
• 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:

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 an ambiguous n-gram;

identifying a plurality of second nodes or a plurality of edges corresponding to the ambiguous n-gram;

generating a first set of structured queries, each structured query from the first set of structured queries corresponding to an identified second node or identified edge, the structured query comprising a reference to the identified second node or identified edge;

receiving from the first user a selection of a first structured query from the first set of structured queries, the first structured query corresponding to a selected second node or selected edge from the identified second nodes or identified edges, respectively; and

generating a second set of structured queries, each structured query of the second set of structured queries comprising a reference to the selected second node or selected edge.

2. 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.

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

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

5. 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 second node or identified edge corresponding to the structured query.

6. The method of claim 1, further comprising transmitting the first set of structured queries to the first user, wherein each structured query of the first set of structured queries is selectable by the first user to indicate that the identified second node or identified edge referenced in the structured query matches an intent of the user for the ambiguous n-gram.

7. The method of claim 1, further comprising transmitting the first set of structured queries for presentation to the first user as the first user enters the unstructured text query into a graphical user interface, the presentation 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.

8. 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.

9. The method of claim 8, further comprising generating one or more search results corresponding to the second structured query.

10. The method of claim 9, wherein the second structured query further comprises reference to zero or more additional second nodes of the plurality of second nodes and zero or more additional edges of the plurality of edges, and wherein each search result corresponds to a second node of the plurality of second nodes that is connect to either the selected second node or one of the additional second nodes by one or more of either the selected edge or one of the additional edges.

11. The method of claim 1, wherein the unstructured text query is received as a portion of a third structured query, wherein the third structured query comprises:

references to one or more second nodes or second edges; and

the unstructured text query.

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

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

14. The method of claim 1, 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.

15. The method of claim 1, wherein identifying the plurality of second nodes or the plurality of edges corresponding to the ambiguous n-gram comprises:

determining a score for each n-gram that the n-gram corresponds to a second node of the plurality of second nodes or an edge of the plurality of edges; and

identifying each second nodes or each edge having a score greater than a threshold score, wherein at least two second nodes or two edges have a score greater than the threshold score.

16. The method of claim 15, wherein the score for each n-gram is a probability that the n-gram correspond to a second node of the plurality of second nodes or an edge of the plurality of edges.

17. The method of claim 15, wherein determining the score that an n-gram corresponds to a second node of the plurality of second nodes is based on the degree of separation between the first node and the second node.

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

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 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 an ambiguous n-gram;

identify a plurality of second nodes or a plurality of edges corresponding to the ambiguous n-gram;

generate a first set of structured queries, each structured query from the first set of structured queries corresponding to an identified second node or identified edge, the structured query comprising a reference to the identified second node or identified edge;

receive from the first user a selection of a first structured query from the first set of structured queries, the first structured query corresponding to a selected second node or selected edge from the identified second nodes or identified edges, respectively; and

generate a second set of structured queries, each structured query of the second set of structured queries comprising a reference to the selected second node or selected edge.

20. 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 an ambiguous n-gram;

identify a plurality of second nodes or a plurality of edges corresponding to the ambiguous n-gram;

generate a first set of structured queries, each structured query from the first set of structured queries corresponding to an identified second node or identified edge, the structured query comprising a reference to the identified second node or identified edge;

receive from the first user a selection of a first structured query from the first set of structured queries, the first structured query corresponding to a selected second node or selected edge from the identified second nodes or identified edges, respectively; and

generate a second set of structured queries, each structured query of the second set of structured queries comprising a reference to the selected second node or selected edge.