Dynamic database reordering system

• US 20040083198A1
• Filed: 07/16/2003
• Published: 04/29/2004
• 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
• Granted Patent: US 7,610,194 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• 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 process for reordering items retrieved from a database for display to a user, comprising the steps of:

accepting user input from a keyboard;

providing a linguistic database;

wherein said linguistic database contains words ordered using a linguistic model;

dynamically retrieving words from said linguistic database that comprise letters formed by the user'"'"'s keyboard input;

displaying a list of said retrieved words to the user;

wherein words in said list are ordered using the linguistic database ordering and a dynamic reordering frequency count;

wherein the dynamic reordering frequency count overrides the linguistic database ordering for words in said list; and

assigning a dynamic reordering frequency count to words selected by the user from said list.

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

providing a reorder database; and

wherein said assigning step inserts selected words and their associated reordering frequencies into said reorder database.

3. The process of claim 2, further comprising the step of:

providing a user database;

wherein words that the user specifically enters into the system are stored in said user database; and

wherein said retrieving step also retrieves words that comprise letters formed by the user'"'"'s keyboard input from said user database.

4. The process of claim 2, wherein said assigning step inserts a first ordered word from said list and a non first ordered word into said reorder database if the user has selected the non first ordered word for the first time, and wherein the first ordered word is inserted if it does not already exist in said reorder database.

5. The process of claim 4, wherein the first ordered word in said list loses its position if the non first ordered word is selected by the user a predetermined number of times, and wherein the non first ordered word is then assigned a higher frequency value than the first ordered word.

6. The process of claim 4, wherein all non first ordered words entered into said reorder database are initially assigned equal reordering frequencies.

7. The process of claim 1, wherein a word'"'"'s reordering frequency is increased each time the user selects the word.

8. The process of claim 1, wherein if a word in said list is selected by the user and the word is below a second ordered position then said assigning step assigns the word'"'"'s reordering frequency to a value that places the word in the second ordered position in said list.

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

periodically performing an aging process to the reordering frequencies in said reorder database; and

wherein the reordering frequencies in said reordering database are reduced by a predetermined factor by said aging step.

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

periodically checking the free space of said reordering database;

wherein if the free space in said reordering database below a predetermined threshold, then removing words that have reordering frequencies below a predetermined threshold from said reordering database.

11. The process of claim 10, wherein said checking step removes user defined words having reordering frequencies below the predetermined threshold after other words having reordering frequencies below the predetermined threshold from said reordering database.

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

resolving reordering frequency collisions in said list;

wherein said resolving step resolves a collision if two words have the same reordering frequency by ordering the most recently selected of the two words first.

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

resolving reordering frequency collisions in said list;

wherein said resolving step resolves a collision if two words have the same reordering frequency by ordering the word having a higher ordering in said linguistic database first.

14. The process of claim 2, further comprising the step of:

resolving reordering frequency collisions in said list;

wherein said resolving step resolves a collision if two words have the same reordering frequency by ordering user defined words first if a user defined word and a word from said linguistic database have a collision.

15. The process of claim 1, wherein words selected by the user that do not have a possibility of a collision with other words are not assigned a reordering frequency count.

16. An apparatus for reordering items retrieved from a database for display to a user, comprising:

a module for accepting user input from a keyboard;

a linguistic database;

wherein said linguistic database contains words ordered using a linguistic model;

a module for dynamically retrieving words from said linguistic database that comprise letters formed by the user'"'"'s keyboard input;

a module for displaying a list of said retrieved words to the user;

wherein words in said list are ordered using the linguistic database ordering and a dynamic reordering frequency count;

wherein the dynamic reordering frequency count overrides the linguistic database ordering for words in said list; and

a module for assigning a dynamic reordering frequency count to words selected by the user from said list.

17. The apparatus of claim 16, further comprising:

a reorder database; and

wherein said assigning module inserts selected words and their associated reordering frequencies into said reorder database.

18. The apparatus of claim 17, further comprising:

a user database;

wherein words that the user specifically enters into the system are stored in said user database; and

wherein said retrieving module also retrieves words that comprise letters formed by the user'"'"'s keyboard input from said user database.

19. The apparatus of claim 17, wherein said assigning module inserts a first ordered word from said list and a non first ordered word into said reorder database if the user has selected the non first ordered word for the first time, and wherein the first ordered word is inserted if it does not already exist in said reorder database.

