System and method for analyzing database records using sampling and probability

A method for analyzing database records using sampling includes querying a recipient database for recipients with attributes that match one or more specified recipient attributes, querying a sampling database for transactions with attributes that match one or more specified transaction attributes, where the sampling database stores a subset of transactions that are also stored in a transaction database, intersecting the recipients resulting from the querying of the recipient database and the transactions resulting from the querying of the sampling database based on attributes thereof to create a set of joined sample results, and determining an approximate full count value by extrapolating a count value associated with the set of joined sample results based on both a total number of recipients in the recipient database and a total number of transactions in the transaction database.

BACKGROUND

1. Field of the Invention

The present invention relates to the field of database querying, and, in particular, to a system and method for analyzing database records using sampling and probability.

2. Description of the Related Art

Marketers aim to build a list of known recipients with information about those recipients and the purchase transactions in which they engage. For example, an online marketer may track a known recipient (e.g., an existing customer) from a promotional email sent to the recipient containing a hyperlink to the marketer's website, to the actual purchase of a product using, for example, an online shopping cart. When the recipient purchases a product, the marketer obtains valuable information about the recipient's purchasing habits. The marketer may continue to track information about the recipient's purchases over time (such information referred to herein as “transaction data”) to enhance its overall understanding of the recipient. The combination of such transaction data with personal attributes of the recipient such as gender, age, address and interests (such information referred to herein as “recipient data”) allows the marketer to more accurately target users with relevant, personalized marketing promotions or other marketing content.

Typically, personal attributes for a given recipient may be updated from time to time, but the quantity of such data associated with a given recipient stays relatively constant over time. Thus, for a given marketer, the size of recipient data is proportional to the number of recipients who are known to the marketer, and grows only when the marketer identifies new recipients. Conversely, the size of the transaction data can grow quickly as recipients make purchases over time. Typically, recipient data is stored in a separate database or database table from transaction data.

Marketers often desire to send marketing content to recipients deemed likely to identify with the product or service being advertised in the content. Effective targeting relies on using both recipient data and transaction data. For example, a cycling merchant located in San Francisco may desire to send a particular promotion to a subset of its known customers, e.g., men who are between the ages of 18 and 40, reside in certain zip codes in the San Francisco Bay Area, and who have purchased one or more bicycle-related products in the past six months.

Marketers also often desire to know the approximate number of potential recipients of a proposed promotion before deciding to actually launch the promotion or modify the promotion. For example, if the number is low, the criteria may need to be loosened, and vice-versa. Traditionally, in order to determine such a number, the marketer would execute separate queries against the recipient database and the transaction database, join the results using an intersection or union set operation, and then either count or query the resulting data set. However, due to the large amounts of recipient data—and even larger amounts of transaction data—typically managed by marketers, running such database queries simply to obtain a count of potential recipients is prohibitive with respect to cost, time and computing resources. As a result, the number of queries that the marketer is able to effectively execute, and the marketer's ability to fine tune and effectively target marketing communications, is significantly reduced.

Accordingly, there remains a need in the art for a technique that addresses the drawbacks and limitations discussed above with respect to analyzing database records.

SUMMARY

One embodiment of the invention provides a method for analyzing database records using sampling. The method includes querying a recipient database for recipients with attributes that match one or more specified recipient attributes, querying a sampling database for transactions with attributes that match one or more specified transaction attributes, wherein the sampling database stores a subset of transactions that are also stored in a transaction database, intersecting the recipients resulting from the querying of the recipient database and the transactions resulting from the querying of the sampling database based on attributes thereof to create a set of joined sample results, and determining an approximate full count value by extrapolating a count value associated with the set of joined sample results based on both a total number of recipients in the recipient database and a total number of transactions in the transaction database.

