Using inverse operators for queries on online social networks

• US 9,367,536 B2
• Filed: 05/03/2013
• Issued: 06/14/2016
• Est. Priority Date: 05/03/2013
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Raina, Rajat, Hong, Kihyuk, Sankar, Sriram, Virochsiri, Kittipat, Curtiss, Michael, Mishra, Chaitanya
• Primary Examiner(s): MACKES, KRIS E
• Application Number:
  US13/887,068
• Publication Number:
  US 20140330809A1
• Time in Patent Office: 1,138 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24565 Triggers; Constraints
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: G06F 16/90332 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• 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 from a user a structured query comprising references to selected nodes and selected edges, parsing the structure query to identify a first query constraint and one or more second query constraints, identifying a inverse constraint associated with the first query constraint, and generating a query command based on the structured query, where the query command includes the inverse constraint and the one or more second query constraints.

Claims

1. A method 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 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 a structured query comprising references to one or more selected nodes from the plurality of nodes and one or more selected edges from the plurality of edges;

parsing the structured query to identify a first query constraint and one or more second query constraints;

identifying an inverse constraint associated with the first query constraint, wherein the first query constraint has been previously flagged as identifying greater than a threshold number of nodes; and

generating a query command based on the structured query, wherein the query command comprises the inverse constraint and the one or more second query constraints.

2. The method of claim 1, wherein the first query constraint is for a first object-type and the inverse constraint is for a second object-type.

3. The method of claim 2, wherein the first object-type and the second object-type are each selected from a group consisting of:

a user, a photo, a post, a webpage, an application, a location, or a user group.

4. The method of claim 1, wherein the first query constraint is for a first object-type and the inverse constraint is for the first object-type.

5. The method of claim 1, wherein the inverse constraint is for a first object-type and one or more of the second query constraints are for one or more second object-types.

6. The method of claim 1, wherein:

the first query constraint comprises an inner constraint and an outer constraint; and

the query command comprises an intersect of the inverse constraint and the inner constraint.

7. The method of claim 1, further:

the first query constraint is for a first object-type, the first query constraint corresponding to an inverted index mapping the first object-type to a second object-type; and

the inverse constraint is for the second object-type, the inverse constraint corresponding to a forward index mapping the second object-type to the first object-type.

8. The method of claim 1, wherein:

the first query constraint is for a first object-type corresponding to one or more nodes of a first node-type that are each connected by one of the selected edges referenced in the structured query to one or more nodes of a second node-type; and

the inverse constraint is for a second object-type corresponding to one or more nodes of the second node-type that are connected by the one of the selected edges referenced in the structured query to one or more nodes of the first node-type.

9. The method of claim 1, further comprising:

identifying a first set of nodes matching the inverse constraint;

identifying a second set of nodes matching the one or more second query constraints; and

generating one or more search results based on the first and second sets, wherein each search result corresponds to a node of the plurality of nodes.

10. The method of claim 9, wherein generating the one or more search results based on the first and second sets comprises generating a search result corresponding to each node identified in both of the first set of nodes and the second set of nodes.

11. The method of claim 9, wherein each search result corresponds to a node of the second set of nodes that is connected by one or more selected edges referenced in the structured query to one or more of the nodes of the first set of nodes.

12. The method of claim 9, wherein each search result corresponds to a node of the first set of nodes that is connected by one or more selected edges referenced in the structured query to one or more of the nodes of the second set of nodes.

13. The method of claim 9, wherein identifying the second set of nodes matching the one or more second query constraints comprises identifying one or more nodes of the plurality of nodes that is connected by one or more selected edges referenced in the structured query to one or more of the nodes in the first set of nodes.

14. The method of claim 1, further comprising:

determining a number of nodes satisfying the first query constraint; and

if the number of nodes is greater than a threshold number of nodes, then generating the query command with the inverse constraint;

else generating the query command with the first query constraint.

15. The method of claim 1, further comprising:

generating a preliminary query command based on the structured query, wherein the preliminary query command comprises the first query constraint and the one or more second query constraints;

generating a first set of search results based on the preliminary query command; and

if the first set of search results is less than a threshold number of search results, then generating the query command with the inverse constraint and generating a second set of search results based on the query command with the inverse constraint.

16. The method of claim 1, further comprising:

generating a first set of search results, wherein each search result corresponds to a node of the plurality of nodes, by;

identifying a first set of node matching the first query constraint; and

identifying a second set of nodes comprising one or more nodes from the first set of nodes that match one or more of the second query constraints; and

if the second set of nodes is less than a threshold number of nodes, then generating a second set of search results by;

identifying a third set of nodes matching the inverse constraint; and

identifying a fourth set of nodes comprising one or more nodes from the third set of nodes that match one or more of the second query constraints.

17. The method of claim 1, further comprising:

flagging one or more query constraints, wherein each flagged query constraint has been identified as identifying greater than a threshold number of nodes when executed;

determining whether the first query constraint is one of the flagged query constraints; and

generating a querying command comprising the inverse constraint if the first query constraint is a flagged query constraint.

18. The method of claim 1, further comprising generating one or more search results corresponding to the query command, wherein each search result corresponds to a node of the plurality of nodes.

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 a structured query comprising references to one or more selected nodes from the plurality of nodes and one or more selected edges from the plurality of edges;

parse the structured query to identify a first query constraint and one or more second query constraints;

identify an inverse constraint associated with the first query constraint, wherein the first query constraint has been previously flagged as identifying greater than a threshold number of nodes; and

generate a query command based on the structured query, wherein the query command comprises the inverse constraint and the one or more second query constraints.

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 a structured query comprising references to one or more selected nodes from the plurality of nodes and one or more selected edges from the plurality of edges;

parse the structured query to identify a first query constraint and one or more second query constraints;

identify an inverse constraint associated with the first query constraint, wherein the first query constraint has been previously flagged as identifying greater than a threshold number of nodes; and

generate a query command based on the structured query, wherein the query command comprises the inverse constraint and the one or more second query constraints.