Keyboard-based corrections for search queries on online social networks

• US 10,635,661 B2
• Filed: 07/11/2016
• Issued: 04/28/2020
• Est. Priority Date: 07/11/2016
• Status: Expired due to Fees

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Husain, Aliasgar Mumtaz, Jeon, Sung-eok
• Primary Examiner(s): Morrison, Jay A
• Assistant Examiner(s): Hoang, Ken
• Application Number:
  US15/207,259
• Publication Number:
  US 20180011900A1
• Time in Patent Office: 1,387 Days
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

In one embodiment, a method includes receiving from a first user a text query inputted by the first user using an I/O device associated with the client system, the I/O device including a first keyboard layout. The method also includes identifying one or more physical-proximity phrases corresponding to the text query based at least in part on the first keyboard layout and calculating a confidence score for each of the identified physical-proximity phrases based at least in part on a search history of the first user. The method also includes identifying one or more objects, where each identified object matches at least one of the identified physical-proximity phrases having a confidence score greater than a threshold confidence score and sending to the first user one or more search results corresponding to one or more of the identified objects, respectively.

Claims

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

receiving, from a client system of a first user of an online social network, a completed text query submitted to the search engine by the first user using an I/O device associated with the client system, the I/O device comprising a first keyboard layout having a plurality of layers, wherein each of the plurality of layers comprises a particular set of characters, wherein the completed text query comprises N characters having N character positions in a first layer of the plurality of layers of the first keyboard layout;

identifying one or more physical-proximity phrases corresponding to the completed text query based at least in part on a second layer of the plurality of layers of the first keyboard layout, each identified physical-proximity phrase matching one or more n-grams included in a reference corpus, each matching n-gram comprising N characters having N character positions in the second layer of the first keyboard layout;

calculating a confidence score for each of the identified physical-proximity phrases based at least in part on a search history of the first user, wherein the confidence score for each physical-proximity phrase represents a likelihood that the first user intended to include the physical-proximity phrase in the completed text query;

determining one or more corrected text queries, each corrected text query comprising one or more of the physical-proximity phrases having a calculated confidence score greater than a threshold confidence score;

identifying, from a plurality of objects associated with the online social network, responsive to the completed text query, automatically without requiring the first user to select a corrected text query, one or more first objects matching the completed text query and one or more second objects matching at least one of the corrected text queries; and

sending, to the client system of the first user for display, a plurality of search results corresponding to one or more of the identified first objects and one or more of the identified second objects.

2. The method of claim 1, wherein the I/O device comprises a physical keyboard.

3. The method of claim 1, wherein the I/O device comprises a touch screen configured to display a soft keyboard.

4. The method of claim 1, further comprising:

receiving, from the client system of the first user, information about the first keyboard layout.

5. The method of claim 1, further comprising:

identifying, for each n^th character position of the text query, a set of physical-proximity characters comprising a first character that occupies the n^th character position of the text query and one or more characters adjacent to the first character on the first keyboard layout; and

generating a plurality of physical-proximity phrases based on the identified physical-proximity characters.

6. The method of claim 1, wherein, for each of one or more pairs of a first character in the first layer and a second character in the second layer, the first character is located on the first keyboard layout at a position corresponding to that of the second character.

7. The method of claim 5, wherein, for each of the generated physical-proximity phrases, at each n^th character position of character positions 1 through N, the character occupying the n^th character position of the physical-proximity phrase is a character selected from the set of physical-proximity characters corresponding to the n^th character position.

8. The method of claim 1, wherein the reference corpus comprises a lexical database.

9. The method of claim 1, wherein the reference corpus comprises text extracted from a plurality of content objects associated with the online social network.

10. The method of claim 1, wherein calculating the confidence score for each of the identified physical-proximity phrases is further based on a level of matching between the physical-proximity phrase and the reference corpus.

11. The method of claim 10, wherein the level of matching between the physical-proximity phrase and the reference corpus is based on a number of times that physical-proximity phrase appears in the reference corpus.

12. The method of claim 10, wherein the level of matching between the physical-proximity phrase and the reference corpus is based on a number of component n-grams of the physical-proximity phrase that appear in the reference corpus.