Another embodiment of the invention provides a computer system comprising a processor configured to analyze database records using sampling. In particular, the computer system performs the steps of querying a recipient database for recipients with attributes that match one or more specified recipient attributes, querying a sampling database for transactions with attributes that match one or more specified transaction attributes, wherein the sampling database stores a subset of transactions that are also stored in a transaction database, intersecting the recipients resulting from the querying of the recipient database and the transactions resulting from the querying of the sampling database based on attributes thereof to create a set of joined sample results, and determining an approximate full count value by extrapolating a count value associated with the set of joined sample results based on both a total number of recipients in the recipient database and a total number of transactions in the transaction database.

Further embodiments of the present invention provide a non-transitory computer-readable storage medium that includes instructions for causing a computer system to carry out one or more of the methods set forth above.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

FIG. 1illustrates a networked computer environment100in which embodiments of the invention may be practiced. As shown, networked computer environment100includes a plurality of client computers110(only two of which are shown) and a plurality of web servers120with associated databases125. Client computers110and web servers120are connected over a computer network130, e.g., the Internet.

Each client computer110includes conventional components of a computing device, e.g., a processor112, a system memory114, a hard disk drive, input devices such as a mouse and a keyboard, and output devices such as a monitor, among others. Each web server120includes a processor122and a system memory124, and manages the contents stored in respective database125.

As shown, database125-1includes recipients150, transactions152, and sample recipients/transactions154. In one embodiment, each of recipients150, transactions152, and sample recipients/transactions154are relational database tables. Recipients150is configured to store, for each recipient known to networked computer environment100, a record that includes one or more attributes of the recipient, e.g., a unique identifier (ID), name, email address, billing address, gender, age, interests, and the like. Transactions152is configured to store, for each transaction executed by a recipient known to networked computer environment100, a record that includes one or more attributes of the transaction, e.g., the unique ID of the recipient who executed the transaction, the date of the transaction, the specific products/services sold to the recipient, the monetary amount of the transaction, and the like. In one embodiment, sample recipients/transactions154is configured to actively maintain a sample dataset of transactions152associated with a given set of random sample recipients.

For example, if recipients150and transactions152include records relating to one-hundred thousand recipients and ten million transactions, respectively, then sample recipients/transactions154may include transaction records relating to ten thousand randomly-selected recipients. Moreover, sample recipients/transactions154can be configured to automatically update its transaction records when corresponding changes are made to transactions152for a recipient who is also a sample recipient, e.g., when insertions and/or updates occur, or to automatically add transaction records for a new sample recipient when a new recipient is added to recipients150and is associated with sample recipients/transactions154. Sample recipients/transactions154may be adjusted to maintain a more accurate sample of transactions152, e.g., by increasing the number of sample recipients whose data is stored in sample recipients/transactions154, though overhead is increased as a result.

The web server120is programmed to communicate with client computers110and other web servers120using, e.g., the TCP/IP protocol. Client computers110are programmed to execute web browser programs and other software applications and access the web pages and/or applications managed by the web servers by specifying a uniform resource locator (URL) for the web server into the browser.

In the embodiments of the present invention described below, users are respectively operating client computers110that are connected to web servers120over the Internet. The web pages that are displayed to a user are transmitted from web servers120to that user's client computer110and processed by the web browser program stored in that user's client computer110for display through the monitor of that user's client computer110.

Client computer110may be a personal computer, smart phone, touch pad, touch screen, or any other device suitable for practicing one or more embodiments of the present invention. It should be noted that the present invention can be implemented in hardware, software, or in a combination of hardware and software, e.g., using application specific integrated circuits (ASIC), a general purpose computer or any other hardware equivalents.

In one embodiment, the web server120may be configured to deliver a user interface to the user at the client computer110via the network130. For example, the user interface may be displayed in a web browser executed by the client computer110.

Analyzing Database Records

