论文：FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network
会议：SIGMOD 2025
作者：Hanbing Zhang, Yinan Jing, Zhenying He, Kai Zhang, X. Sean Wang
简介：对于交互式数据探索来说，近似查询处理（Approximate Query Processing, AQP）是一种有效的方法，它通过损失一部分查询准确性来换取查询响应速度的提高，能够满足交互式数据探索对低查询延迟的需求。为了减少查询延迟，现有的近似查询处理方法使用样本或模型而不是底层数据来回答查询。然而，这些方法很难同时在查询准确性和查询延迟方面取得令人满意的结果。对于基于样本的方法，这是因为需要的查询结果越准确，所需的样本就越多，处理所需的时间成本就越高。基于模型的方法虽然查询延迟较低，但由于现有模型无法准确捕捉复杂的数据分布，因此无法返回高精度的近似结果。本文提出了一种快速准确的近似查询处理FAAQP。在FAAQP中，我们提出了一种新颖的无监督模型：位图增强的和积网络（bitmap-augmented sum-product network, BSPN），它结合了和积网络与位图的优点，能更准确地捕捉数据分布特征。同时，我们提出了一种预算感知的BSPN构建方法，该方法能在给定存储预算的情况下构建查询准确率最高的BSPN模型。此外，为了降低FAAQP的查询延迟，我们提出了一种位图合并策略，在查询准确性和查询延迟之间进一步做出权衡。在多个真实世界和合成数据集上的实验结果表明，FAAQP优于最先进的近似查询处理方法，在保持低查询延迟的情况下，查询准确率获得了显著提高。
