Method and system for forecasting information based on events and criterion

A method and system provide the ability to forecast events that match a criterion. Input is received and includes an event set and a criterion. The event set includes events and each of the events is a record with features. Each feature is an instance of a feature type (FT) and feature value (FV) combination. The criterion is a logical statement that specifies a criterion FT, a criterion FV, and an operator. The event set is partitioned and a partition BitSet is built for each partition. Each partition length of each partition BitSet is based on a number of the events. Based on the partition BitSets, a partition FT-FV count is created. For each partition, a partition FT criterion BitSet is created and a partition Criterion BitSet is computed based thereon. The forecast is then computed based on the partition Criterion BitSet.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to computing, outputting, and utilizing metadata for a large dataset. In particular, embodiments of the invention relate to a method, system, apparatus, and article of manufacture for quickly determining and forecasting a count of events and an accurate average aggregate value for those events, followed by the output and utilization of such information.

2. Description of the Related Art

In various domains/industries, given an input of a set of events with various features having values, upon receipt of a specific criterion, it is desirable to determine and forecast the number of events that satisfy such criterion and an average value of the aggregate feature of such satisfying features. Depending on the domain/industry, there can be hundreds, to thousands, to billions of different events received on a daily basis that need to be quickly evaluated to determine if they match a given criteria/set of criteria. Quickly determining how and which criterion/criteria provide a resulting set of events in a dynamic, efficient, and fast manner is not only desirable, but essential to provide satisfactory results/services to clients/customers.

Prior art systems evaluate such events utilizing a brute-force method that matches all events with a criterion/criteria to determine a forecast and/or an aggregate value. The pessimistic brute force complexity is 0 (Event Count*Criterion Feature Type Count). In this regard, such a brute-force method is slow, inefficient, and fails to achieve desired results. Accordingly, what is needed is a system/method for determining/forecasting the number of events that match a defined set of criteria, and determining an accurate average aggregate value for such events in a fast, efficient manner.

SUMMARY OF THE INVENTION

Embodiments of the invention overcome the problems of the prior art by pre-processing an input of events to corresponding metadata and BitSets and upon receipt of criterion performing logical operations on the BitSets to quickly and efficiently forecast matching results. In particular, such processing enables forecasting by reducing the complexity of computing a count of events, an accurate average aggregate value for those events, and a breakdown of feature type restrictiveness in the criterion. Once forecasted, actual generation of a campaign/commodity, engineering design, etc. may be conducted based on the forecasting. Further, real-world physical budgets and/or plans may need to be adjusted/created based on the campaign/commodity/design generation.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Terminology

The terms and definitions set forth below provide the context within which embodiments of the operation may operate.

CPU Core Count: Number of CPUs available on machine.

Event Set: A set of Events used as input.

Event: A record, within an Event Set, with one or more Features, an implied timestamp, and optionally an Aggregate.

Event Set Span: The distance between the oldest and newest Event timestamp across the Event Set.

Feature: An instance of a combination of Feature Type and Feature Value.

Feature Type: One of the two characteristics of a specific Feature, representing a dimension against which to forecast. Within an Event, some Feature Types can have only one Feature Value, others can have multiple.

Aggregate: An instance of combination of Aggregate Type and Aggregate Value.

Aggregate Type: Each Event record may have a single Aggregate Type. An Aggregate Type has a single Aggregate Value. If no Aggregate Type is provided, then embodiments of the invention will not generate an average Aggregate value for matching Events.

Partition Key: A formula with which to divide an Event Set into Partitions made up of smaller subsets of Events. This formula could be based on one or more Feature Types, Feature Values, count of Events, time, or randomization. The main goal of the Partition Key is to enable parallelism by reducing the total count of events in a Partition, but not reducing it all the way to 1, as that would defeat the purpose of partitioning. Further, the Partition Key is meant to split Events, count-wise, in a distributed manner (e.g., by number of Events and/or uniformly) across Partitions. If e.g., due to Partition Key definition, some Partitions end up having orders of magnitude more Events than other Partitions, than this would defeat the purpose as well.

Partition: A set of Events, grouped by Partition Key and time, which will first be analyzed together, before embarking on cross-Partition analysis. The position of each Event record within a Partition is significant information, and is locked down at the point of creating the Partition.

