Approximate Range Queries by Histograms in OLAP

Abstract

Online analytical processing applications typically analyze a large amount of data by means of repetitive queries involving aggregate measures on such data. In fast OLAP applications, it is often advantageous to provide approximate answers to queries in order to achieve very high performances. A way to obtain this goal is by submitting queries on compressed data in place of the original ones. Histograms, initially introduced in the field of query optimization, represent one of the most important techniques used in the context of OLAP for producing approximate query answers.