Online predictive memory

• US 6,078,918 A
• Filed: 04/02/1998
• Issued: 06/20/2000
• Est. Priority Date: 04/02/1998
• Status: Expired due to Term

• Current Assignee: Conversant, LLC (Publicis Groupe SA)
• Original Assignee: Trivada Corporation
• Inventors: Jensen, John B., Allen, Bradley P., Twomey, Cormac, Greif, Jeffrey M., Lo, Michael W., Adam, David L.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/054,178
• Time in Patent Office: 810 Days
• Field of Search: 707/1-206, 706/23-33, 187/391
• US Class Current: 1/1
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• 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

One embodiment of the present invention provides a system for making predictions about data records from an incoming stream of data records. This system operates by discovering predictive relationships in an online manner between fields in records in the incoming stream of data records as the incoming stream of data records is received. These predictive relationships can used to predict values in fields based on other field values in the same record. This facilitates cleansing of data by allowing transaction values to be validated based upon predictions made from other field values in the same transaction record. It also allows missing field values to be predicted based upon the other field values. A variation of this embodiment provides for filtering transaction records based upon discovered predictive relationships and routing the transaction records to other servers in real-time. Another embodiment forms association rules between fields in records in the incoming stream of records, and outputs these association rules for viewing by a human decision-maker. In another embodiment, the present invention comprises a server with an online predictive memory that can be incorporated into a heterogeneous network as a server. This embodiment is scalable and can be incorporated into an existing network with minimal integration effort. Note that the underlying model for this system continuously adapts to changes in the incoming stream of records over time without the need for any human intervention.

Claims

1. A method for making online predictions about data records from an incoming stream of data records, comprising:

receiving, at a computer system, the incoming stream of data records;

learning a predictive relationship between fields in the incoming stream of data records in an online manner as the incoming stream of data records is received;

examining at least one value from at least one input field of a first data record in the incoming stream of data records; and

creating a predicted value for an output field in the first data record using the at least one value and the predictive relationship.

2. The method of claim 1, further comprising discovering an association rule between fields in the incoming stream of data records in an online manner.

3. The method of claim 2, further comprising outputting the association rule for viewing by a human decision-maker.

4. The method of claim 2, wherein discovering the association rule includes discovering that a first value occurring in a first field is predictive of a second value occurring in a second field in a data record in the incoming stream of data records.

5. The method of claim 2, wherein discovering the association rule includes discovering that a first value occurring in a first field and a second value occurring in a second field is predictive of a third value occurring in a third field in data records in the incoming stream of data records.

6. The method of claim 2, wherein discovering the association rule includes sampling a subset of records in the incoming stream of data records in order to discover the association rule.

7. The method of claim 2, further comprising removing association rules having a history of making poor predictions.

8. The method of claim 2, further comprising removing infrequently used association rules.

9. The method of claim 1, wherein creating the predicted value for the output field includes summing at least one weight relating the predicted value to the at least one input field value from the at least one input field, and determining whether the sum exceeds a prediction threshold, and if so establishing the predicted value for the output field.

10. The method of claim 9, further comprising removing weights that fall below a threshold value.

11. The method of claim 1, wherein learning the predictive relationship includes using a predictive learning mechanism that is configured so that only a limited number of prediction errors is made before the predictive relationship is modified, the limited number of prediction errors being limited by a bound that is proportionate to a logarithm of a number of field-value combinations occurring in records in the incoming stream of data records.

12. The method of claim 1, wherein learning the predictive relationship includes using a predictive learning mechanism that multiplicatively updates a set of weights associated with the predictive relationship.

13. The method of claim 1, wherein learning the predictive relationship includes using a predictive learning mechanism that learns from mistaken predictions.

14. The method of claim 1, wherein learning the predictive relationship includes using a predictive learning mechanism that ignores true negative predictions.

15. The method of claim 1, wherein learning the predictive relationship includes sampling a subset of records in the incoming stream of data records in order to learn the predictive relationship.