Partition Feature Types: The subset of Feature Types available in a specific Partition, defined as:Partition Feature Types {Partition Key: Value;Feature Types: List of Feature Types available in this Partition;}

Intra-Feature Type Operators (used only for Feature Types):EQUAL: =. Event matches Criterion if Event has one of the listed Feature Values in Criterion.NOT EQUAL: !=. To match, an Event cannot have any of the listed Feature Values in Criterion.

Aggregate Type Operator (used only for Aggregate Type):GREATER THAN OR EQUAL TO: >=. Used for denoting a range for Aggregate Types only.LESS THAN OR EQUAL TO: <=. Used for denoting a range for Aggregate Types only.

Further operators may include >= and <= for Feature Types.

Inter-Feature Type Operators: AND or OR. These are for non-Aggregate Types.

Criterion: A logical statement with Feature Type(s), Feature Value(s), Intra-Feature Type Operators, Inter-Feature Type Operators, a Criterion Span, and optionally an Aggregate with an Aggregate Type Operator.

Criterion Span: Interval of time over which to forecast.

BitSet: A set of 1s and 0s, equal in length to the number of Events being evaluated in a Partition. This is represented by as many words as needed to account for all Events in that Partition. The position of each Event within a BitSet corresponds to the position of that Event record within the Partition. For example, with 200 Events, each BitSet is 200 bits, while technically implemented using 4 Words=ROUNDUP(200/64).

BitSet (0): A BitSet created with all bits cleared to 0. For example, for 4 Events BitSet (0)=[0, 0, 0, 0].

Aggregate rounding: To speed up forecasting calculations, Aggregate Values can be rounded. For example, 73.352 could be rounded to 73.4; 917262 could be rounded to 917300. Precision to round to is up to implementation needs.

FIG. 1illustrates a BitSet concept entity-relationship diagram in accordance with one or more embodiments of the invention. As illustrated and described above, the Event Set102contains multiple events104. Further, the event set is associated with an event set span106that defines the distance between timestamps across the Events104in the Event Set102. Each Event104consists of record that contains one or more Features108and a potential Aggregate110.

Each Feature108is an instance of a combination of a Feature Type and a Feature Value. The Aggregate110is an instance of a combination of an Aggregate Type and a single Aggregate Value. An exemplary Aggregate110is a price.

An Event Set102can be divided into multiple partitions112that are grouped by a partition key. Accordingly, each partition112has multiple events102. Further, each partition112has a subset of feature types114that are available in a specific partition. The number of different feature type values in each partition112is counted/summed in the partition feature type value count116.

As described above, the criterion118is a logical statement that is used to select/filter the events104. Accordingly, the criterion118may specify one or more features108(e.g., feature type and feature value) and may optionally specify an aggregate110with an aggregate type operator120. The aggregate type operator specifies an inequality (e.g., greater than or equal to OR less than or equal to). For the features108, the criteria118may be based on one (or both) of two different types of operators—inter-feature type operator122and/or intra-feature type operator124. Inter-feature type operators122are logical AND/OR operations. Intra-feature type operators124specify whether a feature value is equal to and/or not equal to a specified feature value.

In addition, the criterion118specifies a time period/interval over which to evaluate/filter the features/aggregates. This time period/interval is referred to as the Criterion Span126. Criterion Span is a forecasting (looking forward) window.

Methodology

One or more embodiments of the invention provide the ability to forecast the total number of records that match a particular specified criteria. There are two primary phases/steps that may be used to perform the matching/filtering of the events104based on specified criteria:

(2) Criterion118Processing—when the criterion118arrives/is available and is used to evaluate/filter the events104to perform the forecasting.

FIG. 2illustrates the logical flow for counting events that comply with a defined set of criteria in accordance with one or more embodiments of the invention.

Steps202-208provide for pre-processing of the events104in an event set102. At step202, input in the form of the event set102are received. In this regard, the event set102consists of records that each represent an event consisting of a feature and/or an aggregate along with an implied time stamp. Thus, the input received at step202may include a set of feature type (FT)-feature value (FV) combinations along with an optional aggegate type (AT)-aggregate value (AV) combination. For example, an exemplary event may comprise:Time: 11; FT1: 100; FT2: 300; FT3: 500; AT: 1.123187