Embodiments of the invention provide a technique for analyzing database records using database sampling and probability. In particular, web server120queries recipients150, transactions152, and/or sample recipients/transactions154based on recipient attributes and/or transaction attributes that are provided by, e.g., a marketer requesting data from web server120. As described herein, web server120may execute additional operations prior to executing the query, e.g., dynamically sampling recipients150and/or statically sampling transactions152, which is described in detail below in conjunction withFIGS. 2-4and significantly reduces the overall execution time of the query.

FIG. 2is a conceptual diagram of performing a quick count technique using recipient-only data filters200, according to one embodiment of the invention. Because recipient attributes can change over time, statically sampling recipients150and then maintaining the sample snapshot on an ongoing basis involves significant overhead. In addition, recipient data grows more slowly over time than transaction data. Therefore, dynamic sampling of recipients150, where sampling data is extracted from recipients150on demand when a query to recipients150is requested, is practical to implement and avoids the overhead associated with maintaining a static sampling thereof. Most modern relational databases provide mechanisms to extract a random sample of the data stored therein.

As shown inFIG. 2, sample recipient data206is generated based on a dynamic sampling204of all recipient data202stored in recipients150. In one embodiment, web server120is configured to execute dynamic sampling204based on settings specified by, for example, an administrator (e.g., a marketer) via the user interface described above in conjunction withFIG. 1. For example, web server120may be configured to sample ten percent of all recipient data202in order to create sample recipient data206. In some embodiments, sample recipient data206is stored in a temporary database table that has the same schema as recipients150.

Web server120executes filtering208based on recipient attributes specified by the administrator through the user interface. For example, the administrator may specify recipient attributes that target women between the ages of 18-30 who reside in Houston, Tex. Accordingly, web server120queries sample recipient data206for recipients that match the foregoing attributes, which yields filtered sample recipient data210.

Next, web server120executes extrapolation212, which involves reversing the sampling procedure performed through dynamic sampling204—that is, taking the count of filtered sample recipient data210and extrapolating the count to an approximate result for all recipient data202. Continuing with the example described above, and assuming that filtered sample recipient data210includes one-hundred entries, web server120multiplies the one hundred entries by the inverse of ten percent, i.e., a value of ten, to yield one thousand inferred results214. Thus, the administrator may assume, based on the random sampling technique and basic probability theory, that all recipient data202includes approximately one thousand recipients who meet the criteria specified by the administrator. In this way, the amount of data that has to be analyzed to arrive at an approximate count for the results of the query is significantly reduced, which decreases latency and requires fewer operations to database125.

FIG. 3is a conceptual diagram of performing a quick count technique using transaction-only data filters300, according to one embodiment of the invention. As is commonly understood, transaction tables, such as transactions152, receive frequent inserts, and rarely receive updates and deletes. Because of the size of transactions152, it is generally impractical to employ dynamic sampling of this database. Therefore, embodiments of the invention implement static sampling of all transaction data302included in transactions152to create sample recipients/transaction data306, where sampling data is initially extracted from all transaction data302for a given set of random recipients and then updated as changes are made to transactions152for such sample recipients. For example, as the sample recipients engage in additional transactions over time, the transaction data associated with such additional transactions will be added to sample recipients/transaction data306. In particular, static sampling involves identifying at random a sample number of recipients in recipients150, where the random sample can grow progressively as recipients are added to recipients150. Transactions of each recipient in the random sample are then monitored and tracked. Because the size of the random sample of recipients is only a small fraction of all recipients in recipients150, the size of the transactions associated with those sample recipients is accordingly limited.

As shown inFIG. 3, sample transaction data306is generated based on a static sampling304of all transaction data302stored in transactions152associated with the given random sampling of recipients. In one embodiment, web server120is configured to execute static sampling304. Alternatively, database125, which stores transactions152and sample recipients/transactions154, may include therein a software engine that automates static sampling304independent of web server120. As with the dynamic sampling204described above, static sampling304may be configured to sample a percentage of all transaction data302, e.g., eight percent, in order to maintain sample recipients/transaction data306within sample recipients/transactions154.

