Rewriting Search Queries on Online Social Networks

• US 20150039597A1
• Filed: 07/30/2013
• Published: 02/05/2015
• 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 9,514,230 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• 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 set of queries of an online social network received from one or more users of the online social network, parsing each query using a parsing algorithm to generate a query command based on each query, each query command comprising one or more query constraints for a specified number of objects of a specified object-type as specified by parsing-configuration parameters of the parsing algorithm, retrieving the specified number of objects that match at least a portion of the query constraint from one or more data stores associated with the online social network, scoring each retrieved object based on a scoring algorithm, and generating one or more revised parsing-configuration parameters based on a comparison of the scores of the retrieved objects and the specified number of objects of the query constraints.

Claims

1. A method comprising, by one or more computing devices:

accessing a first set of queries of an online social network received from one or more users of the online social network;

parsing each query in the first set of queries using a first parsing algorithm to generate a query command based on each query, each query command comprising one or more query constraints, each query constraint being for a specified number of objects of a specified object-type as specified by one or more parsing-configuration parameters of the first parsing algorithm;

retrieving, for each query constraint of each query command, the specified number of objects that match at least a portion of the query constraint from one or more data stores, each data store storing one or more objects associated with the online social network of the specified object-type for the query constraint;

scoring, for each query command, each retrieved object based on a first scoring algorithm; and

generating one or more revised parsing-configuration parameters based on a comparison of the scores of the retrieved objects and the specified number of objects of the query constraints.

2. The method of claim 1, further comprising:

revising the first parsing algorithm based on the parsing-configuration parameters, wherein one or more of the specified number of objects of a specified object-type is reduced based on the revised parsing-configuration parameters.

3. The method of claim 1, further comprising:

revising the first parsing algorithm based on the parsing-configuration parameters, wherein one or more of the query constraints is removed from the query commands generated by the first parsing algorithm based on the revised parsing-configuration parameters.

4. The method of claim 1, wherein the first parsing algorithm further specifies a number of data stores to access, the method further comprising:

revising the first parsing algorithm based on the parsing-configuration parameters, wherein one or more of the specified number of data stores to access is reduced based on the revised parsing-configuration parameters.

5. The method of claim 1, wherein scoring each retrieved object based on the first scoring algorithm comprises ranking all of the retrieved objects.

6. The method of claim 1, wherein generating the one or more revised parsing-configuration parameters comprises:

identifying each retrieved object having a score greater than or equal to a threshold score;

determining, for each query constraint of each query command, a number of objects that need to be retrieved from the data store to retrieve each identified object having a score greater than or equal to the threshold score; and

revising one or more of the parsing-configuration parameters based on the determined number of objects that need to be retrieved from the data store.

7. The method of claim 1, wherein the parsing-configuration parameters of the first parsing algorithm specify, for each particular type of query, instructions for generating a query commands based on the type of query 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.

8. The method of claim 1, wherein the first set of queries comprises a plurality of archived queries from a plurality of users of the online social network.

9. 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 each query in the first set of queries corresponds to a particular user node, and each retrieved object corresponds to a user node or concept node of the plurality of nodes.

10. The method of claim 9, wherein each query of the first set of queries 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.

11. The method of claim 9, wherein each query constraint is 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.

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

13. The method of claim 1, wherein retrieving the specified number of objects that match at least a portion of the query constraint from one or more data stores comprises, for each query constraint:

accessing one or more data stores storing objects of the specified object-type of the query constraint; and

identifying one or more objects from the accessed data stores that match at least a portion of the query constraint.

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

15. The method of claim 1, wherein each data store 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.

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

access a first set of queries of an online social network received from one or more users of the online social network;

parse each query in the first set of queries using a first parsing algorithm to generate a query command based on each query, each query command comprising one or more query constraints, each query constraint being for a specified number of objects of a specified object-type as specified by one or more parsing-configuration parameters of the first parsing algorithm;

retrieve, for each query constraint of each query command, the specified number of objects that match at least a portion of the query constraint from one or more data stores, each data store storing one or more objects associated with the online social network of the specified object-type for the query constraint;

score, for each query command, each retrieved object based on a first scoring algorithm; and

generate one or more revised parsing-configuration parameters based on a comparison of the scores of the retrieved objects and the specified number of objects of the query constraints.

17. 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 set of queries of an online social network received from one or more users of the online social network;

parse each query in the first set of queries using a first parsing algorithm to generate a query command based on each query, each query command comprising one or more query constraints, each query constraint being for a specified number of objects of a specified object-type as specified by one or more parsing-configuration parameters of the first parsing algorithm;

retrieve, for each query constraint of each query command, the specified number of objects that match at least a portion of the query constraint from one or more data stores, each data store storing one or more objects associated with the online social network of the specified object-type for the query constraint;

score, for each query command, each retrieved object based on a first scoring algorithm; and

generate one or more revised parsing-configuration parameters based on a comparison of the scores of the retrieved objects and the specified number of objects of the query constraints.