Each event104may represent a variety of different information elements depending on the industry in which it is used (see industry specific details below).

At step204, the events104are partitioned into partitions112. Such a partitioning may include the rounding of aggregate values (e.g., to reduce the dimensionality of aggregate types). In one or more embodiments, such a rounding may round to tenths or hundredths (e.g., rounding a price aggregate to one digit beyond the decimal place). To divide the events104into partitions112, a partition key is determined/decided. As described above, the formula for determining the partition key may be based one or more feature types, feature values, or count of events (e.g., a specified number of events in each partition). Further, the partition key serves to reduce a total count of the events in each partition and attempts to split the events, count-wise, across the partitions in a distributed manner which may be uniform. Such partitioning enables efficient processing of the events. Once the partition key has been decided/determined, the event set102is partitioned into the partitions112.

At step206, having created partitions112using the partition key formula, a partition BitSet is built for each partition. To build the partition BitSet, available feature types and optional aggregate type are gathered into a partition feature type definition (i.e., a list of the various feature types and optional aggregate type in each partition). Once feature types are gathered, for each FT-FV combination (and the optional AT-AV combination(s)), a partition BitSet is built. The build process begins with BitSet (0) (i.e., every bit is equal to 0) and the bit at position (P) is set to 1 if the FT-FV combination is found in the Event (E)104that is represented by potision (P). Each partition's length of BitSets equals the number of events104in that partition112. Thus, for each of the AT-AV combinations, a bit at position (P) is set to 1 when an AT-AV combination is found in the event (E) represented by position (P). Further, only for AT, the resultants BitSets may be sorted in ascending order by AV.

At step208, Partition FT-FV and AT-AV counts are created. The counts list the number of occurrences of each FV, within a partition-FT combination, and optionally of each AV within an optional partition-AT combination.

Once the criterion118is received/available, criterion processing is performed as defined in steps210-218. The criterion118consists of a logical statement that specifies a set of criterion FT-FV combinations, a set of logical operators, and optionally a criterion AT-AV. Steps210-216are performed for each partition.

FIG. 3illustrates the logical flow for step210—computing the partition on FT criterion BitSet in accordance with one or more embodiments of the invention.

At step302, for each FT-FV criterion combination within the criterion118, a single BitSet (referred to as an FT-FV Criterion BitSet) is assembled, its count (referred to as FT-FV criterion count) is computed, and both the BitSet and count are stored.FIG. 4illustrates the logical flow for assembling the BitSet and count of step302ofFIG. 3in accordance with one or more embodiments of the invention. Note that a number of bits in the FT-FV criterion BitSet correpsonds to a number of events in the partition. For each FT-FV Criterion combination, an FT-FV Criterion BitSet of all zeroes (0) is used, and a bit at position (P) is set to 1 when the FT-FV Criterion combination is found in the event (E) represented by position (P).

At step402, a determination is made regarding whether the FT or FT-FV combination within the input criterion118exists in the partition112. If the combination does not exist, the BitSet (0) is used at step404. Thus, for each FT-FV Criterion combination having a common FT, the FT-FV Criterion BitSets are combined to create a single FT Criterion BitSet by the process described below.

If the combination exists in the partition, a determination is made at step406regarding what type of intra-feature operator124is used (for the FT-FV combination). If the “=” intra-feature type operator124is used, a logical OR operation is performed against all of the pre-computed FT-FV Criterion BitSets at step408.

If a “!=” intra-feature type operator124is used, then a logical NOT operation is performed against the (precomputed) FT-FV Criterion BitSets at step410. Thereafter, at step412, a logical AND operator is performed against the results to compute the FT Criterion BitSet. The reason to ‘NOT and then AND together’ vs. to ‘OR together and then NOT’ is because the former is cheaper computationally when BitSets are used in concert with stepwise AND-ing across BitSets. Further, embodiments of the invention stop computing when a stepwise AND operation yields BitSet (0).

Returning toFIG. 3, at step304, the Partition FT criterion BitSet is computed by applying the inter-feature type operator122(OR or AND) found in the Criterion118between computed criterion FT-criterion FV combinations found/computed in the Criterion118.

