Abstract:
The invention introduces a mechanism for analyzing large amounts of data. The end-user selects the various filter expression types and any required parameters used to condense the data, and this allows interactive selection of the most interesting ones as well as the ability to vary parameters for those filter expressions requiring them. These selected filter expressions are used to produce filtered views of the data in the cross-tabulations, so that the end-user gains a better grasp of the significant attributes of the data by having less important data either omitted, or aggregated into arbitrary groups. Because all of the permitted filter expressions are pre-computed there are significant improvements in usability and effectiveness. Further, since the pre-computation of these quite complex functions is performed concurrently there is potential for significant savings in processing resources.

Description:
TECHNICAL FIELD 
     The present invention relates to the field of computing. More particularly, it relates to a method for performing analysis of data. 
     BACKGROUND OF THE INVENTION 
     The field of database management systems is well known and understood. The increasing size and usage of databases has lead to new problems. In possibly large, possibly sparse cross-tabulations, commonly referred to as cross-tabs, computed from data contained within a database, it is always a challenge to present the end-user with that subset of data with the highest semantic content obtainable. This is done by omitting or consolidating redundant or unimportant information by deleting or aggregating specified rows and/or columns in the cross-tabulation so that only the more useful data is shown. 
     In the past, various techniques have been used to reduce the amount of information presented to the end-user. These techniques include simple ploys such as removing complete rows or columns of data containing only zero data or no data at all. Other more complex techniques have also been used to aggregate data so that the end-user is not overwhelmed by the sheer quantity of values, many of them sufficiently small that they can be discounted when assessing the overall picture. An example of this approach is the use of the so-called “Pareto rule”, which, in summary, postulates that in many sets of data, a large proportion of the data values are small and uninteresting, and thus may with advantage be grouped or ‘rolled up’ into a pseudo-category named, typically, “Other”. (This ‘rule’ is named for Vilfredo Pareto, an Italian economist and sociologist of the early 1900s. It is based on the unequal distribution of things in the universe, and paraphrased states that “80% of wealth is in the hands of 20% of the population”). 
     Other similar functions, herein referred to as filter expressions, have been adopted to assist the end-user in interpreting data. Each such function generally requires significant ad hoc development, and frequently not all of them have been available to the end-users of any one system. Because of the ad hoc nature of previous implementations, there have been few opportunities to take advantage of the processing savings available if several functions are evaluated at once. 
     Typical end-users of large databases are not always familiar with or even aware of, these functions, and in consequence are not able to manipulate the data effectively. 
     What is needed is an improvement in the usability of databases and in efficiency of processing the data. 
     SUMMARY OF THE INVENTION 
     According to the invention, there is provided a computer-based method of evaluating data by selecting the highest semantic content of a table of data, comprising the steps of: constructing a cross-tabulation of data from one or more databases; ascertaining filter expressions to be applied to said cross-tabulation of data; evaluating said filter expressions using said cross-tabulation of data; and storing the results of said evaluation in a status table. In this context, semantic content is defined as that the informational content that is most meaningful or significant within the table, particularly for the current user. 
     The present invention introduces a mechanism to overcome the limitations of the existing methods for analyzing large amounts of data, which improves their usability as well as efficiency of processing. Examination of the problem led to the realization that there is indeed a relatively small number of possible filter expressions, or rather, filter expression types, which are useful in the context of manipulating cross-tabulations, particularly, but by no means limited to, large sparse ones. Typically, the end-user is presented with a list from which to select the various filter expression types used to condense the data, and this allows interactive selection of the most interesting ones. 
     The invention is a computer-based method of evaluating data by selecting the highest semantic content of a table of data. This is achieved, in one embodiment, by constructing a cross-tabulation of data from one or more databases, then ascertaining which filter expressions are to be applied to the data. The results of the evaluations of the filtering expressions using the data are then stored in a status table for later use. 
     In addition to permitting the end-user to select the filter expressions to be applied to the cross-tabulations, the invention allows the end-user to choose parameters or arguments for those filter expressions requiring them. All of the selected filter expressions can then be used as ‘filters’ of the data in the cross-tabulations, so that the end-user gains a better grasp of the significant attributes of the data by having less important data either omitted, or aggregated into arbitrary groups. 
     An additional benefit of the invention is that faster presentation (or evaluation and display) of the results occurs because all of the permitted filter expressions can be pre-computed. This faster presentation leads to significant improvements in usability and effectiveness. 
     It can also be seen that in geographically dispersed systems, any reduction of the quantity of data presented to the end-user provides the additional benefit of lessening the system resources required to transfer that data between locations. 
     In some instances, the invention involves the pre computation of quite complex functions. Although this can be expensive in processing time, the improvements in end-user results and presentation speed, as well as the resultant savings in data transfer volumes, often outweigh this cost. Pre-computation is especially beneficial when it is anticipated that the table will be used multiple times, which is more likely where the end-user is analyzing the data interactively. Further, when performed concurrently, the computation cost for several parameters used in selected functions does not increase linearly with the number of parameters, but rather each is a relatively small incremental cost. Overall, concurrent pre-computing of multiple filters has the potential for significant savings in processing resources. 
     Although the primary benefit of the invention is to improve computational efficiency and provide enhanced end-user functionality, there are further benefits for client/server and similar network-based environments. The invention permits, indeed encourages, the end-user to make decisions which ultimately reduce the amount of data required to be transmitted across the network. 
     The environment in which the present invention is used is that of a general purpose computing facility connected with a number of databases. It is typically used by a number of simultaneous end-users, although that aspect is not relevant to the operation of the invention. The computing facility may comprise a number of interconnected computers, and the databases and users may be co-located or remotely located. Interconnection of these elements, whether or not co-located, might be over a network such as the Internet. 
     Other aspects of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows the computing environment typically used in implementing the preferred embodiment of the invention. 
     FIGS. 2,  2   a ,  2   b  and  2   c  depict a flowchart of the operation of a preferred embodiment of the invention, from the end-user&#39;s perspective, 
     FIG. 3 shows, in a somewhat simplified manner, the various tables required to implement a preferred embodiment of the invention. 
     FIG. 4 shows how the filter status data can be used to produce many filtered views from a base cross-tabulation for which multiple filters have been evaluated. 
    
    
     DESCRIPTION OF PREFERRED EMBODIMENTS 
     Referring to FIG. 1, the invention is implemented as software running on a general purpose computing facility  10  which has access to a number of database repositories  11 , capable of performing SQL or equivalent functions, and is typically used by a number of end-users  12 . 
     Filter Expressions 
     A filter expression is any logical predicate with a single unbound variable, which is evaluated by taking the value of a cell within a cross-tabulation as the value of the unbound variable. The preferred embodiment is assumed to contain an expression evaluation facility capable of evaluating arbitrary logical predicates. 
     The simplest filter expression is an arbitrary logical predicate in the form of a function with a single real valued argument (the cell value): e.g. V ij &gt;1.23, where V ij  is the value in the cell at the intersection of the i&#39;th row and the j&#39;th column. The functions may be arbitrarily complex and may involve arithmetic functions such as ABS, MOD or SQUARE_ROOT; comparison operators such as LESS THAN (&lt;) or NOT EQUALS (≠) as well as logical operators such as AND or NOT. The cell value V ij , which is the argument to the function, may appear arbitrarily many times within the function. A typical filter expression of this type would determine whether each of the values fell within a specified range. This is expressed as: 
     
       
         ( V   ij &gt;1.23&amp; V   ij &lt;4.56). 
       
     
     A richer repertoire of filter expressions may be obtained if the expressions may contain functions which take as an argument the entire set of values within the cross-tabulation. For example, the mean (average) value of the cells within a cross-tabulation may be represented as ƒ(V) where ƒ represents the particular function and V represents the full set of values within the entire cross-tabulation. An arbitrary predicate thus has the general form, ƒ(V ij , ƒ 1 , ƒ 2  . . . ƒ n ). A typical filter expression of this type would test whether the value in a cell is 2 standard deviations above the mean, This is expressed as: 
     
       
         (( V   ij −MEAN(V))/(2*SQUARE_ROOT(VARIANCE(V))&gt;2). 
       
     
     Many of the interesting functions of the form ƒ(V) are made more useful if they may be parameterized. For example, the percentile function which finds the value which is larger (or smaller) than a specified percentage of the values of set is more useful if the percentage can be defined. Thus a useful form of the percentile function takes two arguments: a set containing the values in the cross tabulation and a number between 1 and 99 indicating the percentage. The full form is thus ƒ(V, c), where c is the control value which controls the evaluation of the function. A typical filter expression of this type would determine whether each of the values fell between the first and third quartiles for the values in the table. This is expressed as: 
     
       
         ( V   ij &gt;BOTTOM_PERCENTILE( V,  25)&amp; V   ij &lt;TOP_PERCENTILE( V,  25)). 
       
     
     The result of evaluating a function of the form or ƒ(V) or ƒ(V, c) is termed a run time parameter of the filter expression. 
     Selection of Parameter Types 
     Unlike the basic logical predicate in the form of a function with a single real valued argument, the filter expression containing functions evaluated over the set V cannot be simply expressed because the definition of bow to compute the functions ƒ(V) or ƒ(V, c) can be quite complex. A practical embodiment must constrain the ƒ(V) or ƒ(V, c) to a predefined set. 
     The types of run time parameter values which can be defined for inclusion within simple logic predicates are without theoretical limit but a practical set would be based on: a) counts; b) sums; c) extreme values; d) central and non-central moment statistics, including the mean and standard deviation; e) order statistics, including percentiles, deciles, quartiles and the median; f) values or cumulative sums at specified ordinal positions. 
     Twelve functions over the set of values in the cross-tabulation which have been chosen as being these with the highest utility for the types of data under consideration are defined for use here. Six of these expressions are simple (or univariate) run time parameters —ƒ(V)— and a further six are run time parameters with control values provided by the end-user —ƒ(V, p). They appear in Table 1. 
     
       
         
               
               
             
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 Expression Type 
                 Examples 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 Simple statistical expressions 
                 Count 
                 Standard Deviation 
               
               
                   
                 Sum 
                 Maximum 
               
               
                   
                 Mean 
                 Minimum 
               
               
                 Statistical expressions 
                 Top Count n 
                 Bottom Percentile n 
               
               
                 with control values 
                 Bottom Count n 
                 Top Sum n 
               
               
                   
                 Top Percentile n 
                 Bottom Sum n 
               
               
                   
               
             
          
         
       
     
     All of these filter expressions are well understood in the art. The following brief definitions are included for reference. 
     Top Count n: The n&#39;th largest value in the set V. 
     Bottom Count n: The n&#39;th smallest value in the set V. 
     Top Percentile n: In a size ordered set of values, the smallest value in the set of maximal values which constitute n % of the set V. 
     Bottom Percentile n: In a size ordered set of values, the largest value in the set of minimal values which constitutes n % of the sum for the set V. 
     Top Sum n: The value in a size ordered set of values which is smaller than the set of maximal values which sum to n % of the sum for the set V. 
     Bottom Sum n: The value in a size ordered set of values which is larger than the set of minimal values which sum to n % of the sum for the set V. 
     It will be obvious to an ordinarily skilled practitioner of the art that more filter expressions, both simple (e.g. mode) and with control values (e.g. explicit deciles), could be added to the list in Table 1, but they would have little value in most domains. However, their inclusion or exclusion does not change the nature of the invention. 
     OPERATION OF THE PREFERRED EMBODIMENT 
     The flowchart FIG.  2  and the FIGS. 3 and 4 illustrate a preferred embodiment of the present invention in which an end-user interacts with the computing system and data. Referring to FIGS. 2 and 3, in the first step to be considered  105  a cross-tabulation of the data is constructed. At step  100  the end user may elect to ascertain and construct filter expressions from primitives with the help of an expression editor and, where a parameter is required for the filter expression, may elect to provide that information as well. In the next step  110 , the end user constructs expressions from primitives with the help of an expression editor and, where a parameter is required for the filter expression, provides that information. Subsequently, the end user  120  selects the data to be examined, as well as the preferred filter expressions to be used in manipulating the data, which are stored in  210 . The data are retrieved  130  from the appropriate database repository and stored in the cross-tabulation  200 . The computing system examines the filter expressions  140  selected by the end-user  120  and, if required, the parametervalues are evaluated and stored  150  in the Run Time Parameter table  230  as previously described. In turn, the selected filter expressions are then evaluated  160  for each data value and the results are stored in the appropriate Expression Status table  220 . In turn the expression status values for each row and column are computed and stored  150  in the appropriate filter expression tables  210 . The filter set is displayed  170  to the end-user to permit selection of the desired view. Referring now also to FIG. 4, if the end-user makes a selection  180 , the computing system filters the Data Table  300  according to the Expression status information for the rows  310 , and the Expression status information for the columns  312  and presents  190  a filtered cross-tabulation  320  to the end-user. Finally, if no further filtered views are requested, the process terminates  199 . 
     EXAMPLE USING THE INVENTION 
     The utility of the invention is further explained by way of the following example. 
     Consider a situation in which a manager wishes to produce a list of those salespeople who have consistently had gross sales above the mean for every quarter of the year (and give them bonuses!), and also another list of those salespeople who have NEVER been in the top 25% of gross sales for any quarter during the year (and replace them!). 
     First, a temporary (or ephemeral) data table known as a ‘cross-tabulation’ is created (from information stored in a database repository) in which the ‘rows’ represent individual salespeople, and ‘columns’ represent calendar quarters, values in the table being the gross sales by salesperson/quarter. 
     For both the ‘rows’ and ‘columns’ there is also created a set of ‘filter expressions’, selected or determined by the manager from a list of possible filter expressions. Multiple filter expressions can be requested simultaneously by the manager, if desired. The set of filter expressions may be the same for the rows and columns but need not be. 
     The set of rows in the cross-tabulation and the set of filter expressions for the rows imply a table of ‘expression status values’ which has as many rows as the number of rows in the cross-tabulation and as many columns as the number of filter expressions associated with the rows. Each of these ‘expression status values’, once computed, has the value ‘True’ or ‘False’: ‘False’ meaning that there is at least one cell value in the row for which the filter expression evaluates to False; ‘True’ meaning that for all cell values in the row, the filter expression evaluates to True. There is likewise a set of filter expressions and an expression status value table for columns to which the foregoing applies mutatis mutandis. 
     In this example, the manager chose two filter expressions, one based on Mean and the other on Top Percentile (25). The system can construct on demand a display table consisting of either: 
     Salespeople whose sales in the previous four quarters are above the Mean, or 
     Salespeople who have not been in the Top 25 Percentile in any of the preceding four quarters. 
     The system, when requested to display the data as requested by the manager then creates another (viral) table comprising only those rows and columns for which the selected ‘expression status values’ are ‘True’. This can be achieved by examining the ‘expression status values’ for appropriate rows (i.e., for each Salesperson) without incurring the significant cost of processing and other resources in recomputing these status values each time. 
     The manager can apply, or re-apply, multiple filters with a low computational (and time) cost because the time-consuming operations of data retrieval and selector calculation have already been performed. 
     The invention can be implemented in digital electronic circuitry or in computer hardware, firmware, software or in combinations thereof. Apparatus of the present invention can be implemented in a computer program product tangibly embodied in a machine-readable storage device for execution by a programmable processor. The method of the present invention can be performed by a programmable processor executing a program of instructions to perform the functions of the invention by operating on input data and generating output. 
     Numerous modifications, variations and adaptations may be made to the particular embodiments of the invention described above without departing from the scope of the invention, which is defined in the claims.