Dynamic database reordering system

• US 7,610,194 B2
• Filed: 07/16/2003
• Issued: 10/27/2009
• Est. Priority Date: 07/18/2002
• Status: Active Grant

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Tegic Communications, Inc. (Microsoft Corporation)
• Inventors: Bradford, Ethan R., Kay, David Jon
• Primary Examiner(s): Hudspeth; David R
• Assistant Examiner(s): Spooner; Lamont M
• Application Number:
  US10/621,864
• Publication Number:
  US 20040083198A1
• Time in Patent Office: 2,295 Days
• Field of Search: 704/1, 704/9, 704/10, 715/534, 715/261, 715/256, 715/259, 711/136, 707 1- 6, 341/21, 341/22, 345/173, 382/181, 382/188, 379/368
• US Class Current: 704/10
• CPC Class Codes: G06F 3/0236 using selection techniques to select from displayed items
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A dynamic database reordering system provides a linguistics database that contains words that are ordered according to a linguistics model that dictates the order in which words are presented to a user. While a user enters keystrokes on a keypad of a communications device is pressing keys, the invention predicts the words, letters, numbers, or word stubs that the user is trying to enter. The invention reorders the linguistics model order based on the user'"'"'s usage of the system by tracking the user'"'"'s word selections. Once a word has been selected as a result of a next key selection (the nexted word), a frequency value is applied to the selected word and the word ordered first by the linguistics model in the linguistics database for that key sequence. The frequency value of the nexted word will become greater than the frequency value of the first displayed word upon repeated nexting to the same word. Subsequent user entries of the key sequence for the nexted word and the first ordered word will result in displaying the nexted word before the word ordered first by the linguistics model.

Claims

1. A computer-implemented process for reordering items in a database to be retrieved for display to a user, comprising the steps of:

storing a plurality of words in a linguistic database (LDB), said plurality of words ordered in said LDB according to a predefined linguistics frequency of use model;

accepting with a processor user input from a keyboard, said user input comprising at least one keypress;

retrieving any words from said LDB that matches at least one letter corresponding to said at least one keypress;

displaying a list of said retrieved words as ordered in said LDB;

accepting a user-defined word as input by said user;

storing said user-defined word in a user database (UDB);

assigning a frequency count to said user-defined word;

storing said frequency count for said user-defined word in said UDB;

enabling said user to select a word from said displayed list;

assigning a frequency count to every selected word in a non first order position in said displayed list and a frequency count to a first order word, if a non first order word is selected, said frequency count for said non first order selected word being different than said frequency count for said first order non selected word;

storing said frequency count of each word in association with each word in said UDB;

accepting a subsequent user input from a keyboard, said user input comprising at least one keypress;

retrieving any words from said LDB and any user-defined words from said UDB that match at least one letter corresponding to said at least one keypress;

if more than one word from any of said LDB and said UDB is retrieved and at least one retrieved word is associated with a frequency count, dynamically reordering for display said retrieved words as a function of said predefined linguistics frequency of use model and each frequency count associated with any of said retrieved words;

displaying a list of said reordered matching words if more than one word matches said user'"'"'s subsequent input; and

updating a frequency count associated with a word each time a non first order word is selected from a displayed list of matching words.

2. The process of claim 1, wherein if a non first ordered word is selected by said user a predetermined number of times then said non first ordered word is displayed in a first ordered position in said list of reordered matching words.

3. The process of claim 1, wherein all non first ordered words that are assigned said frequency count are initially assigned equal frequency counts.

4. The process of claim 1, wherein said word'"'"'s frequency count is increased each time said user selects said word.

5. The process of claim 1, wherein if said user selects said word from said list of retrieved words or said list of reordered words that is below a second ordered position, then said selected word is assigned said frequency count that places said word in said second ordered position in said list.

6. The process of claim 1, further comprising the step of:

periodically checking free space in said UDB and, if said free space is less than a predetermined amount, then removing from said UDB said words that have said frequency counts below a predetermined threshold.

7. The process of claim 6, wherein said removing step removes said user-defined words having said frequency counts below said predetermined threshold after removing other words having said frequency counts below said predetermined threshold.

8. The process of claim 1, further comprising the step of:

resolving frequency collisions when two words in said list of reordered words are associated with equal frequency counts by ordering said word that was most recently selected first.

9. The process of claim 1, further comprising the step of:

resolving frequency collisions when two words in said list of reordered words are associated with equal frequency counts by ordering said word having a higher initial ordering in said LDB first.

10. The process of claim 1, further comprising the step of:

resolving frequency collisions in said list of reordered words when a user-defined word and a word from said LDB have equal reordering frequency counts by ordering said user-defined word first.

