Social-Based Spelling Correction for Online Social Networks

• US 20160154861A1
• Filed: 12/01/2014
• Published: 06/02/2016
• Est. Priority Date: 12/01/2014
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Hegerty, Ian Douglas, Bernhardt, Daniel, Liang, Feng, Podsiadlo, Agnieszka Anna
• Granted Patent: US 9,679,024 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/248 Presentation of query results
• 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/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

In one embodiment, a method includes receiving a search query, determining if a bloom filter indicates an n-gram of the query does not exist in a set of object names associated with a vertical, identifying variant-tokens for each n-gram that does not exist in the set of object names, generating unique combinations of the n-grams and variant-tokens, where each unique combination includes a variant-token corresponding to each n-gram that does not exist in the set of object names for the n-gram, calculating a confidence score for each unique combination based at least in part on the search query and whether the unique combination exists in the set of object names, identifying objects matching each unique combination, where the unique combination has a confidence score greater than a threshold confidence score, and sending a search-results page responsive to the search query to the client device of the user.

Claims

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

receiving, from a client device of a user of an online social network, a search query comprising one or more n-grams;

determining, for each n-gram, if a first bloom filter indicates the n-gram does not exist in a first set of object names associated with a first vertical;

identifying, for each n-gram that does not exist in the first set of object names, one or more variant-tokens based at least on the first bloom filter and the first set of object names;

generating one or more unique combinations of the n-grams and variant-tokens, wherein each unique combination comprises a variant-token corresponding to each n-gram that does not exist in the first set of object names for the n-gram;

calculating a confidence score for each unique combination based at least in part on the search query and whether the unique combination exists in the first set of object names;

identifying objects matching each unique combination having a confidence score greater than a threshold confidence score; and

sending, to the client device of the user, a search-results page responsive to the search query, the search-results page comprising one or more references to one or more of the identified objects, respectively.

2. The method of claim 1, wherein indicating the n-gram does not exist in the first set of object names associated with the first vertical comprises indicating the n-gram is misspelled.

3. The method of claim 1, wherein generating one or more unique combinations of the n-grams and variant-tokens comprises:

calculating a token score for each identified variant-token based at least a language model and an error-correction model, wherein the language model and the error-correction model are associated with the first set of object names and the first vertical, and wherein the token score indicates if the identified variant-token exists in the language model associated with the first set of object names and the first vertical; and

generating one or more unique combinations of the n-grams and the variant-tokens, each variant-token used in a unique combination having a token score greater than a threshold token score.

4. The method of claim 1, wherein the first bloom filter comprises a plurality of second bloom filters, each of the second bloom filters being associated with a sub-set of object names of the first set of object names.

5. The method of claim 4, wherein determining if the first bloom filter indicates that the n-gram does not exist in the first set of object names associated with the first vertical comprises determining, for each n-gram, if one of the second bloom filters of the plurality of second bloom filters indicates that the n-gram does not exist in a sub-set of object names associated with the second bloom filter.

6. The method of claim 4, wherein generating one or more unique combinations of the n-grams and variant-tokens comprises:

calculating a combination score for each unique combination based on whether one or more second bloom filters of the plurality of second bloom filters indicate the unique combination does not exist in one or more sub-sets of object names of the first set of object names; and

selecting one or more of the unique combinations having combination scores greater than a threshold combination score.

7. The method of claim 6, wherein calculating the combination score for each unique combination is further based on one or more of:

an indication of a valid grammar construct for the unique combination;

an indication of whether the unique combination is associated with a database of previously identified lexicons associated with the first vertical;

or

a measure of interactions with the unique combination by one or more users of the online social network.

8. The method of claim 1, wherein generating one or more unique combinations of the n-grams and variant-tokens comprises:

classifying each unique combination to indicate whether the unique combination is suitable as a search query associated with the first vertical; and

selecting one or more of the classified unique combinations that are suitable as search queries associated with the first vertical.

9. The method of claim 1, wherein calculating the confidence score for each unique combination based on whether the unique combination exists in the first set of object names comprises determining if the first bloom filter indicates that the unique combination does not exist in the first set of object names.