Returning toFIG. 2, at step212, the Partition AT Criterion BitSet is computed.FIG. 5illustrates the detailed logical flow for computing the Partition AT Criterion BitSet in step212ofFIG. 2in accordance with one or more embodiments of the invention. In this regard, the input may optinally include an aggregate that consists of an instance of a combination of an aggregate type (AT) and an aggregate value (AV). At step502, a subset of AT-AV BitSets is selected corresponding to matching AT-AV in the Criterion. At step504, for each Partition AT Criterion BitSet, a logical AND is performed between the respective BitSet and the Partition FT Criterion BitSet, and the counts are stored. In other words, for each selected AV BitSet, a logical AND operation is performed between the partition AT-AV BitSet and the partition FT Criterion BitSet.

Step506is an optional step that is only performed if the Criterion118has an AT. If the AT is present in the criterion118, Partition AT Criterion BitSet is computed by applying the OR logical operator across resultant BitSets.

Returning toFIG. 2, at step214, each AT-AV BitSet within the partition112is processed.FIG. 6illustrates the logical flow for processing each AT-AV BitSet at step214ofFIG. 2in accordance with one or more embodiments of the invention. At602, a determination is made regarding whether the Criterion118includes AT-AV (i.e., an Aggregate110). If the Criterion118includes an Aggregate110, only the AT-AVs within the Criterion's range are used at604. If the Criterion118does not have an Aggregate110, all AT-AVs are used at606. At608, the AV Match BitSet is computed by applying a logical AND operator between the FT Criterion BitSet and the AV BitSet. In other words, for each partition AT-AV BitSet within each partition, if the criterion includes an AT-AV and a range, only events having AT-Avs within the range of the AT-AV specified are used (otherwise all AT-AVs are used), and the partition AV Match BitSet is computed by applying a logical AND operation between the FT Criterion BitSet and the partition AT-AV BitSet.

At step216, the Partition Criterion BitSet is computed (based on the partition FT criterion BitSet). If AT is provided, a logical AND operator is applied between the Partition FT Criterion BitSet and the Partition AT Criterion BitSet. If AT is not provided, the Partition FT Criterion BitSet is used. The bits in the Partition Criterion BitSet are then summed/counted to generate a count of Events in the Partition112matching the AV available in Events104.

At step218, the forecasts are computed.FIG. 7provides an overview of the forecasts that are computed in step218ofFIG. 2in accordance with one or more embodiments of the invention. At702, the counts from each Partition Criterion FT BitSet are summed to produce a Total Matched Count.

At704, the Total Matched Count per normalized unit of time is computed by multiplying the Total Matched Count produced in step702by the Criterion Span126and dividing by the Event Set Span.

At706, the total count of Events104in the Event Set102is calculated.

At708, using all AV Matches for the Criterion118, an accurate average AV is computed. An estimated average AV may also be generated (by performing at pre-Criterion time, certain operations currently done at post-Criterion time).

At710, for each FT-FV combination in the Criterion118, roll up, across Partitions112, individual FT counts and their FV counts to find the most restrictive portion of Criterion118(i.e., the smallest values). If a Criterion FT-FV combination does not exist in the Partition112, and the Intra-Feature Type Operator124is ‘=’ then 0 is used as the count, otherwise the Event count in the Partition112is used as the count.

Exemplary Processing

WhileFIGS. 2-7illustrate the logical flow for performing the forecasting, an example data set that is processed in accordance with this logical flow may be useful to gain a better understanding. Table A illustrates an exemplary data set that may be processed in accordance with one or more embodiments of the invention.

As described below, the first example is based on Criterion 1 from Table A while the second example is based on Criterion 2 from Table A.

As illustrated in Table A, the following Events104and Criterion118are input at step202:

At step204, the three steps of (1) reducing the dimensionality, (2) deciding on a partition key, and (3) partitioning the event set102are performed. Accordingly, the AVs are rounded to 1 digit beyond the decimal place. In the example, the formula used for the partition key is to place a maximum of 4 Events104in a partition112. To partition the event set102, the Event Set Span is first computed: Max time (Time: 13)−Min time (Time: 11)=2. Based on the Event Set Span and the partition key, the Events104in the input data are partitioned into Partitions112as set forth in Table B:

