Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-12-08
2003-04-15
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06549919
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to techniques for processing information in a database system, and more particularly to techniques for updating customer signatures or other types of records in a database system.
BACKGROUND OF THE INVENTION
It is desirable in many business applications of database systems to track separately the transaction behavior of each customer. This tracking may be implemented using a customer-specific record referred to herein as a customer signature. For example, a customer signature for buying behavior may contain information on the likely place of purchase, value of goods purchased, type of goods purchased, and timing of purchases for the given customer. The signature may be updated whenever the customer makes a transaction, and, because of storage limitations, the updating may be able to use only the new transaction and the summarized information in the current customer signature.
The above-described customer signatures may be provided using relative frequency distributions. Such distributions are also commonly known as histograms. Updating histograms sequentially is not difficult when observations are randomly sampled. If {circumflex over (&pgr;)}
n
is a vector of current histogram probabilities and X
n+1
is a characteristic of a current transaction, represented as a vector of 0's except for a 1 in a cell containing an observed value, then the sequentially updated vector of histogram probabilities is
{circumflex over (&pgr;)}
n+1
=(1
−w
n+1
){circumflex over (&pgr;)}
n
+w
n+1
X
n+1
, (1)
where w
n+1
=1/(n+1) and {circumflex over (&pgr;)}
0
=0. Updating thus requires only the most recent transaction, the number of transactions made so far and the current summary. This is known as an unweighted average, because {circumflex over (&pgr;)}
n
weights each observed transaction X
1
, . . . , X
n
equally.
In cases of time-dependent customer behavior, a histogram updated using an unweighted average is generally inappropriate because recent transactions have no more influence on the histogram than old transactions do. Such time-dependent behavior is tracked better by an exponentially weighted moving average (EWMA). An updated EWMA vector {circumflex over (&pgr;)}
n+1
is given by equation (1) with w
n+1
=w for a fixed weight w, 0<w<1, that controls the extent to which {circumflex over (&pgr;)}
n+1
is affected by a new transaction and the speed with which a previous transaction is “aged out.” The initial probability estimate {circumflex over (&pgr;)}
0
must be specified, and can be determined, e.g., from historical data on other customers. Under some conditions, an EWMA approximates the corresponding posterior mean under a Bayesian dynamic model, as described in M. West et al., “Bayesian Forecasting and Dynamic Models,” Springer-Verlag, 1989. Additional details regarding EWMA can be found in B. Abraham et al., “Statistical Methods for Forecasting,” John Wiley & Sons, New York, N.Y., 1983.
It is important to note that the unweighted averages and EWMAs are generally appropriate only when variables are randomly sampled. However, timing variables like day-of-week are typically not randomly sampled. As a result, standard sequential estimates of their distributions can be badly biased. For example, if the transaction rate on Monday is high and the most recent transaction occurred early Monday morning, then the next transaction is likely to occur on Monday and unlikely to occur on Tuesday or any day of the week other than Monday. Because unweighted averages and EWMAs increase the estimated probability for a histogram cell every time that cell is observed, the estimated probability for Monday first rises with every transaction made on Monday and then falls with every transaction made before the following Monday.
As is apparent from the foregoing, a need exists for techniques for updating customer signatures or other records of time-dependent behavior in the presence of timing variables that are not randomly sampled.
SUMMARY OF THE INVENTION
The present invention provides improved techniques for updating customer signatures or other types of records in a database system.
In accordance with one aspect of the invention, a customer signature or other type of record in a database system is updated using an event-driven estimator based on a model of time-dependent behavior. A current version of a record affected by a given transaction is retrieved from a memory of the system and an event-driven estimator of at least one of a transaction rate and a period probability for the record is determined based at least in part on a dynamic Poisson timing model. The dynamic model has a number of periods and corresponding period-based transaction rates associated therewith. The event-driven estimator may be configured so as to generate an estimated transaction rate {circumflex over (&lgr;)}
j,n
for period j and a given transaction n, and then to generate an estimated period probability {circumflex over (&pgr;)}
j,n
for period j as {circumflex over (&lgr;)}
j,n
/&Sgr;
k
{circumflex over (&lgr;)}
k,n
. An updated version of the record may then be generated based on the event-driven estimator.
In accordance with another aspect of the invention, a number of different techniques may be used to update the event-driven estimator. As one example, the event-driven estimator may be updated for every transaction in a specified period and at the end of each oft he periods. As another example, the event-driven estimator may be updated for every transaction, regardless of which of the periods any particular transaction falls in, but not at the end of each of the periods. As yet another example, the event-driven estimator may be updated for a given one of the periods only when there is a transaction occurring within that period.
In accordance with a further aspect of the invention, the estimated transaction rate {circumflex over (&lgr;)}
j,n
provided by the event-driven estimator under the dynamic Poisson timing model satisfies
λ
^
j
,
n
-
1
=
{
(
1
-
w
)
λ
^
j
,
n
-
1
-
1
+
wZ
j
,
n
,
if
transaction
n
falls
in
period
j
λ
^
j
,
n
-
1
-
1
+
w
1
-
w
Z
j
,
n
,
if
transaction
n
does
not
fall
in
period
j
,
wherein w denotes a specified updating weight, Z
j,n
is an elapsed time in period j since a previous transaction n−1, and {circumflex over (&lgr;)}
j,n
−1
is a reciprocal rate that estimates the average time between transactions in period j.
Advantageously, the event-driven estimator of the present invention is both computationally efficient and memory efficient. It provides better sequential estimates of timing distributions used for customer signatures or other records than the conventional unweighted average and exponentially weighted moving average (EWMA) described previously, and yet is nearly as simple to compute as an EWMA.
REFERENCES:
patent: 5870752 (1999-02-01), Gibbons et al.
patent: 5907602 (1999-05-01), Peel et al.
patent: 5912905 (1999-06-01), Sakai et al.
patent: 6012064 (2000-01-01), Gibbons et al.
patent: 6381589 (2002-04-01), Leon
F. Chen et al., “Incremental Quantile Estimation For Massive Tracking,” Proceedings of KDD-2000, pp. 516-522, 2000.
M. West et al., “Introduction to the DLM: The First-Order Polynomial Model,” Bayesian Forecasting and Dynamic Models, Chapter 2, Springer Verlag, pp. 37-55, 1989.
B. Abraham et al., “Locally Constant Mean Model and Simple Exponential Smoothing,” Statistical Methods for Forecasting, John Wiley and Sons, pp. 85-89, 1983.
P.B. Gibbons et al., “Fast Incremental Maintenance of Approximate Histograms,” Proceedings of the 23rd VLDB Conference, Athens, Greece, 5 pages, 1997.
Lambert Diane
Pinheiro José C.
Sun Don X.
Al-hashemi Sana
Lucent Technologies - Inc.
Metjahic Safet
Ryan & Mason & Lewis, LLP
LandOfFree
Method and apparatus for updating records in a database... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for updating records in a database..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for updating records in a database... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3008995