16. The method of claim 1, further comprising refining the predictive relationship by training a predictive learning mechanism on a saved set of records from the incoming stream of data records.

17. The method of claim 1, wherein receiving the incoming stream of data records includes receiving the incoming stream of data records over a network from at least one process that is generating the data records.

18. The method of claim 1, wherein receiving the incoming stream of data records includes receiving the incoming stream of data records over a network from a plurality of processes that are generating the data records.

19. The method of claim 1, wherein receiving the incoming stream of data records includes receiving the incoming stream of data records from a client computer system.

20. The method of claim 1, wherein receiving the incoming stream of data records includes receiving the incoming stream of data records from an application server computer system.

21. The method of claim 1, wherein receiving the incoming stream of data records includes receiving the incoming stream of data records from a transactional database.

22. The method of claim 1, further comprising using the predicted value to supply a missing data value for the output field.

23. The method of claim 1, further comprising using the predicted value to validate a value in the output field.

24. The method of claim 1, further comprising using the predicted value to predict a trend in the incoming stream of data records.

25. A method for making online predictions about data records from an incoming stream of data records, comprising:

receiving, at a computer system, the incoming stream of data records;

discovering an association rule between fields in the incoming stream of data records in an online manner as the incoming stream of data records is received; and

outputting the association rule for viewing by a human decision-maker.

26. A method for making online predictions about data records from an incoming stream of data records, comprising:

receiving, at a computer system, the incoming stream of data records;

learning a predictive relationship in an online manner between fields in a record in the incoming stream of data records as the incoming stream of data records is received;

discovering an association rule between records in the incoming stream of data records in an online manner as the incoming stream of data records is received;

examining at least one value from at least one input field of a first data record in the incoming stream of data records; and

creating a predicted value for an output field in the first data record using the at least one value and the predictive relationship.

27. The method of claim 26, further comprising outputting the association rule for viewing by a human decision-maker.

28. A method for making online predictions about data records from an incoming stream of data records, comprising:

receiving, at a computer system, the incoming stream of data records;

learning a predictive relationship between fields in records in the incoming stream of data records in an online manner as the incoming stream of data records is received using a predictive learning mechanism, so that only a limited number of prediction errors is made before the predictive relationship is modified;

discovering an association rule between records in the incoming stream of data records in an online manner as the incoming stream of data records is received, wherein discovering the association rule includes discovering that a first value occurring in a first field is predictive of a second value occurring in a second field in data records in the incoming stream of data records;

removing association rules that make poor predictions;

removing infrequently used association rules;

examining at least one value from at least one input field of a first data record in the incoming stream of data records; and

creating a predicted value for an output field in the first data record using the at least one value and the predictive relationship.

29. The method of claim 28, wherein the limited number of prediction errors is limited by a bound that is proportionate to a logarithm of a number of field-value combinations occurring in records in the incoming stream of data records.

30. An apparatus for making predictions about data records from an incoming stream of data records, comprising:

an input, for receiving the incoming stream of data records;

a predictive learning mechanism coupled to the input, that is configured to learn a predictive relationship between fields in records in the incoming stream of data records in an online manner as the incoming stream of data records is received; and

a prediction mechanism that is configured to examine at least one value from at least one input field of a first data record in the incoming stream of data records and creates a predicted value for an output field in the first data record using the at least one value and the predictive relationship.

31. The apparatus of claim 30, further comprising a relationship discovering mechanism, for discovering an association rule between records in the incoming stream of data records in an online manner.

32. The apparatus of claim 31, further comprising a mechanism that outputs the association rule for viewing by a human decision-maker.

33. The apparatus of claim 31, wherein the relationship discovering mechanism includes a mechanism that discovers that a first value occurring in a first field is predictive of a second value occurring in a second field in data records in the incoming stream of data records.

34. The apparatus of claim 31, wherein the relationship discovering mechanism includes a mechanism that discovers that a first value occurring in a first field and a second value occurring in a second field is predictive of a third value occurring in a third field in data records in the incoming stream of data records.

