Reducing Transaction Databases, Without Lagging Behind or Losing Information

Abstract

This paper describes a way to reduce a database of transaction records when interest lies in the behaviors of the people making the transactions. A fixed length data structure, called a signature, is used to summarize the complete, multidimensional behavior of each individual, giving a database that is linear in the number of individuals instead of the number of transactions. The signature structure can be used with both static and dynamic databases. With dynamic databases, a signature can be updated with every transaction that the individual makes, so that the signature adapts reliably and efficiently to changing behavior. The structure of a signature and the initial set of signatures to be assigned to individuals with no past transaction history are derived automatically from a set of past transactions for a set of individuals. An application to wireless calling patterns, in which each signature is limited to about the size of one call record and must be updated at the end of each call, is used to motivate the ideas.