公开(公告)号：US07191181B2

公开(公告)日：2007-03-13

申请号：US10873569

申请日：2004-06-22

Applicant: Sarajit Chaudhuri ,  Vivek R. Narasayya ,  Rajeev Motwani ,  Mayur D. Datar

Inventor： Sarajit Chaudhuri ,  Vivek R. Narasayya ,  Rajeev Motwani ,  Mayur D. Datar

IPC: G06F17/30

CPC classification number: G06F17/30489 ,  G06F17/30536 ,  G06F2216/03 ,  Y10S707/957 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99935 ,  Y10S707/99942 ,  Y10S707/99943

Abstract: Aggregation queries are performed by first identifying outlier values, aggregating the outlier values, and sampling the remaining data after pruning the outlier values. The sampled data is extrapolated and added to the aggregated outlier values to provide an estimate for each aggregation query. Outlier values are identified by selecting values outside of a selected sliding window of data having the lowest variance. An index is created for the outlier values. The outlier data is removed from the window of data, and separately aggregated. The remaining data without the outliers is then sampled in one of many known ways to provide a statistically relevant sample that is then aggregated and extrapolated to provide an estimate for the remaining data. This sampled estimate is combined with the outlier aggregate to form an estimate for the entire set of data. Further methods involve the use of weighted sampling and weighted selection of outlier values for low selectivity queries, or queries having group by.

Abstract translation: 通过首先识别异常值，聚合异常值和在修剪异常值之后对剩余数据进行采样来执行聚合查询。 采样数据被外推并加到聚合异常值中，以提供每个聚合查询的估计。 异常值通过选择具有最小方差的数据的所选滑动窗口之外的值来识别。 为异常值创建索引。 离群数据从数据窗口中移除，并单独汇总。 然后以许多已知方式之一对剩余的没有异常值的数据进行采样，以提供统计学相关的样本，然后进行聚合和外推，以提供剩余数据的估计。 该采样估计与异常值聚合组合以形成整套数据的估计。 进一步的方法涉及对低选择性查询或具有分组查询的异常值的加权采样和加权选择。