Rewriting search queries on online social networks

• US 10,324,928 B2
• Filed: 10/28/2016
• Issued: 06/18/2019
• Est. Priority Date: 07/30/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, Stewart, Allan, Mashiach, Li-Tal
• Primary Examiner(s): Beausoliel, Jr., Robert W
• Assistant Examiner(s): Santos, Pedro J
• Application Number:
  US15/337,452
• Publication Number:
  US 20170046385A1
• Time in Patent Office: 963 Days
• Field of Search: 707723, 707748, 707769
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

In one embodiment, a method includes accessing a data set including a list of objects matching a query command and a score for each of the listed objects, where the query command is generated by parsing a query using a parsing algorithm, and where the score for each of the listed objects is calculated based on a scoring algorithm. The method also includes generating multiple subsets of the data set, each subset including one or more of the listed objects, and calculating, for each subset, a measure of score-quality associated with the scores of the objects in the subset and a measure of CPU-power associated with an amount of processing power required for retrieving the objects in the subset. The method also includes revising the parsing algorithm based on a comparison of the measures of score-quality and the measures of CPU-power associated with one or more of the subsets.

Claims

1. A method comprising, by one or more computing devices associated with a search engine:

accessing, by the one or more computing devices, a first data set comprising a list of objects matching a first query command and a score for each of the listed objects, the objects being structured documents accessible to the search engine, wherein the first query command is generated by parsing a first query using a first parsing algorithm of the search engine, and wherein the score for each of the listed objects is calculated based on a first scoring algorithm;

generating, by the one or more computing devices, a plurality of subsets of the first data set, each subset comprising a plurality of the listed objects;

calculating, by the one or more computing devices, for each of the subsets, a measure of score-quality for the subset, wherein the measure of score-quality is based on a count of objects in the subset that each has a score above a threshold;

accessing, by the one or more computing devices, for each of the subsets, a measure of CPU-power for the subset, wherein the measure of CPU-power is related to an amount of processing power required for retrieving the objects in the subset; and

revising, by the one or more computing devices, the first parsing algorithm of the search engine based on a comparison of (1) the measure of score-quality for each of the subsets and (2) the measure of CPU-power for each of the subsets, wherein the first parsing algorithm is revised to reduce an amount of processing power consumed by the search engine by reducing a number of objects retrieved for executing each of one or more future query commands generated using the first parsing algorithm.

2. The method of claim 1, wherein calculating, for each of the subsets, the measure of score-quality for the subset comprises:

identifying a first number of top scoring objects of the list of objects;

determining that a second number of the identified top scoring objects are included in the subset; and

calculating the measure of score-quality for the subset by comparing the second number with the first number.

3. The method of claim 1, wherein the measure of CPU-power for each of the subsets is based on a number of listed objects included in the subset.

4. The method of claim 1, wherein the first query command comprises one or more query constraints, each query constraint being for a specified number of objects of a specified object-type.

5. The method of claim 4, wherein the specified object-type is selected from a group consisting of:

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

6. The method of claim 1, wherein the first parsing algorithm comprises one or more parsing-configuration parameters, the parsing-configuration parameters specifying instructions for generating a query command comprising a specified number of query constraints for a specified number of objects of a specified object-type to be retrieved from a specified number of data stores.

7. The method of claim 6, wherein each of the data stores is selected from a group consisting of:

a users data store, a photos data store, a posts data store, a webpages data store, an applications data store, a locations data store, or a user-groups data store.

8. The method of claim 6, wherein revising the first parsing algorithm comprises:

generating one or more revised parsing-configuration parameters based on the comparison; and

revising the first parsing algorithm based on the revised parsing-configuration parameters.

9. The method of claim 6, wherein revising the first parsing algorithm comprises reducing, for one or more of the query constraints, the specified number of objects of the specified object-type of the respective query constraint.

10. The method of claim 6, wherein revising the first parsing algorithm comprises removing one or more of the query constraints from the query command generated by the first parsing algorithm.

11. The method of claim 6, wherein revising the first parsing algorithm comprises reducing, for one or more of the query constraints, the specified number of data stores of the respective query constraint.

12. The method of claim 1, wherein the score for each of the listed objects comprises a rank assigned to the object by the first scoring algorithm.

13. 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 plurality of user nodes corresponding to a plurality of users of the online social network, respectively; and

a plurality of concept nodes corresponding to a plurality of concepts associated with the online social network, respectively;

wherein the first query corresponds to a particular user node, and each of the listed objects corresponds to a user node or concept node of the plurality of nodes.

14. The method of claim 13, wherein the first query is 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.

15. The method of claim 14, wherein the first query command comprises one or more query constraints, each query constraint being for one or more nodes of the plurality of nodes connected to a first of the selected nodes by a first of the selected edges.