11. The process of claim 1 wherein when said word from said LDB is selected for a first time, said step of assigning said frequency count generates said frequency count from said word'"'"'s position in said LDB as a function of said predefined linguistics frequency of use model.

12. The process of claim 11, wherein said user-defined words are initially assigned equal frequency counts during said assigning step.

13. A computer-implemented process for reordering items in a database to be retrieved for display to a user, comprising the steps of:

storing a plurality of words in a linguistic database (LDB), said plurality of words ordered in said LDB according to a predefined linguistics frequency of use model;

accepting with a processor user input from a keyboard, said user input comprising at least one keypress;

retrieving any words from said LDB that match at least one letter corresponding to said at least one keypress;

displaying a list of said retrieved words as ordered in said LDB;

accepting a user-defined word as input by said user;

storing said user-defined word in a user database (UDB);

assigning a frequency count to said user-defined word;

storing said frequency count for said user-defined word in said UDB;

enabling said user to select a word from said displayed list;

assigning a frequency count to every selected word in a non first order position in said displayed list and a frequency count to a first order word, if a non first order word is selected, said frequency count for said non first order selected word being different than said frequency count, said frequency count for said first order non selected word;

storing said frequency count of each word in association with each word in said UDB;

storing a frequency count for a first order word from said displayed list if a non first order word is selected from said displayed list, said frequency count for said non selected first order word being lower than said frequency count for said selected non first order word, said frequency count being stored in association with said first order non selected word in said UDB

accepting a subsequent user input from a keyboard, said user input comprising at least one keypress;

retrieving any words from said LDB and any user-defined words from said UDB that match at least one letter corresponding to said at least one keypress;

if more than one word from any of said LDB and said UDB is retrieved and at least one retrieved word is associated with a frequency count, dynamically reordering for display said retrieved words as a function of said predefined linguistics frequency of use model and each frequency count associated with any of said retrieved words;

displaying a list of said reordered matching words if more than one word matches said user'"'"'s subsequent input;

updating a frequency count associated with a word each time a non first order word is selected from a displayed list of matching words; and

periodically aging said frequency counts in said reorder database by reducing said frequency counts by a predetermined factor.

14. A computer-implemented process for reordering items in a database to be retrieved for display to a user, comprising the steps of:

storing a plurality of words in a linguistic database (LDB), said plurality of words ordered in said LDB according to a predefined linguistics frequency of use model;

accepting with a processor user input from a keyboard, said user input comprising at least one keypress;

retrieving any words from said LDB that matches at least one letter corresponding to said at least one keypress;

displaying a list of said retrieved words as ordered in said LDB;

accepting a user-defined word as input by said user;

storing said user-defined word in a user database (UDB);

assigning a frequency count to said user-defined word;

storing said frequency count for said user-defined word in said UDB;

enabling said user to select a word from said displayed list;

assigning a frequency count to every selected word in a non first order position in said displayed list and a frequency count to a first order word, if a non first order word is selected, said frequency count for said non first order selected word being different than said frequency count for said first order non selected word;

storing said frequency count of each word and in association with each word in said UDB;

accepting a subsequent user input from a keyboard, said user input comprising at least one keypress;

retrieving any words from said LDB and any user-defined words from said UDB that match at least one letter corresponding to said at least one keypress;

if more than one word from any of said LDB and said UDB is retrieved and at least one retrieved word is associated with a frequency count, dynamically reordering for display said retrieved as a function of said predefined linguistics frequency of use model and each frequency count associated with any of said retrieved words;

displaying a list of said reordered matching words if more than one word matches said user'"'"'s subsequent input;

updating a frequency count associated with a word each time a non first order word is selected from a displayed list of matching words; and

wherein words selected by said user that do not have a possibility of a collision with other words are not assigned a frequency count.

15. An apparatus for reordering items in a database to be retrieved for display to a user, comprising:

a module for accepting user input from a keyboard, said user input comprising at least one keypress;

a linguistic database (LDB) containing a plurality of words ordered according to a predefined linguistic frequency of use model;

a module for displaying to said user a list of any words in said LDB and any user-defined words in a user database (UDB) that match at least one letter corresponding to said at least one keypress, said words retrieved from any of said LDB and from said UDB;

said UDB for storing any user-defined words entered by said user, a frequency count associated with each user-defined word, and a frequency count associated with each word stored in said LOB that was assigned a frequency count by an assigning module;

a module for retrieving from any of said LOB and from said UDB a list of any words that match at least one letter corresponding to said at least one keypress of said user'"'"'s input, said words dynamically reordered for display of said retrieved words as a function of said predefined linguistics frequency of use model and each frequency count associated with any of said retrieved words; and

