System and method for finding desired results by incremental search using an ambiguous keypad with the input containing orthographic and/or typographic errors

• US 8,370,284 B2
• Filed: 12/18/2009
• Issued: 02/05/2013
• Est. Priority Date: 11/23/2005
• Status: Active Grant

• Current Assignee: Veveo, Inc. (Adeia Inc.)
• Original Assignee: Veveo, Inc. (Adeia Inc.)
• Inventors: Garg, Pankaj, Venkataraman, Sashikumar, Rajpurohit, Gopal Mishrimalji
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Tran, Mai T
• Application Number:
  US12/642,173
• Publication Number:
  US 20100153380A1
• Time in Patent Office: 1,145 Days
• Field of Search: 706/46, 725/51, 725/53, 707/769
• US Class Current: 706/46
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 3/0236 using selection techniques to select from displayed items
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A system for finding and presenting content items in response to keystrokes entered by a user on an input device having a known layout of overloaded keys selected from a set of key layouts. The system includes a database containing content items and terms characterizing the content items; input logic for receiving keystrokes from the user and building a string corresponding to incremental entries by the user, each item in the string having the set of alphanumeric symbols associated with a corresponding keystroke; mapping logic to map the string to the database to find the most likely content items corresponding to the incremental entries, the mapping logic operating in accordance with a defined error model corresponding to the known layout of overloaded keys; and presentation logic for ordering the most likely content items identified by the mapping logic and for presenting the most likely content items.

Claims

1. A computer-implemented user-interface system for incrementally finding and presenting one or more items in response to keystrokes entered by a user on an input device having a known layout of overloaded keys selected from a set of overloaded key layouts, each overloaded key having a corresponding set of alphanumeric symbols, the system comprising:

a database stored in a computer memory, the database containing a catalog of items and corresponding descriptive terms that characterize the items, wherein the items include at least one of content items and data items; and

a computer memory comprising instructions for causing a computer system to;

determine which known layout of overloaded keys of the set of overloaded key layouts is present on the input device;

receive a sequence of incremental keystrokes from the user;

in response to each incremental keystroke of the sequence of incremental keystrokes, build a string corresponding to the sequence, each entry in the string having the set of alphanumeric symbols associated with a corresponding keystroke of the sequence of incremental keystrokes;

in response to each incremental keystroke of the sequence of incremental keystrokes, map the string to the database to find the most likely items corresponding to the sequence of incremental keystrokes, the mapping being in accordance with a defined error model, the error model providing for at least one suggested correction in the string wherein at least one keystroke of the sequence of incremental keystrokes is replaced by at least one alphanumeric symbol based on the known layout of overloaded keys of the input device and based on the alphanumeric symbols associated with said overloaded keys, and wherein the at least one alphanumeric symbol that replaces the at least one keystroke of the sequence of incremental keystrokes is an alphanumeric symbol from a set associated with a keystroke other than the keystroke being replaced; and

in response to each incremental keystroke of the sequence of incremental keystrokes, order and present the most likely items on a display device in accordance with defined ordering criteria such that the user-interface system receives ambiguous entries from the user and presents the most likely matching items in response to the entries.

2. The system of claim 1, wherein the error model associates the string with suggested corrections for typographic errors corresponding to incremental user entries, and wherein the suggested corrections are derived by replacing characters in the string resulting from one or more accidentally pressed adjacent keys.

3. The system of claim 1, wherein the error model associates the string with suggested corrections for orthographic errors corresponding to incremental user entries, and wherein the suggested corrections are derived by replacing one or more characters in the string resulting from phonetic substitutions.

4. The system of claim 1, wherein the content items include at least one of television shows and movies.

5. The system of claim 1, wherein the data items include at least one of address book records and to do list items.

6. A computer-implemented method of incrementally finding and presenting one or more items in response to keystrokes entered by a user on an input device having a known layout of overloaded keys selected from a set of overloaded key layouts, each overloaded key having a corresponding set of alphanumeric symbols, the method comprising:

providing access to a database stored in a computer memory, the database containing a catalog of items and corresponding descriptive terms that characterize the items, wherein the items include at least one of content items and data items;

determining which known layout of overloaded keys of the set of overloaded key layouts is present on the input device;

receiving a sequence of incremental keystrokes from the user;

in response to each incremental keystroke of the sequence of incremental keystrokes, building a string corresponding to the sequence, each entry in the string having the set of alphanumeric symbols associated with a corresponding keystroke of the sequence of incremental keystrokes;

in response to each incremental keystroke of the sequence of incremental keystrokes, mapping the string to the database to find the most likely items corresponding to the sequence of incremental keystrokes, the mapping being in accordance with a defined error model, the error model providing for at least one suggested correction in the string wherein at least one keystroke of the sequence of incremental keystrokes is replaced by at least one alphanumeric symbol based on the known layout of overloaded keys of the input device and based on the alphanumeric symbols associated with said overloaded keys, and wherein the at least one alphanumeric symbol that replaces the at least one keystroke of the sequence of incremental keystrokes is an alphanumeric symbol from a set associated with a keystroke other than the keystroke being replaced; and

in response to each incremental keystroke of the sequence of incremental keystrokes, ordering and presenting the most likely items on a display device in accordance with defined ordering criteria such that the user-interface system receives ambiguous entries from the user and presents the most likely matching items in response to the entries.

7. The method of claim 6, wherein the error model associates the string with suggested corrections for typographic errors corresponding to incremental user entries, and wherein the suggested corrections are derived by replacing characters in the string resulting from one or more accidentally pressed adjacent keys.

8. The method of claim 6, wherein the error model associates the string with suggested corrections for orthographic errors corresponding to incremental user entries, and wherein the suggested corrections are derived by replacing one or more characters in the string resulting from phonetic substitutions.

9. The method of claim 6, wherein the content items include at least one of television shows and movies.

10. The method of claim 6, wherein the data items include at least one of address book records and to do list items.