Web server120executes filtering308based on transaction attributes specified by the administrator through the user interface. For example, the administrator may specify transaction attributes that target transactions associated with a certain genre and locale, such as skiing/snowboarding equipment purchases in Mammoth, Calif. Accordingly, web server120queries sample recipients/transaction data306for transactions that match the foregoing transaction attributes, which yields filtered sample recipients/transaction data310.

Web server120then executes extrapolation312according to the techniques described above in conjunction withFIG. 2. For example, assuming that filtered sample recipients/transaction data310includes ten thousand entries, web server120multiplies the ten-thousand entries by the inverse of eight percent, i.e., a value of 12.5, to yield one hundred twenty-five thousand inferred results314. Thus, the administrator may assume, based on the sampling technique and basic probability theory, that all transaction data302includes approximately one hundred twenty-five thousand recipients who meet the criteria specified by the administrator. Again, the amount of data that has to be analyzed to arrive at an approximate count for the results of the query is significantly reduced, which decreases latency and requires fewer operations to database125.

FIG. 4is a flow diagram of a method400for performing a quick count technique using both recipient data filters and transaction data filters, according to one embodiment of the invention. Persons skilled in the art will understand that, even though the method400is described in conjunction withFIGS. 1-4, any system configured to perform the method steps is within the scope of embodiments of the invention.

As shown, method400begins at step402, where web server120receives a set of recipient attributes. As described herein, such recipient attributes may be submitted by an administrator via a user interface. In some embodiments, the user interface may display each available recipient attribute as a selectable checkbox, which enables the administrator to build complex criteria. For example, the administrator may select one or more checkboxes to target men between the ages of 25 and 35 who are located in New York and enjoy tennis.

At step404, web server120queries a recipient database, e.g., recipients database150, for recipients with attributes that match one or more recipient attributes in the set of recipient attributes. In some cases, web server120may first create sample recipient data, as described above in conjunction withFIG. 2, if the recipient database includes a number of records that exceeds a threshold value. In turn, the overall latency of executing method400may be reduced. Accordingly, at step406, web server120receives the recipients from the recipient database based on the query executed in step404.

At step408, web server120receives a set of transaction attributes. Continuing with the example described above, the administrator may select one or more transaction attributes via user interface checkboxes, for example, tennis-related purchases within the last six months.

At step410, web server120queries a sampling database associated with a transaction database, e.g., sample recipients/transactions154and transactions152, respectively, for sample transactions with attributes that match the specified set of transaction attributes. Accordingly, at step412, web server120receives the resulting transactions from the sampling database.

At step414, web server120intersects the resulting recipients and the resulting transactions to create a set of joined sample results. In particular, such intersection comprises both removing resulting recipients that do not correspond to any of the resulting transactions and removing resulting transactions that do not correspond to any of the resulting recipients.

At step416, web server120infers an approximate count value for the query at issue by extrapolating the set of joined sample results according to both a total number of recipients in the recipient database and a total number of transactions in the transaction database, as described above inFIGS. 2 and 3. At step418, web server120returns the count value, which may be displayed within the user interface.

In sum, embodiments of the invention provide a technique for analyzing database records using database sampling and probability theory. Recipient data and transaction data are dynamically and/or statically sampled. The sampled recipient data and/or sampled transaction data is filtered based on target attributes included in a query, which reduces the overall execution time of obtaining an approximate count of the results of the query when compared to querying both the entire recipient database and the entire transaction database. The count of the filtered data set is then extrapolated based on the size of the recipient data and/or the size of the transaction data, thereby yielding a result that approximates the result that would be yielded if the recipient data and the transaction data were queried as a whole.

The invention has been described above with reference to specific embodiments and numerous specific details are set forth to provide a more thorough understanding of the invention. Persons skilled in the art, however, will understand that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. The foregoing description and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.