Syntactic models for parsing search queries on online social networks

• US 10,185,763 B2
• Filed: 11/30/2016
• Issued: 01/22/2019
• Est. Priority Date: 11/30/2016
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Wang, Haixun
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US15/365,797
• Publication Number:
  US 20180150552A1
• Time in Patent Office: 783 Days
• Field of Search: 707723
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

In one embodiment, a method includes receiving, from a client system of a user of an online social network, a query inputted by the user, wherein the query comprises multiple n-grams; determining one or more head-terms and one or more modifier-terms of the n-grams based on a syntactic model; identifying one or more objects matching at least a portion of the query; ranking each identified object based on a quality of matching of the object to the determined head-terms and modifier-terms; and sending, to the client system in response to the query, a search-results interface for display, wherein the search-results interface includes one or more search results corresponding to one or more of the identified objects, respectively, each identified object corresponding to a search result having a rank greater than a threshold rank.

Claims

1. A method comprising, by one or more computer systems:

receiving, from a client system of a user of an online social network, a query inputted by the user, wherein the query comprises a plurality of n-grams;

determining one or more head-terms and one or more modifier-terms of the plurality of n-grams based on a syntactic model;

identifying one or more objects matching at least a portion of the query;

ranking each identified object based on a quality of matching of the object to the determined head-terms and modifier-terms; and

sending, to the client system in response to the query, a search-results interface for display, wherein the search-results interface comprises one or more search results corresponding to one or more of the identified objects, respectively, each identified object corresponding to a search result having a rank greater than a threshold rank.

2. The method of claim 1, wherein the syntactic model comprises a function relating two input terms to an output representing an identification of which of the two input terms is a head-term, wherein the function is based on a data structure mapping head-terms to modifier-terms.

3. The method of claim 2, wherein the function is generated based on a frequency analysis of a corpus of phrases.

4. The method of claim 1, wherein the syntactic model comprises a function relating two input terms to an output representing a probability that a first term of the two input terms is a head-term, wherein the function is generated based on a machine learning model.

5. The method of claim 4, wherein the machine learning model generates the function based on an analysis of a data structure mapping head-terms to modifier-terms, respectively, the data structured being based on a frequency analysis of a corpus of well-formed sentences.

6. The method of claim 1, further comprising determining a parse tree of the query representing the grammatical structure of the one or more determined head-terms and the one or more determined modifier-terms.

7. The method of claim 6, wherein the quality of matching of the object to the determined head-terms and modifier-terms is further based on a relative position of each head-term and modifier-term in the parse tree with respect to terms associated with the object.

8. The method of claim 6, further comprising rewriting the query based on a relative position of each head-term and modifier-term in the parse tree, wherein identifying the one or more objects matching at least the portion of the query comprises identifying one or more objects matching the rewritten query.

9. The method of claim 6, wherein the parse tree is a syntactic dependency-based parse tree.

10. The method of claim 1, wherein each identified object comprises an object-type, and wherein ranking each identified object is further based on a quality of matching of one of the determined head-terms and the object-type of the identified object.

11. The method of claim 1, wherein each identified object comprises an item-type, and wherein ranking each identified object is further based on a quality of matching of one of the determined head-terms and the item-type of the identified object.

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

receive, from a client system of a user of an online social network, a query inputted by the user, wherein the query comprises a plurality of n-grams;

determine one or more head-terms and one or more modifier-terms of the plurality of n-grams based on a syntactic model;

identify one or more objects matching at least a portion of the query;

rank each identified object based on a quality of matching of the object to the determined head-terms and modifier-terms; and

send, to the client system in response to the query, a search-results interface for display, wherein the search-results interface comprises one or more search results corresponding to one or more of the identified objects, respectively, each identified object corresponding to a search result having a rank greater than a threshold rank.

13. The media of claim 12, wherein the syntactic model comprises a function relating two input terms to an output representing an identification of which of the two input terms is a head-term, wherein the function is based on a data structure mapping head-terms to modifier-terms.

14. The media of claim 13, wherein the function is generated based on a frequency analysis of a corpus of phrases.

15. The media of claim 12, wherein the syntactic model comprises a function relating two input terms to an output representing a probability that a first term of the two input terms is a head-term, wherein the function is generated based on a machine learning model.

16. The media of claim 15, wherein the machine learning model generates the function based on an analysis of a data structure mapping head-terms to modifier-terms, respectively, the data structured being based on a frequency analysis of a corpus of well-formed sentences.

17. The media of claim 12, wherein the software is further operable when executed to determine a parse tree of the query representing the grammatical structure of the one or more determined head-terms and the one or more determined modifier-terms.

18. The media of claim 17, wherein the quality of matching of the object to the determined head-terms and modifier-terms is further based on a relative position of each head-term and modifier-term in the parse tree with respect to terms associated with the object.

19. The media of claim 17, wherein the software is further operable when executed to rewrite the query based on a relative position of each head-term and modifier-term in the parse tree, wherein identifying the one or more objects matching at least the portion of the query comprises identifying one or more objects matching the rewritten query.

20. A system comprising:

one or more processors; and

a non-transitory 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 user of an online social network, a query inputted by the user, wherein the query comprises a plurality of n-grams;

determine one or more head-terms and one or more modifier-terms of the plurality of n-grams based on a syntactic model;

identify one or more objects matching at least a portion of the query;

rank each identified object based on a quality of matching of the object to the determined head-terms and modifier-terms; and

send, to the client system in response to the query, a search-results interface for display, wherein the search-results interface comprises one or more search results corresponding to one or more of the identified objects, respectively, each identified object corresponding to a search result having a rank greater than a threshold rank.