PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression

Abstract

Exponential growth in data collection is creating significant challenges for data storage and analytics latency.Approximate Query Processing (AQP) has long been touted as a solution for accelerating analytics on large datasets, however, there is still room for improvement across all key performance criteria. In this paper, we propose a novel histogram-based data synopsis called PairwiseHist that uses recursive hypothesis testing to ensure accurate histograms and can be built on top of data compressed using Generalized Deduplication (GD). We thus show that GD data compression can contribute to AQP. Compared to state-of-the-art AQP approaches, PairwiseHist achieves better performance across all key metrics, including 2.6$\times$ higher accuracy, 3.5$\times$ lower latency, 24$\times$ smaller synopses and 1.5--4$\times$ faster construction time.

References in corpus (4)

• Online Decorrelation of Humidity and Temperature in Chemical Sensors for Continuous Monitoring
• Hermes: Enabling Energy-efficient IoT Networks with Generalized Deduplication
• Online Aggregation based Approximate Query Processing: A Literature Survey
• An Adaptive Column Compression Family for Self-Driving Databases