Step206provides for building the Partition BitSets. The first step in this process is to create the Partition definitions for each Partition. In particular, the available FTs are gathered into a Partition FT definition for each partition. For Partition 1:

As described above, for each FT-FV combination (and the AT-AV combination), a Partition BitSet is built. The FT-FV and AT-AV BitSets for Partition 1 are set forth in Table C below.

At step208, the Partition FT-FV counts are created. The counts for Partition 1 are set forth in Table D below.

The creation of the FT definitions, FT-FV/AT-AV BitSets (step206) and counts (step208) are then repeated for Partition 2.

The FT definitions for Partition 2 are:

The FT-FV and AT-AV BitSets for Partition 2 are set forth in Table E below.

The counts for Partition 2 are set forth in Table F below.

Once all the initial set of events have been processed, when the criterion is available, processing continues with step210by computing the Partition FT Criterion BitSet for each partition112. In this regard, for each FT-FV within the Criterion118, a single BitSet is computed. If the FT- or FT-FV combination does not exist in the Partition, BitSet(0) is used. Alternatively, if the combination exists, then the intra-feature operator124(“=” or “!=) utilized determines the logical operations to perform. For example, for FT1−100, the Criterion118uses “=” as the intra-feature operator124, accordingly, the logical OR operation is used. However, since there is only 1 value, there is no need to perform the OR operation and the BitSet for FT1−100 [1,1,0,0] is used:

The next criterion is FT2=300 or 800. Since “=” is used, a logical OR operation is performed for the two FT2BitSets:

The Criterion for FT3utilizes “!=”. Accordingly, for the count, a logical NOT is performed on the FT-FV combination before counting and the results are combined using a logical AND operator. Since the FT-FV combination for FT3−900 and FT3−950 do not exist in Partition 1, BitSet(0) is used. Lastly, the Partition FT Criterion BitSet is created by applying the Inter-Feature type operator (OR or AND) found in the Criterion—in other words, since the Criterion specifies the different FT-FV combinations are combined using an AND operator, all of the FT BitSets are also combined using an AND operator:

At step212, the Partition 1 AT Criterion BitSet is created. As AT<=2.0 is in the Criterion, the AVs to be used in Partition 1 are 1.2, 1.4 and 1.8, with Partition 1-AV BitSets of [1, 0, 0, 0], [0, 0, 0, 1] and [0, 1, 0, 0] respectively. A logical AND operation is performed between the respective AV BitSet and the Partition FT Criterion BitSet (e.g., [1,1,0,0]) and the counts are stored:

Thereafter (also within step212), since the criterion has an AT, the Partition AT Criterion BitSet is computed by applying the OR logical operator across resultant BitSets:

At step214, the AT-AV BitSet is processed. In particular, the AV Match BitSet is computed by applying a logical AND operator between the FT Criterion BitSet and the AV BitSet:

At step216, the Partition Criterion BitSet is computed by performing a logical AND operation between the Partition FT Criterion BitSet with the Partition AT Criterion BitSet:

The above process is then repeated for Partition 2.

Create FT-FV and then FT BitSets for FTs in Criterion:

As AT<=2.0 in Criterion, the AVs to be used in Partition 2 are 1.2 and 1.8, with Partition 1-AV BitSets of [1, 0, 0] and [0, 0, 1] respectively.

Once steps210-216have been computed for both Partition 1 and Partition 2, the forecasts can be computed at step218(e.g., as detailed inFIG. 7). Referring toFIG. 7, the total matched count is computed at step702:Total Matched Count=Partition 1 Criterion FT BitSet ([1, 1, 0, 0]) Count (2)+Partition 2 Criterion FT BitSet ([1, 0, 0]) Count (1)=3.

At step704, the normalized total matched count (that is normalized per unit of time) is computed:Total Matched Count normalized per unit of time=3*9/2=13.5.

At step706, the total event count is calculated: 7.

At step708, the average AV is computed:[(1*1.2+1*1.8)+(1*1.2)]/3=1.4.

At step710, the most restrictive portion of the Criterion118is determined.

