The majority of data reduction techniques for approximate query processing (such as wavelets, histograms, kernels, and so on) are not usually applicable to categorical data. There has been something of a disconnect between research in this area and the reality of database data; much recent research has focused on approximate query processing over ordered or numerical attributes, but arguably the majority of database attributes are categorical: country, state, job_title, color, sex, department, and so on. This paper considers the problem of approximation of aggregate functions over categorical data, or mixed categorical/numerical data. We propose a method based upon random sampling, called Approximate Pre-Aggregation (APA). The biggest drawback of sampling for aggregate function estimating is the sensitivity of sampling to attribute value skew, and APA uses several techniques to overcome this sensitivity. The increase in accuracy using APA compared to "plain vanilla" sampling is dramatic. For SUM and AVG queries, the relative error for random sampling alone is more than 700% greater than for sampling with APA. Even if stratified sampling techniques are used, the error is still between 28% and 175% greater than for APA. Approximate query answering has received much recent research attention from the data management community. The importance of approximation as an area of database research has been greatly enhanced by the emergence of Decision Support Systems (DSS) as a fundamental application area for database technology. Two characteristics specific to such systems make DSS a potential area where approximation methods can be used. •First, DSS archive many gigabytes or terabytes of data (often on the order of billions of records), and so exact query answers can be very expensive. •Second, queries over DSS are usually aggregate queries, and thus lend themselves to numerical approximation. A great amount of the work in this area has centered around the approximate evaluation of aggregate queries of the form: SELECT AGG_FUNC (TBL.MEAS_ATT) FROM THE_TABLE TBL WHERE TBL.SEL_ATT_1 BETWEEN(N1_LOW AND N1_HI) AND TBL.SEL_ATT_2 BETWEEN(N2_LOW AND N2_HI) AND ... In most work, it has been assumed that the data model that is queried over is something similar to a multidimensional data cube. In this model, there are D selection attributes, any of which can appear in the WHERE clause of the query. These attributes partition the data space into a D-dimensional cube. In addition to the selection attributes, there is a set of measure attributes to which different aggregate functions may be applied in the SELECT clause of the query. Each tuple in the database is mapped to a cell in the data cube based on the values of that tuple's selection attributes, and the values of that tuple's different measure attributes are written into the cell. Queries then compute aggregate functions (such as SUM, AVG, COUNT, etc.) over different lowdimensional projections of the measure attributes which are stored in the cube. A key assumption in much of the work in this area is that the attributes appearing in the WHERE clause either are numerical or have been discretized into a set of buckets which have a meaningful ordering. In this case, one can choose from many proposed approximation methodologies. Examples are multidimensional histograms [18] , wavelets [20] , and kernel estimators [13] , among others. One problem with these approximation techniques is that data often have attributes which are truly categorical. An example of this is the attribute country (with possible values United States, Canada, France, etc.). These values are not numerical, and it is difficult to impose an ordering on them that allows for a meaningful decomposition of the data In this case, we may have increased our data dimensionality from three to 500 attributes, which is likely far more than any of the mentioned approximation methods can handle. According to Gunopulos et al., it is doubtful that any of these methods can consistently work in more than ten dimensions [13] .
Approximate Pre-Aggregation REF (APA) uses a random sample combined with a small set of statistics about the data to increase the accuracy.
Robust Estimation With Sampling and Approximate Pre-Aggregation
VLDB
Computer Science