16. The method of claim 1, wherein the first query is an unstructured text query comprising one or more n-grams.

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

access a first data set comprising a list of objects matching a first query command and a score for each of the listed objects, the objects being structured documents accessible to a search engine, wherein the first query command is generated by parsing a first query using a first parsing algorithm of the search engine, and wherein the score for each of the listed objects is calculated based on a first scoring algorithm;

generate a plurality of subsets of the first data set, each subset comprising a plurality of the listed objects;

calculate, for each of the subsets, a measure of score-quality for the subset, wherein the measure of score-quality is based on a count of objects in the subset that each has a score above a threshold;

access, for each of the subsets, a measure of CPU-power for the subset, wherein the measure of CPU-power is related to an amount of processing power required for retrieving the objects in the subset; and

revise the first parsing algorithm of the search engine based on a comparison of (1) the measure of score-quality for each of the subsets and (2) the measure of CPU-power for each of the subsets, wherein the first parsing algorithm is revised to reduce an amount of processing power consumed by the search engine by reducing a number of objects retrieved for executing each of one or more future query commands generated using the first parsing algorithm.

18. 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 first data set comprising a list of objects matching a first query command and a score for each of the listed objects, the objects being structured documents accessible to a search engine, wherein the first query command is generated by parsing a first query using a first parsing algorithm of the search engine, and wherein the score for each of the listed objects is calculated based on a first scoring algorithm;

generate a plurality of subsets of the first data set, each subset comprising a plurality of the listed objects;

calculate, for each of the subsets, a measure of score-quality for the subset, wherein the measure of score-quality is based on a count of objects in the subset that each has a score above a threshold;

access, for each of the subsets, a measure of CPU-power for the subset, wherein the measure of CPU-power is related to an amount of processing power required for retrieving the objects in the subset; and

revise the first parsing algorithm of the search engine based on a comparison of (1) the measures of score-quality for each of the subsets and (2) the measures of CPU-power for each of the subsets, wherein the first parsing algorithm is revised to reduce an amount of processing power consumed by the search engine by reducing a number of objects retrieved for executing each of one or more future query commands generated using the first parsing algorithm.

19. The system of claim 18, wherein the instructions to calculate, for each of the subsets, the measure of score-quality for the subset comprise instructions to:

identify a first number of top scoring objects of the list of objects;

determine that a second number of the identified top scoring objects are included in the subset; and

calculate the measure of score-quality for the subset by comparing the second number with the first number.

20. The system of claim 18, wherein the measure of CPU-power for each of the subsets is based on a number of listed objects included in the subset.

21. The system of claim 18, wherein the first query command comprises one or more query constraints, each query constraint being for a specified number of objects of a specified object-type.

22. The system of claim 21, wherein the specified object-type is selected from a group consisting of:

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

23. The system of claim 18, wherein the first parsing algorithm comprises one or more parsing-configuration parameters, the parsing-configuration parameters specifying instructions for generating a query command comprising a specified number of query constraints for a specified number of objects of a specified object-type to be retrieved from a specified number of data stores.

24. The system of claim 23, wherein each of the data stores is selected from a group consisting of:

a users data store, a photos data store, a posts data store, a webpages data store, an applications data store, a locations data store, or a user-groups data store.

25. The system of claim 23, wherein the instructions to revise the first parsing algorithm comprise instructions to:

generate one or more revised parsing-configuration parameters based on the comparison; and

revise the first parsing algorithm based on the revised parsing-configuration parameters.

26. The system of claim 23, wherein the instructions to revise the first parsing algorithm comprise instructions to reduce, for one or more of the query constraints, the specified number of objects of the specified object-type of the respective query constraint.

27. The system of claim 23, wherein the instructions to revise the first parsing algorithm comprise instructions to remove one or more of the query constraints from the query command generated by the first parsing algorithm.

28. The system of claim 23, wherein the instructions to revise the first parsing algorithm comprise instructions to reduce, for one or more of the query constraints, the specified number of data stores of the respective query constraint.

29. The system of claim 18, wherein the score for each of the listed objects comprises a rank assigned to the object by the first scoring algorithm.

30. The system of claim 18, wherein the processors are further 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 plurality of user nodes corresponding to a plurality of users of the online social network, respectively; and

a plurality of concept nodes corresponding to a plurality of concepts associated with the online social network, respectively;

wherein the first query corresponds to a particular user node, and each of the listed objects corresponds to a user node or concept node of the plurality of nodes.

31. The system of claim 30, wherein the first query is 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.

32. The system of claim 31, wherein the first query command comprises one or more query constraints, each query constraint being for one or more nodes of the plurality of nodes connected to a first of the selected nodes by a first of the selected edges.

33. The system of claim 18, wherein the first query is an unstructured text query comprising one or more n-grams.