Lune

ICDE2020Top-tier venue

Approximate Query Processing for Data Exploration using Deep Generative Models

Saravanan Thirumuruganathan, Shohedul Hasan, Nick Koudas, Gautam Das

Abstract

Data is generated at an unprecedented rate surpassing our ability to analyze them. The database community has pioneered many novel techniques for Approximate Query Processing (AQP) that could give approximate results in a fraction of time needed for computing exact results. In this work, we explore the usage of deep learning (DL) for answering aggregate queries specifically for interactive applications such as data exploration and visualization. We use deep generative models, an unsupervised learning based approach, to learn the data distribution faithfully such that aggregate queries could be answered approximately by generating samples from the learned model. The model is often compact - few hundred KBs - so that arbitrary AQP queries could be answered on the client side without contacting the database server. Our other contributions include identifying model bias and minimizing it through a rejection sampling based approach and an algorithm to build model ensembles for AQP for improved accuracy. Our extensive experiments show that our proposed approach can provide answers with high accuracy and low latency.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

18 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation cites Are We Ready For Learned Cardinality Estimation?
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers18

  1. Are We Ready For Learned Cardinality Estimation?Xiaoying Wang, Changbo Qu, Weiyuan Wu, Jiannan Wang et al.VLDB 2021 · 156 citations
  2. FLAT: Fast, Lightweight and Accurate Method for Cardinality EstimationRong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng et al.VLDB 2021 · 120 citations
  3. A Learned Sketch for Subgraph CountingKangfei Zhao, Jeffrey Xu Yu, Hao Zhang, Qiyan Li et al.SIGMOD 2021 · 43 citations
  4. Accelerating Approximate Aggregation Queries with Expensive PredicatesDaniel Kang, John Guibas, Peter Bailis, Tatsunori Hashimoto et al.VLDB 2021 · 34 citations
  5. MaGNET: Uniform Sampling from Deep Generative Network Manifolds Without RetrainingAhmed Imtiaz Humayun, Randall Balestriero, Richard G. BaraniukICLR 2022 · 34 citations

Builds on1

  1. IDEBench: A Benchmark for Interactive Data ExplorationPhilipp Eichmann, Emanuel Zgraggen, Carsten Binnig, Tim KraskaSIGMOD 2020 · 57 citations

Related papers

  1. Conditional Generative Model Based Predicate-Aware Query ApproximationNikhil Sheoran, Subrata Mitra, Vibhor Porwal, Siddharth Ghetia et al.AAAI 2022 · 14 citations
  2. FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product NetworkHanbing Zhang, Yinan Jing, Zhenying He, Kai Zhang et al.SIGMOD 2025
  3. ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data GenerationRong Gu, Han Li, Haipeng Dai, Wenjie Huang et al.VLDB 2023 · 9 citations
  4. Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian ProcessKangfei Zhao, Jeffrey Xu Yu, Zongyan He, Rui Li et al.SIGMOD 2022 · 28 citations
  5. LAQy: Efficient and Reusable Query Approximations via Lazy SamplingViktor Sanca, Periklis Chrysogelos, Anastasia AilamakiSIGMOD 2023 · 5 citations
Dusk over the sea between two cliffs drawn in fine vertical lines