Patent ID: 6842753

Claim:
A method that computes an approximate result to an aggregation query on a relation with at least one attribute comprising: identifying outlier tuples in the relation having an attribute value that meets an outlier criteria that is a variance of the attribute value in each tuple with respect to the other tuples in the relation by: sorting the tuples based on the tuple value for the attribute; determining a minimum number of tuples to be classified as outliers; determining a set of contiguous sorted tuples that includes at least the minimum number of tuples and for which the variance is minimized; and classifying tuples not in the set of contiguous sorted tuples as outliers; executing the query on the identified outlier tuples to obtain an outlier result; estimating a non-outlier contribution of non-outlier tuples to the result of the query; and combining the outlier result and the non-outlier contribution.