35. The apparatus of claim 31, wherein the relationship discovering mechanism is configured to sample a subset of records in the incoming stream of data records in order to discover the association rule.

36. The apparatus of claim 31, wherein the relationship discovering mechanism is configured to remove association rules that make poor predictions.

37. The apparatus of claim 31, wherein the relationship discovering mechanism is configured to remove infrequently used association rules.

38. The apparatus of claim 30, wherein the predictive learning mechanism is configured to sum at least one weight relating the predicted value to the at least one input field value from the at least one input field, and to determine whether the sum exceeds a prediction threshold, and if so to establish the predicted value for the output field.

39. The apparatus of claim 30, wherein the predictive learning mechanism is configured so that only a limited number of prediction errors is made before the predictive relationship is modified, the limited number of prediction errors being limited by a bound that is proportionate to a logarithm of a number of field-value combinations occurring in records in the incoming stream of data records.

40. The apparatus of claim 30, wherein the predictive learning mechanism is configured to multiplicatively update a set of weights associated with the predictive relationship.

41. The apparatus of claim 30, wherein the predictive learning mechanism includes a predictive learning mechanism that learns from mistaken predictions.

42. The apparatus of claim 30, wherein the predictive learning mechanism is configured to ignore true negative predictions.

43. The apparatus of claim 30, wherein the predictive learning mechanism is configured to sample a subset of records in the incoming stream of data records in order to learn the predictive relationship.

44. The apparatus of claim 30, wherein the predictive learning mechanism operates on a saved set of records from the incoming stream of data records when no new records are being received at the input.

45. The apparatus of claim 30, wherein the input is configured to receive the incoming stream of data records from at least one process that is generating the data records.

46. The apparatus of claim 30, wherein the input is configured to receive the incoming stream of data records from a plurality of processes that are generating the data records.

47. The apparatus of claim 30, wherein the input is configured to receive the incoming stream of data records from a client computer system.

48. The apparatus of claim 30, wherein the input is configured to receive the incoming stream of data records from an application server computer system.

49. The apparatus of claim 30, wherein the input is configured to receive the incoming stream of data records from a transactional database.

50. The apparatus of claim 30, further comprising a mechanism that uses the predicted value to predict a missing data value for the output field.

51. The apparatus of claim 30, further comprising a mechanism that uses the predicted value to validate a value in the output field.

52. The apparatus of claim 30, further comprising a mechanism that uses the predicted value to predict a trend in the incoming stream of data records.

53. An apparatus for making predictions about data records from an incoming stream of data records, comprising:

an input, for receiving the incoming stream of data records;

a relationship discovering mechanism that discovers an association rule between records in the incoming stream of data records in an online manner;

a predictive learning mechanism coupled to the input, that learns a predictive relationship in an online manner between fields in records in the incoming stream of data records as the incoming stream of data records is received, wherein the predictive learning mechanism includes a predictive learning mechanism that learns from mistaken predictions; and

a prediction mechanism that examines at least one value from at least one input field of a first data record in the incoming stream of data records and creates a predicted value for an output field in the first data record using the at least one value and the predictive relationship.

54. An apparatus for making predictions about data records from an incoming stream of data records, comprising:

an input, for receiving the incoming stream of data records;

a relationship discovering mechanism that discovers an association rule between records in the incoming stream of data records in an online manner; and

a mechanism that outputs the association rule for viewing by a human decision-maker.

55. A data entry system that predicts a contents of a field in a first record based upon a contents of at least one other field in the first record, comprising:

a predictive learning mechanism that learns a predictive relationship in an online manner between fields in records in an incoming stream of records as the incoming stream of records is received;

a data input mechanism, that receives input into fields in the first record from a user; and

a prediction mechanism, coupled to the data input mechanism and the predictive learning mechanism, that examines at least one value from at least one input field of the first record and creates a predicted value for an output field in the first record based upon the at least one value and the predictive relationship.

56. The data entry system of claim 55, further comprising a server computer system containing the predictive learning mechanism, the data input mechanism and the prediction mechanism, wherein the data input mechanism receives input from the user through a client computer system that communicates with the server computer system through a network.

