ZIP: Lazy Imputation during Query Processing

Summary: ZIP makes relational operators imputation-aware at query time, using a cost-based decide-to-impute-or-defer policy while guaranteeing results equivalent to eager (pre-query) imputation. Key techniques: outer-join execution to preserve NULLs and a Bloom-filter index; yields 10–25× speedups over ImputeDB and up to 19,607× vs. offline imputation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hb4b03ef9b9702d70
Venue: VLDB
Year: 2024
Pagerank: 5.1540002e-05
Overall Rank: 9,496 | 36.35%
DOI: 10.14778/3617838.3617841
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Yiming Lin (University of California Irvine)
2. Sharad Mehrotra (University of California Irvine)

BibTeX Citation

@article{lin_vldb24,
        title = {{ZIP: Lazy Imputation during Query Processing}},
        author = {Lin, Yiming and Mehrotra, Sharad},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {1},
        pages = {28--40},
        doi = {10.14778/3617838.3617841},
        url = {https://doi.org/10.14778/3617838.3617841},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,598	Deduplicated Sampling On-Demand	2025	VLDB	5.1376962e-05
11,423	DIM-SUM: Dynamic Imputation for Smart Utility Management	2025	VLDB	4.9605343e-05
11,655	Hardware-Efficient Data Imputation through DBMS Extensibility	2024	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
100	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033951027
277	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002235043
348	Discovering Denial Constraints	2013	VLDB	0.00020216677
745	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014267268
988	Towards Certain Fixes with Editing Rules and Master Data	2010	VLDB	0.00012643318
1,099	KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing	2015	SIGMOD	0.00012008783
2,252	Query Optimization for Dynamic Imputation	2017	VLDB	8.7454369e-05
2,371	Artemis: A System for Analyzing Missing Answers	2009	VLDB	8.5457987e-05
2,429	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.4657925e-05
2,598	Mind the Gap: An Experimental Evaluation of Imputation of Missing Values Techniques in Time Series	2020	VLDB	8.2195844e-05
2,891	Optimal Column Layout for Hybrid Workloads	2019	VLDB	7.887378e-05
3,372	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	7.3488827e-05
3,440	Efficient and Effective Data Imputation with Influence Functions	2022	VLDB	7.2791144e-05
4,149	Missing Value Imputation on Multidimensional Time Series	2021	VLDB	6.7631758e-05
4,978	Adaptive Data Augmentation for Supervised Learning over Missing Data	2021	VLDB	6.3182056e-05
5,206	QuERy: A Framework for Integrating Entity Resolution with Query Processing	2016	VLDB	6.2160113e-05
5,296	Enriching Data Imputation with Extensive Similarity Neighbors	2015	VLDB	6.1777832e-05
6,026	Query-Driven Approach to Entity Resolution	2013	VLDB	5.891678e-05
6,563	ORBITS: Online Recovery of Missing Values in Multiple Time Series Streams	2021	VLDB	5.7285748e-05
9,415	JENNER: Just-in-time Enrichment in Query Processing	2022	VLDB	5.1672232e-05
12,086	LOCATER: Cleaning WiFi Connectivity Datasets for Semantic Localization	2021	VLDB	4.9605343e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,922	Query Processing over Incomplete Autonomous Databases	2007	VLDB
2	11,641	Win-Win: On Simultaneous Clustering and Imputing over Incomplete Data	2024	VLDB
3	11,815	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
4	3,479	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB
5	8,192	Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints	2020	SIGMOD
6	8,806	QPPT: Query Processing on Prefix Trees	2013	CIDR
7	5,296	Enriching Data Imputation with Extensive Similarity Neighbors	2015	VLDB
8	7,606	Data Imputation with Limited Data Redundancy Using Data Lakes	2025	VLDB
9	10,218	In-Database Data Imputation	2024	SIGMOD
10	2,252	Query Optimization for Dynamic Imputation	2017	VLDB