Rewriting Search Queries on Online Social Networks

• US 20170046385A1
• Filed: 10/28/2016
• Published: 02/16/2017
• 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
• Granted Patent: US 10,324,928 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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:

accessing a first data set comprising a list of objects matching a first query command and a score for each of the listed objects, wherein the first query command is generated by parsing a first query using a first parsing algorithm, and wherein the score for each of the listed objects is calculated based on a first scoring algorithm;

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

calculating, for each of the subsets, 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; and

revising the first 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.

2. The method of claim 1, wherein calculating, for each of the subsets, the measure of score-quality 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 associated with each of the subsets is calculated 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 of the measures of score-quality and the measures of CPU-power associated with one or more of the subsets; 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, wherein the first query command is generated by parsing a first query using a first parsing algorithm, 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 one or more of the listed objects;

calculate, for each of the subsets, 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; and

revise the first 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.

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, wherein the first query command is generated by parsing a first query using a first parsing algorithm, 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 one or more of the listed objects;

calculate, for each of the subsets, 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; and

revise the first 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.