57. The data entry system of claim 55, wherein the incoming stream of records originates from the data input mechanism.

58. The data entry system of claim 55, wherein the incoming stream of records originates from a source other than the data input mechanism.

59. The data entry system of claim 55, wherein the data input mechanism receives in put from a plurality of users.

60. The data entry system of claim 55, further comprising a mechanism that uses the predicted value to establish a missing data value for the output field.

61. The data entry system of claim 55, further comprising a mechanism that uses the predicted value to validate a value in the output field.

62. The data entry system of claim 55, further comprising a mechanism that uses the predicted value to predict a trend in the incoming stream of data records.

63. The data entry system of claim 55, further comprising a database system coupled to the data entry system, for storing records entered through the data entry system.

64. The data entry system of claim 55, wherein the predictive learning mechanism is configured so that so that only a limited number of prediction errors is made before the predictive relationship is modified, the limited number of prediction errors being limited by a bound that is proportionate to a logarithm of a number of field-value combinations occurring in records in the incoming stream of data records.

65. The data entry system of claim 55, wherein the predictive learning mechanism includes a mechanism that multiplicatively updates a set of weights associated with the predictive relationship.

66. The data entry system of claim 55, wherein the predictive learning mechanism includes a predictive learning mechanism that learns from mistaken predictions.

67. The data entry system of claim 55, wherein the predictive learning mechanism is configured to ignore true negative predictions.

68. The data entry system of claim 55, wherein the predictive learning mechanism operates on a saved set of records from the incoming stream of data records when no new records are being received at the data input mechanism.

69. The data entry system of claim 55, wherein the data input mechanism is configured to receive the incoming stream of data records from a client computer system.

70. The data entry system of claim 55, wherein the data input mechanism is configured to receive the incoming stream of data records from an application server computer system.

71. The data entry system of claim 55, wherein the data input mechanism is configured to receive the incoming stream of data records from a transactional database.

72. An associative memory, comprising:

a predictive learning mechanism, for receiving an incoming stream of groups of values, each group of values in the incoming stream comprising a set of associated values including at least one input value and an output value, the predictive learning mechanism learning a predictive relationship in an online manner between the at least one input value and the output value as the incoming stream is received;

a first input, for receiving the at least one input value from a group of values; and

a prediction mechanism, coupled to the first input and the predictive learning mechanism, for receiving the at least one input value from the first input and creates a predicted value for the output based upon the at least one input value and the predictive relationship; and

a first output, coupled to the prediction mechanism, for outputting the predicted for the output.

73. The associative memory of claim 72, further comprising a relationship discovering mechanism, for discovering an association rule between records in the incoming stream of data records in an online manner.

74. The associative memory of claim 73, further comprising a mechanism, for outputting the association rule for viewing by a human decision-maker.

75. The associative memory of claim 72, further comprising:

a second input, for receiving the output value from the group of values; and

a comparison unit, for comparing the output value to the predicted for the output in order to determine whether the second value was predicted correctly.

76. A program storage device storing instructions that when executed by a computer system perform a method for making predictions about data records from an incoming stream of data records, comprising:

receiving, at a computer system, the incoming stream of data records;

learning a predictive relationship in an online manner between fields in records in the incoming stream of data records as the incoming stream of data records is received;

examining at least one value from at least one input field of a first data record in the incoming stream of data records; and

creating a predicted value for an output field in the first data record using the at least one value and the predictive relationship.

77. A computer system including an apparatus for making predictions about data records from an incoming stream of data records, comprising:

a processor;

a memory coupled to the processor;

an input coupled to the processor, that receives the incoming stream of data records;

a predictive learning mechanism coupled to the input, that learns a predictive relationship in an online manner between fields in records in the incoming stream of data records as the incoming stream of data records is received; and

a prediction mechanism coupled to the input, that examines at least one value from at least one input field of a first data record in the incoming stream of data records and creates a predicted value for an output field in the first data record using the at least one value and the predictive relationship.