said assigning module for assigning a frequency count to every selected word in a non first order position in a list of said retrieved words and assigning a frequency count to a first order word if a word in a non first order position is selected, said frequency count being different for said first order word than said frequency count for said selected non first order word, said assigning module updating a frequency count each time a non first order word is selected from said retrieved list.

16. The apparatus of claim 15, wherein said frequency count is assigned to said selected word if said selected word is in a non first order position in said list and is selected for a first time.

17. The apparatus of claim 16, wherein if said non first ordered word is selected by said user a predetermined number of times then said non first ordered word is displayed in a first ordered position in said list.

18. The apparatus of claim 16, wherein all non first ordered words that are assigned said frequency count are initially assigned equal frequency counts.

19. The apparatus of claim 15, wherein said word'"'"'s frequency count is increased each time said user selects said word.

20. The apparatus of claim 15, wherein if said user selects from said list a word that is below a second ordered position then said assigning module assigns a frequency count that places said word in said second ordered position in said list.

21. The apparatus of claim 15, further comprising:

a module for periodically checking for free space in said UDB and, if said free space is less than a predetermined amount, then removing from said UDB said frequency counts and corresponding object numbers or corresponding user-defined words for words that have frequency counts below a predetermined threshold.

22. The apparatus of claim 21, wherein said removing module removes user-defined words having frequency counts below said predetermined threshold after removing other words having frequency counts below said predetermined threshold.

23. The apparatus of claim 15, further comprising:

a module for resolving frequency collisions when two words in said list have equal frequency counts by ordering said most recently selected word first.

24. The apparatus of claim 15, further comprising:

a module for resolving frequency collisions when two words in said list have equal frequency counts by ordering said word having a higher initial ordering in said LDB first.

25. The apparatus of claim 15, further comprising:

a module for resolving frequency collisions in said list when said user-defined word and said word from said LDB have equal frequency counts by ordering said user-defined word first.

26. The apparatus of claim 15 wherein said assigning module assigns said frequency count for said word from said LDB based on said predefined linguistics frequency of use model.

27. The apparatus of claim 26, wherein said user-defined words are initially assigned equal frequency counts by said assigning module.

28. An apparatus for reordering items in a database to be retrieved for display to a user, comprising:

a module for accepting user input from a keyboard, said user input comprising at least one keypress;

a linguistic database (LDB) containing a plurality of words ordered according to a predefined linguistic frequency of use model;

a module for displaying to said user a list of any words in said LDB and any user-defined words in a user database (UDB) that match at least one letter corresponding to said at least one keypress, said words retrieved from any of said LDB and from said UDB;

said UDB for storing any user-defined words entered by said user, a frequency count associated with each user-defined word, and a frequency count associated with each word stored in said LDB that was assigned a frequency count by an assigning module;

a module for retrieving from any of said LDB and from said UDB a list of any words that match at least one letter corresponding to said at least one keypress of said user'"'"'s input, said words dynamically reordered for display of said retrieved words as a function of said predefined linguistics frequency of use model and each frequency count associated with any of said retrieved words;

said assigning module for assigning said a frequency count to every selected word in a non first order position in a list of said retrieved words and assigning a frequency count to a first order word if a word in a non first order position is selected, said frequency count being different for said first order word than said frequency count for said selected non first order word, said assigning module updating a frequency count each time a non first order word is selected from said retrieved list; and

a module for periodically aging said frequency counts in said reorder database by reducing said frequency counts by a predetermined factor.

29. An apparatus for reordering items in a database to be retrieved for display to a user, comprising:

a module for accepting user input from a keyboard, said user input comprising at least one keypress;

a linguistic database (LDB) containing a plurality of words ordered according to a predefined linguistic frequency of use model;

a module for displaying to said user a list of any words in said LDB and any user-defined words in a user database (UDB) that match at least one letter corresponding to said at least one keypress, said words retrieved from any of said LDB and from said UDB;

said UDB for storing any user-defined words entered by said user, a frequency count associated with each user-defined word, and a frequency count associated with each word stored in said LDB that was assigned a frequency count by an assigning module;

a module for retrieving from any of said LDB and from said UDB a list of any words that match at least one letter corresponding to said at least one keypress of said user'"'"'s input, said words dynamically reordered for display of said retrieved words as a function of said predefined linguistics frequency of use model and each frequency count associated with any of said retrieved words; and

said assigning module for assigning a frequency count to every selected word in a non first order position in a list of said retrieved words and assigning a frequency count to a first order word if a word in a non first order position is selected, said frequency count being different for said first order word than said frequency count for said selected non first order word, said assigning module updating a frequency count each time a non first order word is selected from said retrieved list;

wherein said words selected by said user that do not have a possibility of a collision with other words are not assigned said frequency count.