Patent ID: 7493316

Claim:
A computer-implemented method of using an outlier index to approximate results for a plurality of different ad-hoc aggregate queries, the method comprising: selecting outlier tuples in a computer-stored dataset and creating the outlier index, the outlier index comprising an index of the outlier tuples; selecting a sample of tuples from the dataset and using the outlier index to remove from the sample any outlier tuples, which produces a sample of non-outlier tuples of the dataset; for one of the ad-hoc aggregate queries of the plurality of different ad-hoc aggregate queries, computing an estimated result of applying one of the ad-hoc aggregate queries to all of the dataset, the estimated result being computed by: producing an outlier aggregate by applying the ad-hoc aggregate query to the outlier tuples which are accessed via the outlier index, the outlier aggregate comprising an aggregation, according to the ad-hoc aggregate query, of outlier tuples that satisfy the ad-hoc aggregate query; producing a non-outlier aggregate by applying the ad-hoc aggregate query to the sample of non-outlier tuples, the non-outlier aggregate comprising an aggregation, according to the ad-hoc aggregate query, of non-outlier tuples that satisfy the aggregate query; and computing and storing the estimated result by combining, according to the ad-hoc aggregate query, the outlier aggregate and the non-outlier aggregate, the estimated result comprising a combination of the outlier aggregate and the non-outlier aggregate.