Based on these counts, one may determine that the most restrictive FT is FT1. The next restrictive FT is FT2, and within it, the most restrictive FV is 800. But given 300 is OR-ed with 800, the restrictiveness of 800 is neutralized.

Based on the above, Table G illustrates the exemplary Output for the Example with Criterion 1.

As illustrated in Table A, the same Events104described above are input at step202. However, the Criterion118for this example differ. The Criterion118input at step202in this example is:FT1=100 AND FT2=300, 800 AND FT3NOT IN (900, 950)Criterion Span=9

Since the Event Set102are the same in both examples, steps204-208, described above with respect to the Example 1—Criterion 1, produce the same results for this Example. The examples differ in their processing for steps210-218as the Criteria118in the examples differ.

At step210, the Partition 1 FT Criterion BitSet is created with the same result as with Criterion 1:

At step212, the Partition 1 AT Criterion BitSet is computed by performing a logical AND operation between the AV BitSets and the FT Criterion BitSet ([1, 1, 0, 0]):

At step214, the AT-AV BitSet is processed. As no AT is provided in the Criterion118, all AVs are used:

At step216, the Partition 1 Criterion BitSet is created. Since an AT is not provided in the Criterion118, the FT Criterion BitSet ([1, 1, 0, 0]) is used. The bits are summed to generate the count of Events104in the Partition112matching the AV available in the Events104:

The process of steps210-216are then repeated for Partition 2. At step210, the Partition 2 FT Criterion BitSet is created. For the Criterion 2, the results is the same as in Example 1 above:

At step212, the Partition 2 AT Criterion BitSet is computed:

At step214, the AT-AV BitSet is processed. First, the Partition 2 AV Match BitSet is created:

As part of step214, the Partition 2 Criterion BitSet is created. Since no AT is provided, the Partition 2 FT Criterion BitSet is used for this step and the bits are summed:

Once steps210-216are performed for both Partitions112, the forecasts may be computed:

Compute Total Matched Count Normalized Per Unit of Time:Total Matched Count normalized per unit of time=4*9/2=18.

Total Count of Events in Event Set:7.

Compute Average AV:[(1*1.2+1*1.8)+(1*1.2+1*2.5)]/4=1.675.

Calculate Most Restrictive:

Same as in Example 1 above.

Based on the forecast computations, the process may output the forecasts. An exemplary output for Example 2—Criterion 2 is illustrated in Table H.

INDUSTRY SPECIFIC EXAMPLES

Embodiments of the invention may be utilized in various different domains/industries. Table I below illustrates various exemplary domains/industries, how the different inputs/elements map to such an industry, and an exemplary/primary/main use case for that industry/domain.

HARDWARE EMBODIMENTS

FIG. 8is an exemplary hardware and software environment800used to implement one or more embodiments of the invention. The hardware and software environment includes a computer802and may include peripherals. Computer802may be a user/client computer, server computer, or may be a database computer. The computer802comprises a general purpose hardware processor804A and/or a special purpose hardware processor804B (hereinafter alternatively collectively referred to as processor804) and a memory806, such as random access memory (RAM). The computer802may be coupled to, and/or integrated with, other devices, including input/output (I/O) devices such as a keyboard814, a cursor control device816(e.g., a mouse, a pointing device, pen and tablet, touch screen, multi-touch device, etc.) and a printer828. Processors804A and804B may be multi-core processors, that may operate on a bus size that could be 64-bit, or higher. In one or more embodiments, computer802may be coupled to, or may comprise, a portable or media viewing/listening device832(e.g., an MP3 player, IPOD, NOOK, portable digital video player, cellular device, personal digital assistant, etc.). In yet another embodiment, the computer802may comprise a multi-touch device, mobile phone, gaming system, internet enabled television, television set top box, or other internet enabled device executing on various platforms and operating systems.

In one embodiment, the computer802operates by the general purpose processor804A performing instructions defined by the computer program810under control of an operating system808. The computer program810and/or the operating system808may be stored in the memory806and may interface with the user and/or other devices to accept input and commands and, based on such input and commands and the instructions defined by the computer program810and operating system808, to provide output and results.

