A Quick Introduction to Approximate Query Processing课件.ppt

Decision Support Systems Data Warehousing: Consolidate data from many sources in one large repository. Loading, periodic synchronization of replicas. Semantic integration. OLAP: Complex SQL queries and views. Queries based on spreadsheet-style operations and “multidimensional” view of data. Interactive and “online” queries. Data Mining: Exploratory search for interesting trends and anomalies. (Another lecture!) Introduction Motivation Exact answers NOT always required DSS applications usually exploratory: early feedback to help identify “interesting” regions Aggregate queries: precision to “last decimal” not needed e.g., “What percentage of the US sales are in NJ?” (display as bar graph) Preview answers while waiting. Trial queries Base data can be remote or unavailable: approximate processing using locally-cached data synopses is the only option SQL Query Exact Answer DecisionSupport Systems(DSS) Long Response Times! Fast Approximate Answers Primarily for Aggregate Queries Goal is to quickly report the leading digits of answers In seconds instead of minutes or hours Most useful if can provide error guarantees E.g., Average salary $59,000 +/- $500 (with 95% confidence) in 10 seconds vs. $59,152.25 in 10 minutes Achieved by answering the query based on samples or other synopses of the data Speed-up obtained because synopses are orders of magnitude smaller than the original data Approximate Query Answering Basic Approach 1: Online Query Processing e.g., Control Project [HHW97, HH99, HAR00] Sampling at query time Answers continually improve, under user control Approximate Query Answering Basic Approach 2: Precomputed Synopses Construct store synopses prior to query time At query time, use synopses to answer the query Like estimation in query optimizers, but reported to the user (need higher accuracy) more general queries Need to maintain synopses up-to-date Most work in