Approximate Query Processing Concepts and Techniques

Approximate query processing (AQP) is the best approach for data analysis scenarios where a cost effective solution is required while accuracy is not an important factor. This paper is intended to present the state-of-the-art AQP concepts and techniques, discussing the strength and weak points of each technique, differences between them, and their best implementation. It also includes the most popular data reduction techniques that are used to construct data synopsis for AQP. The paper is organized to address AQP background in first section including historical background, important definitions and motivations. The second section the AQP architecture and process flow are discussed. The third section AQP techniques and data reduction techniques are presented with focus on sampling techniques. Finally, error estimation techniques are explained and how to use approximate answers effectively.