Output/results may be presented on the display822or provided to another device for presentation or further processing or action. In one embodiment, the display822comprises a liquid crystal display (LCD) having a plurality of separately addressable liquid crystals. Alternatively, the display822may comprise a light emitting diode (LED) display having clusters of red, green and blue diodes driven together to form full-color pixels. Each liquid crystal or pixel of the display822changes to an opaque or translucent state to form a part of the image on the display in response to the data or information generated by the processor804from the application of the instructions of the computer program810and/or operating system808to the input and commands. The image may be provided through a graphical user interface (GUI) module818. Although the GUI module818is depicted as a separate module, the instructions performing the GUI functions can be resident or distributed in the operating system808, the computer program810, or implemented with special purpose memory and processors.

In one or more embodiments, the display822is integrated with/into the computer802and comprises a multi-touch device having a touch sensing surface (e.g., track pod or touch screen) with the ability to recognize the presence of two or more points of contact with the surface. Examples of multi-touch devices include mobile devices (e.g., IPHONE, NEXUS S, DROID devices, etc.), tablet computers (e.g., IPAD, HP TOUCHPAD), portable/handheld game/music/video player/console devices (e.g., IPOD TOUCH, MP3 players, NINTENDO 3DS, PLAYSTATION PORTABLE, etc.), touch tables, and walls (e.g., where an image is projected through acrylic and/or glass, and the image is then backlit with LEDs).

Some or all of the operations performed by the computer802according to the computer program810instructions may be implemented in a special purpose processor804B. In this embodiment, some or all of the computer program810instructions may be implemented via firmware instructions stored in a read only memory (ROM), a programmable read only memory (PROM) or flash memory within the special purpose processor804B or in memory806. The special purpose processor804B may also be hardwired through circuit design to perform some or all of the operations to implement the present invention. Further, the special purpose processor804B may be a hybrid processor, which includes dedicated circuitry for performing a subset of functions, and other circuits for performing more general functions such as responding to computer program810instructions. In one embodiment, the special purpose processor804B is an application specific integrated circuit (ASIC).

The computer802may also implement a compiler812that allows an application or computer program810written in a programming language such as C, C++, Assembly, SQL, PYTHON, PROLOG, MATLAB, RUBY, RAILS, HASKELL, or other language to be translated into processor804readable code. Alternatively, the compiler812may be an interpreter that executes instructions/source code directly, translates source code into an intermediate representation that is executed, or that executes stored precompiled code. Such source code may be written in a variety of programming languages such as JAVA, JAVASCRIPT, PERL, BASIC, etc. After completion, the application or computer program810accesses and manipulates data accepted from I/O devices and stored in the memory806of the computer802using the relationships and logic that were generated using the compiler812.

The computer802also optionally comprises an external communication device such as a modem, satellite link, Ethernet card, or other device for accepting input from, and providing output to, other computers802.

In one embodiment, instructions implementing the operating system808, the computer program810, and the compiler812are tangibly embodied in a non-transitory computer-readable medium, e.g., data storage device820, which could include one or more fixed or removable data storage devices, such as a zip drive, floppy disc drive824, hard drive, CD-ROM drive, tape drive, etc. Further, the operating system808and the computer program810are comprised of computer program810instructions which, when accessed, read and executed by the computer802, cause the computer802to perform the steps necessary to implement and/or use the present invention or to load the program of instructions into a memory806, thus creating a special purpose data structure causing the computer802to operate as a specially programmed computer executing the method steps described herein. Computer program810and/or operating instructions may also be tangibly embodied in memory806and/or data communications devices830, thereby making a computer program product or article of manufacture according to the invention. As such, the terms “article of manufacture,” “program storage device,” and “computer program product,” as used herein, are intended to encompass a computer program accessible from any computer readable device or media.

FIG. 9schematically illustrates a typical distributed/cloud-based computer system900using a network904to connect client computers902to server computers906. A typical combination of resources may include a network904comprising the Internet, LANs (local area networks), WANs (wide area networks), SNA (systems network architecture) networks, or the like, clients902that are personal computers or workstations (as set forth inFIG. 8), and servers906that are personal computers, workstations, minicomputers, or mainframes (as set forth inFIG. 8). However, it may be noted that different networks such as a cellular network (e.g., GSM [global system for mobile communications] or otherwise), a satellite based network, or any other type of network may be used to connect clients902and servers906in accordance with embodiments of the invention.

