Error Assessment for Multi-Join AQP using Bootstrap Sampling

Approximate query processing (AQP) is a computing efficient scheme to provide fast and accurate estimations for big data queries. However, assessing the error of an AQP estimation remains an open challenge for high-dimensional multi-relation data. Existing research often focuses on the online AQP methods which heavily rely on expensive auxil- iary data structures. The contribution of this research is three-fold. First, we develop a new framework employing a non-parametric statistic method, namely bootstrap sampling, towards error assessment for multi-join AQP query estimation. Second, we extend the cur- rent AQP schemes from providing point estimations to range estimations by offering the confidence intervals of a query estimation. Third, a prototype system is implemented to benchmark the proposed framework. The experimental results demonstrate the prototype system generates accurate confidence intervals for various join query estimations.