Approximate Query Processing Gautam Das Return to Tutorials Abstract In recent years, we have been getting inundated with data - advances in data collection technologies and increasingly affordable secondary storage have led to a proliferation of very large databases. These arise in diverse applications, ranging from commercial data warehouses such as sales data of large retailers, scientific databases such as satellite imagery data and biological genome databases, data collected from sensor networks, user click-thru data collected at large websites, and other domains. However, while the collection of massive data sets has become relatively straightforward, effective data analysis has proven more difficult to achieve. Most analysis queries, by their nature, require aggregation or summarization of large portions of the data, which means that processing such queries requires prohibitively expensive running times. Fortunately, while keeping query response times short is very important in many data mining and data analysis applications, exactness in query results is frequently less important. In many cases, "ballpark estimates" are adequate to provide the desired insights about the data. The acceptability of inexact query answers coupled with the necessity for fast query response times has led researchers to investigate approximate query processing techniques (AQP). This tutorial will cover several of the approximate query processing techniques have been proposed and investigated recently. Several widely studied methods will be covered, especially sampling-based methods such as online aggregation, pre-computed uniform samples, weighted samples, outlier indexing, stratified samples, dynamic sample selection, and so on, as well as non-sampling based methods such as histograms, wavelets, and other density estimation models. The difficulties of approximate query processing for queries involving joins will be discussed, as well as solutions such as join synopses for the special case of foreign-key joins. Finally the tutorial will also touch upon emerging research directions of AQP, such as beyond aggregation queries, AQP in data streams, sensor networks, distributed P2P systems, XML databases, as well as query processing over imprecise data. We emphasize that this tutorial is not meant to be a comprehensive survey of all aspects of AQP - rather the focus will be on the most fundamental problems that arise in this tantalizing area of research, and the promising approaches that have been attempted to solve these problems. More generally, this tutorial will serve to educate database researchers in important data modeling and approximation techniques that are expected to find increasing applications in database/data mining research and applications. ©2006 Association for Computing Machinery