A network904such as the Internet connects clients902to server computers906. Network904may utilize ethernet, coaxial cable, wireless communications, radio frequency (RF), etc. to connect and provide the communication between clients902and servers906. Further, in a cloud-based computing system, resources (e.g., storage, processors, applications, memory, infrastructure, etc.) in clients902and server computers906may be shared by clients902, server computers906, and users across one or more networks. Resources may be shared by multiple users and can be dynamically reallocated per demand. In this regard, cloud computing may be referred to as a model for enabling access to a shared pool of configurable computing resources.

Clients902may execute a client application or web browser and communicate with server computers906executing web servers910. Such a web browser is typically a program such as MICROSOFT INTERNET EXPLORER, MOZILLA FIREFOX, OPERA, APPLE SAFARI, GOOGLE CHROME, etc. Further, the software executing on clients902may be downloaded from server computer906to client computers902and installed as a plug-in or ACTIVEX control of a web browser. Accordingly, clients902may utilize ACTIVEX components/component object model (COM) or distributed COM (DCOM) components to provide a user interface on a display of client902. The web server910is typically a program such as MICROSOFT'S INTERNET INFORMATION SERVER.

In one or more embodiments of the invention, server computer906may be advertising servers that perform all of the steps described above. In this regard, an advertising server may provide forecasting to potential purchasers as part of an advertising campaign strategy and/or to determine an advertising campaign strategy before bids are actually placed (e.g. in an advertising auction). Similarly, the various steps may be performed on a local client application that is performing the forecasting. Additional examples of such forecasting include use in the search industry to determine a count of specific words for use in determining user demographics/advertisement targeting, in the agriculture business to analyze geographic areas to forecast environmental conditions during given months/days/time, and/or in the vehicle/industrial design industry to forecast/analyze the effects of environmental conditions such as wind and rain on a vehicular design such as the maximum velocity of an aircraft design while maintaining pressure on elements of the design [e.g., wingtip] below a certain threshold, etc.).

Web server910may host an Active Server Page (ASP) or Internet Server Application Programming Interface (ISAPI) application912, which may be executing scripts. The scripts invoke objects that execute business logic (referred to as business objects). The business objects then manipulate data in database916through a database management system (DBMS)914. Alternatively, database916may be part of, or connected directly to, client902instead of communicating/obtaining the information from database916across network904. When a developer encapsulates the business functionality into objects, the system may be referred to as a component object model (COM) system. Accordingly, the scripts executing on web server910(and/or application912) invoke COM objects that implement the business logic. Further, server906may utilize MICROSOFT'S TRANSACTION SERVER (MTS) to access required data stored in database916via an interface such as ADO (Active Data Objects), OLE DB (Object Linking and Embedding DataBase), or ODBC (Open DataBase Connectivity).

Although the terms “user computer”, “client computer”, and/or “server computer” are referred to herein, it is understood that such computers902and906may be interchangeable and may further include thin client devices with limited or full processing capabilities, portable devices such as cell phones, notebook computers, pocket computers, multi-touch devices, and/or any other devices with suitable processing, communication, and input/output capability.

Of course, those skilled in the art will recognize that any combination of the above components, or any number of different components, peripherals, and other devices, may be used with computers902and906. Embodiments of the invention are implemented as a software application on a client902or server computer906. Further, as described above, the client902or server computer906may comprise a thin client device or a portable device that has a multi-touch-based display.

CONCLUSION

This concludes the description of the preferred embodiment of the invention. The following describes some alternative embodiments for accomplishing the present invention. For example, any type of computer, such as a mainframe, minicomputer, or personal computer, or computer configuration, such as a timesharing mainframe, local area network, or standalone personal computer, could be used with the present invention.

Embodiments of the invention enable forecasting by reducing the complexity of computing a count of events, an accurate average aggregate value for those events, and a breakdown of feature type restrictiveness in criterion. For example, in one or more embodiments, the Pessimistic Optimized Complexity=O (Event Count/64*Criterion Feature Type Count at Partition*ROUNDUP(Count of Partition/CPU Core Count).