10. The method of claim 1, wherein calculating the confidence score for each unique combination based on the search query comprises calculating the confidence score for the unique combination based at least on one or more of:

an error model, the error model indicating a likelihood of the unique combination being correctly spelled based at least on one or more pre-determined constraints associated with the search query;

a language model associated with the search query;

or

a lexicon associated with the first vertical of the search query.

11. The method of claim 1, wherein calculating the confidence score for each unique combination is further based on whether the unique combination is relevant to a delivery of advertisements to the user of the online social network.

12. The method of claim 1, wherein calculating the confidence score for each unique combination is further based on a social-graph affinity of one or more of the identified objects to the user of the online social network.

13. The method of claim 1, further comprising:

determining, in response to the received search query, the n-grams of the search query based at least on a pre-determined language model.

14. The method of claim 13, further comprising:

determining, for each n-gram, if a misspelled classifier indicates that the n-gram is not valid based at least on the pre-determined language model; and

selecting, for further determination by the first bloom filter, the n-gram that is not valid as indicated by the pre-determined language model.

15. The method of claim 1, further comprising:

determining, for each n-gram, if a misspelled classifier indicates that the n-gram does not exist in a database of object names associated with the first vertical and the online social network, the database having a finite number of object names; and

selecting, for further determination by the first bloom filter, the n-gram that does not exist in the database of object names as indicated by the misspelled classifier.

16. The method of claim 1, wherein determining if the first bloom filter indicates that the n-gram does not exist in the first set of object names associated with the first vertical comprises determining a likelihood that the n-gram does not exist in the first set of object names associated with the first vertical.

17. The method of claim 1, wherein identifying the variant-tokens is further based on a language model associated with the user of the online social network.

18. The method of claim 1, further comprising:

if the first bloom filter indicates that each and every n-gram of the search query does not exist in the first set of object names associated with the first vertical, then;

determining, for each n-gram, if a third bloom filter indicates the n-gram does not exist in a second set of object names associated with a second vertical;

identifying, for each n-gram that does not exist in the second set of object names, one or more variant-tokens based at least on the second bloom filter and the second set of object names;

generating one or more unique combinations of the n-grams and variant-tokens, wherein each unique combination comprises a variant-token corresponding to each n-gram that does not exist in the second set of object names for the n-gram;

calculating a confidence score for each unique combination based at least in part on the search query and whether the unique combination exists in the second set of object names;

identifying objects matching each unique combination having a score greater than a first threshold score; and

sending, to the client device of the user, a search-results page responsive to the search query, the search-results page comprising one or more references to one or more of the identified objects, respectively.

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

receive, from a client device of a user of an online social network, a search query comprising one or more n-grams;

determine, for each n-gram, if a first bloom filter indicates the n-gram does not exist in a first set of object names associated with a first vertical;

identify, for each n-gram that does not exist in the first set of object names, one or more variant-tokens based at least on the first bloom filter and the first set of object names;

generate one or more unique combinations of the n-grams and variant-tokens, wherein each unique combination comprises a variant-token corresponding to each n-gram that does not exist in the first set of object names for the n-gram;

calculate a confidence score for each unique combination based at least in part on the search query and whether the unique combination exists in the first set of object names;

identify objects matching each unique combination having a confidence score greater than a threshold confidence score; and

send, to the client device of the user, a search-results page responsive to the search query, the search-results page comprising one or more references to one or more of the identified objects, respectively.

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 device of a user of an online social network, a search query comprising one or more n-grams;

determine, for each n-gram, if a first bloom filter indicates the n-gram does not exist in a first set of object names associated with a first vertical;

identify, for each n-gram that does not exist in the first set of object names, one or more variant-tokens based at least on the first bloom filter and the first set of object names;

generate one or more unique combinations of the n-grams and variant-tokens, wherein each unique combination comprises a variant-token corresponding to each n-gram that does not exist in the first set of object names for the n-gram;

calculate a confidence score for each unique combination based at least in part on the search query and whether the unique combination exists in the first set of object names;

identify objects matching each unique combination having a confidence score greater than a threshold confidence score; and

send, to the client device of the user, a search-results page responsive to the search query, the search-results page comprising one or more references to one or more of the identified objects, respectively.