20. The apparatus of claim 19, wherein the first ordered word in said list loses its position if the non first ordered word is selected by the user a predetermined number of times, and wherein the non first ordered word is then assigned a higher frequency value than the first ordered word.

21. The apparatus of claim 19, wherein all non first ordered words entered into said reorder database are initially assigned equal reordering frequencies.

22. The apparatus of claim 16, wherein a word'"'"'s reordering frequency is increased each time the user selects the word.

23. The apparatus of claim 16, wherein if a word in said list is selected by the user and the word is below a second ordered position then said assigning module assigns the word'"'"'s reordering frequency to a value that places the word in the second ordered position in said list.

24. The apparatus of claim 17, further comprising:

a module for periodically performing an aging process to the reordering frequencies in said reorder database; and

wherein the reordering frequencies in said reordering database are reduced by a predetermined factor by said aging module.

25. The apparatus of claim 17, further comprising:

a module for periodically checking the free space of said reordering database;

wherein if the free space in said reordering database below a predetermined threshold, then removing words that have reordering frequencies below a predetermined threshold from said reordering database.

26. The apparatus of claim 25, wherein said checking module removes user defined words having reordering frequencies below the predetermined threshold after other words having reordering frequencies below the predetermined threshold from said reordering database.

27. The apparatus of claim 16, further comprising:

a module for resolving reordering frequency collisions in said list;

wherein said resolving module resolves a collision if two words have the same reordering frequency by ordering the most recently selected of the two words first.

28. The apparatus of claim 16, further comprising:

a module for resolving reordering frequency collisions in said list;

wherein said resolving module resolves a collision if two words have the same reordering frequency by ordering the word having a higher ordering in said linguistic database first.

29. The apparatus of claim 18, further comprising:

a module for resolving reordering frequency collisions in said list;

wherein said resolving module resolves a collision if two words have the same reordering frequency by ordering user defined words first if a user defined word and a word from said linguistic database have a collision.

30. The apparatus of claim 16, wherein words selected by the user that do not have a possibility of a collision with other words are not assigned a reordering frequency count.

31. A process for reordering items retrieved from a database for display to a user, comprising the steps of:

accepting user input from a keyboard;

providing a linguistic database;

wherein said linguistic database contains words ordered using a linguistic model and an ordering frequency for each word;

dynamically retrieving words from said linguistic database that comprise letters formed by the user'"'"'s keyboard input;

displaying a list of said retrieved words to the user;

wherein words in said list are ordered using the linguistic database ordering and a dynamic reordering frequency count;

wherein the dynamic reordering frequency count overrides the linguistic database ordering for words in said list; and

assigning a dynamic reordering frequency count to words selected by the user from said list and initializing the assigned dynamic reordering frequency count for a word to the ordering frequency value obtained from said linguistic database for the word.

32. The process of claim 31, further comprising the step of:

providing a reorder database; and

wherein said assigning step inserts selected words and their associated reordering frequencies into said reorder database.

33. The process of claim 32, further comprising the step of:

providing a user database;

wherein words that the user specifically enters into the system are stored in said user database; and

wherein said retrieving step also retrieves words that comprise letters formed b y the user'"'"'s keyboard input from said user database.

34. The process of claim 33, wherein all words specifically entered by the user are initially assigned equal reordering frequencies by said assigning step.

35. The process of claim 32, wherein said assigning step inserts a first ordered word from said list and a non first ordered word into said reorder database if the user has selected the non first ordered word for the first time, and wherein the first ordered word is inserted if it does not already exist in said reorder database.

36. The process of claim 35, wherein the first ordered word in said list loses its position if the non first ordered word is selected by the user a predetermined number of times, and wherein the non first ordered word is then assigned a higher frequency value than the first ordered word.

37. The process of claim 31, wherein a word'"'"'s reordering frequency is increased each time the user selects the word.

38. The process of claim 31, wherein if a word in said list is selected by the user and the word is below a second ordered position then said assigning step assigns the word'"'"'s reordering frequency to a value that places the word in the second ordered position in said list.

39. The process of claim 32, further comprising the step of:

periodically performing an aging process to the reordering frequencies in said reorder database; and

wherein the reordering frequencies in said reordering database are reduced by a predetermined factor by said aging step.

