Guaranteeing an Exact Error Bound for Bounded Approximate Query Processing
Tianjia Ni, Kento Sugiura, Yoshiharu Ishikawa, Kejing Lu · Journal of Information Processing · 2024
In recent years, efficient query processing in databases has become more crucial with the sophistication of analysis requirements. Approximate query processing (AQP) is one of the approaches to dealing with database queries on big data. In this research, we focus on synopsis construction on a relational database and the query technology based on it, called bounded approximate query processing (BAQ). This paper points out the limitations of existing research BAQ and solves them by the proposed BAQ±. BAQ± is capable of dealing datasets with a broader range while ensuring the exact error bound. Furthermore, compared to the original BAQ, BAQ± generates a more compact synopsis with various data distributions. We introduce an innovative bucketing approach to construct smaller synopses while keeping the same properties in BAQ. Additionally, we propose novel rewrite methods for answering online queries by deriving error guarantee conditions. We provide extensive experiment assessments using different distribution datasets. Our BAQ± provides a smaller synopsis at 64% the size of BAQ and efficiently executes online queries within the exact error bound.