13. The method of claim 1, further comprising:

deriving, based on the search history of the first user, one or more patterns describing a typing behavior of the first user; and

calculating the confidence score for each of the identified physical-proximity phrases further based on one or more of the derived patterns.

14. The method of claim 1, wherein calculating the confidence score for each of the identified physical-proximity phrases comprises:

determining that a first physical-proximity phrase appears in a list of trending-topic keywords; and

increasing the confidence score for the first physical-proximity phrase based on the determination.

15. The method of claim 1, wherein calculating the confidence score for each of the identified physical-proximity phrases is further based on an edit distance between the physical-proximity phrase and the text query.

16. The method of claim 1, further comprising:

determining a number of search results to be displayed based at least in part on the calculated confidence scores of the identified physical proximity phrases.

17. The method of claim 1, further comprising:

dividing the search results into a first group and one or more second groups associated with the completed text query and the one or more corrected text queries, respectively; and

displaying the search results of the first group and the one or more second groups in a first search-results module and one or more second search-results modules, respectively, wherein the positions of the first search-results module and the one or more second search-results modules are based at least in part on the calculated confidence scores of the identified physical proximity phrases.

18. The method of claim 1, further comprising:

ranking each of the search results sent to the client system of the first user based at least in part on the calculated confidence scores of the identified physical-proximity phrases; and

displaying the search results based on the ranked search results.

21. The method of claim 1, wherein each character having a character position in the first layer corresponds to a different character having the same character position in the second layer.

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

receive, at a search engine system from a client system of a first user of an online social network, a completed text query submitted to the search engine system by the first user using an I/O device associated with the client system, the I/O device comprising a first keyboard layout having a plurality of layers, wherein each of the plurality of layers comprises a particular set of characters, wherein the completed text query comprises N characters having N character positions in a first layer of the plurality of layers of the first keyboard layout;

identify one or more physical-proximity phrases corresponding to the completed text query based at least in part on a second layer of the plurality of layers of the first keyboard layout, each identified physical-proximity phrase matching one or more n-grams included in a reference corpus, each matching n-gram comprising N characters having N character positions in the second layer of the first keyboard layout;

calculate a confidence score for each of the identified physical-proximity phrases based at least in part on a search history of the first user, wherein the confidence score for each physical-proximity phrase represents a likelihood that the first user intended to include the physical-proximity phrase in the completed text query;

determine one or more corrected text queries, each corrected text query comprising one or more physical-proximity phrases having a calculated confidence score greater than a threshold confidence score;

identify, from a plurality of objects associated with the online social network, responsive to the completed text query, automatically without requiring the first user to select a corrected text query, one or more first objects matching the completed text query and one or more second objects matching at least one of the corrected text queries; and

send, to the client system of the first user for display, a plurality of search results corresponding to one or more of the identified first objects and one or more of the identified second objects.

20. A search engine 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 first user of an online social network, a completed text query submitted to the search engine system by the first user using an I/O device associated with the client system, the I/O device comprising a first keyboard layout having a plurality of layers, wherein each of the plurality of layers comprises a particular set of characters, wherein the completed text query comprises N characters having N character positions in a first layer of the plurality of layers of the first keyboard layout;

identify one or more physical-proximity phrases corresponding to the completed text query based at least in part on a second layer of the plurality of layers of the first keyboard layout, each identified physical-proximity phrase matching one or more n-grams included in a reference corpus, each matching n-gram comprising N characters having N character positions in the second layer of the first keyboard layout;

calculate a confidence score for each of the identified physical-proximity phrases based at least in part on a search history of the first user, wherein the confidence score for each physical-proximity phrase represents a likelihood that the first user intended to include the physical-proximity phrase in the completed text query;

determine one or more corrected text queries, each corrected text query comprising one or more physical-proximity phrases having a calculated confidence score greater than a threshold confidence score;

identify, from a plurality of objects associated with the online social network, responsive to the completed text query, automatically without requiring the first user to select a corrected text query, one or more first objects matching the completed text query and one or more second objects matching at least one of the corrected text queries; and

send, to the client system of the first user for display, a plurality of search results corresponding to one or more of the identified first objects and one or more of the identified second objects.