40. The process of claim 32, further comprising the step of:

periodically checking the free space of said reordering database;

wherein if the free space in said reordering database below a predetermined threshold, then removing words that have reordering frequencies below a predetermined threshold from said reordering database.

41. The process of claim 40, wherein said checking step removes user defined words having reordering frequencies below the predetermined threshold after other words having reordering frequencies below the predetermined threshold from said reordering database.

42. The process of claim 31, further comprising the step of:

resolving reordering frequency collisions in said list;

wherein said resolving step resolves a collision if two words have the same reordering frequency by ordering the most recently selected of the two words first.

43. The process of claim 31, further comprising the step of:

resolving reordering frequency collisions in said list;

wherein said resolving step resolves a collision if two words have the same reordering frequency by ordering the word having a higher ordering in said linguistic database first.

44. The process of claim 43, further comprising the step of:

resolving reordering frequency collisions in said list;

wherein said resolving step resolves a collision if two words have the same reordering frequency by ordering user defined words first if a user defined word and a word from said linguistic database have a collision.

58. The apparatus of claim 43, further comprising:

a module for resolving reordering frequency collisions in said list;

wherein said resolving module resolves a collision if two words have the same reordering frequency by ordering user defined words first if a user defined word and a word from said linguistic database have a collision.

45. An apparatus for reordering items retrieved from a database for display to a user, comprising:

a module for accepting user input from a keyboard;

a linguistic database;

wherein said linguistic database contains words ordered using a linguistic model and an ordering frequency for each word;

a module for dynamically retrieving words from said linguistic database that comprise letters formed by the user'"'"'s keyboard input;

a module for displaying a list of said retrieved words to the user;

wherein words in said list are ordered using the linguistic database ordering and a dynamic reordering frequency count;

wherein the dynamic reordering frequency count overrides the linguistic database ordering for words in said list; and

a module for assigning a dynamic reordering frequency count to words selected by the user from said list and initializing the assigned dynamic reordering frequency count for a word to the ordering frequency value obtained from said linguistic database for the word.

46. The apparatus of claim 45, further comprising:

a reorder database; and

wherein said assigning module inserts selected words and their associated reordering frequencies into said reorder database.

47. The apparatus of claim 46, further comprising:

a user database;

wherein words that the user specifically enters into the system are stored in said user database; and

wherein said retrieving module also retrieves words that comprise letters formed by the user'"'"'s keyboard input from said user database.

48. The apparatus of claim 47, wherein all words specifically entered by the user are initially assigned equal reordering frequencies by said assigning module.

49. The apparatus of claim 46, wherein said assigning module inserts a first ordered word from said list and a non first ordered word into said reorder database if the user has selected the non first ordered word for the first time, and wherein the first ordered word is inserted if it does not already exist in said reorder database.

50. The apparatus of claim 49, wherein the first ordered word in said list loses its position if the non first ordered word is selected by the user a predetermined number of times, and wherein the non first ordered word is then assigned a higher frequency value than the first ordered word.

51. The apparatus of claim 45, wherein a word'"'"'s reordering frequency is increased each time the user selects the word.

52. The apparatus of claim 45, wherein if a word in said list is selected by the user and the word is below a second ordered position then said assigning module assigns the word'"'"'s reordering frequency to a value that places the word in the second ordered position in said list.

53. The apparatus of claim 46, further comprising:

a module for periodically performing an aging process to the reordering frequencies in said reorder database; and

wherein the reordering frequencies in said reordering database are reduced by a predetermined factor by said aging module.

54. The apparatus of claim 46, further comprising:

a module for periodically checking the free space of said reordering database;

wherein if the free space in said reordering database below a predetermined threshold, then removing words that have reordering frequencies below a predetermined threshold from said reordering database.

55. The apparatus of claim 54, wherein said checking module removes user defined words having reordering frequencies below the predetermined threshold after other words having reordering frequencies below the predetermined threshold from said reordering database.

56. The apparatus of claim 45, further comprising:

a module for resolving reordering frequency collisions in said list;

wherein said resolving module resolves a collision if two words have the same reordering frequency by ordering the most recently selected of the two words first.

57. The apparatus of claim 45, further comprising:

a module for resolving reordering frequency collisions in said list;

wherein said resolving module resolves a collision if two words have the same reordering frequency by ordering the word having a higher ordering in said linguistic database first.