Using inverse operators for queries

• US 10,417,222 B2
• Filed: 06/19/2017
• Issued: 09/17/2019
• 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:
  US15/627,150
• Publication Number:
  US 20170286481A1
• Time in Patent Office: 820 Days
• 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 receiving a query comprising one or more n-grams, generating a plurality of query commands based on a parsing of the query input, wherein each query command comprises a plurality of query constraints, scoring the plurality of query commands based at least in part on a number of objects matching each of the query constraints of the respective query command, selecting a first query command based at least in part on the respective scores of the query commands, wherein the first query command comprises an inverse constraint corresponding to a first query constraint that has previously been flagged as identifying greater than a threshold number of objects and one or more second query constraints, and executing the first query command to identify a plurality of objects matching the inverse constraint and the one or more second query constraints.

Claims

1. A method comprising:

receiving, from a client system of a first user, a query comprising one or more n-grams;

generating a plurality of query commands based on a parsing of the query input, wherein each query command comprises a plurality of query constraints;

scoring the plurality of query commands based at least in part on a number of objects matching each of the query constraints of the respective query command;

selecting, from the plurality of query commands, a first query command based at least in part on the respective scores of the query commands, wherein the first query command comprises;

an inverse constraint corresponding to a first query constraint that has previously been flagged as identifying greater than a threshold number of objects; and

one or more second query constraints; and

executing the first query command to identify a plurality of objects matching the inverse constraint and the one or more second query constraints.

2. The method of claim 1, further comprising:

parsing the one or more n-grams of the query identify a plurality of query constraints, wherein each query constraint of each generated query command corresponds to one of the identified query constraints.

3. The method of claim 1, further comprising:

generating one or more search results based on the first query command, each search result corresponding to an object of the plurality of objects; and

sending, to the client system, one or more of the search results for display to the first user.

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;

or

the first query constraint is for the first object-type and the inverse constraint is for a second object-type.

5. The method of claim 1, wherein the inverse constraint is for a first object-type and the 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 first query command comprises the an intersect of the inverse constraint and the inner constraint.

7. The method of claim 1, wherein:

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 executing the first query command to identify the plurality of objects comprises:

identifying a first set of objects matching the inverse constraint;

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

wherein the plurality of objects is identified based on the first and second sets.

9. The method of claim 8, wherein the plurality of objects comprises each object identified in both of the first set of objects and the second set of objects.

10. The method of claim 8, wherein the plurality of objects comprises each object of the second set of objects that is connected to one or more of the objects of the first set of objects.

11. The method of claim 8, wherein the plurality of objects comprises each object of the first set of objects that is connected to one or more of the objects of the second set of objects.

12. The method of claim 8, wherein identifying the second set of objects matching the one or more second query constraints comprises identifying one or more objects that are connected to one or more of the objects in the first set of objects.

13. The method of claim 1, wherein generating the plurality of query commands comprises, for each query command:

determining a number of objects satisfying each query constraint of the query command; and

generating the query command with an inverse constraint for each query constraint where the number of objects is greater than a threshold number of objects.

14. The method of claim 1, further comprising, for each query command:

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

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

replacing each query constraint that has been flagged with a corresponding inverse constraint.

15. The method of claim 1, wherein the query is a structured query comprising references to one or more selected objects accessible by the computing device.

16. The method of claim 1, wherein the query is a text string.

17. 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 corresponding to the plurality of objects, respectively.

18. The method of claim 17, wherein each query command comprises references to one or more nodes from the plurality of nodes and one or more edges from the plurality of edges.

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

receive, from a client system of a first user, a query comprising one or more n-grams;

generate a plurality of query commands based on a parsing of the query input, wherein each query command comprises a plurality of query constraints;

score the plurality of query commands based at least in part on a number of objects matching each of the query constraints of the respective query command;

select, from the plurality of query commands, a first query command based at least in part on the respective scores of the query commands, wherein the first query command comprises;

an inverse constraint corresponding to a first query constraint that has previously been flagged as identifying greater than a threshold number of objects; and

one or more second query constraints; and

execute the first query command to identify a plurality of objects matching 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;

receive, from a client system of a first user, a query comprising one or more n-grams;

generate a plurality of query commands based on a parsing of the query input, wherein each query command comprises a plurality of query constraints;

score the plurality of query commands based at least in part on a number of objects matching each of the query constraints of the respective query command;

select, from the plurality of query commands, a first query command based at least in part on the respective scores of the query commands, wherein the first query command comprises;

an inverse constraint corresponding to a first query constraint that has previously been flagged as identifying greater than a threshold number of objects; and

one or more second query constraints; and

execute the first query command to identify a plurality of objects matching the inverse constraint and the one or more second query constraints.