EUVIMEDScopri EUVIMED
Crossref

Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees

Yuxuan Zhu, Tengjun Jin, Chenghao Mo, Daniel Kang

Proceedings of the ACM on Management of Data · 2026-05-18 · 4 (3) · 1-28

DOI: 10.1145/3802004 ↗

At a glance

Journal article in Proceedings of the ACM on Management of Data, published online on 2026-05-18. Written by Yuxuan Zhu and 3 co-authors. 104 references. Funded by: Google.

AbstractDati bibliograficiCiteRelated studies

Abstract (original language)

Analytical join queries over unstructured data are increasingly prevalent in data analytics. Applying machine learning (ML) models to label every pair in the cross product of tables can achieve state-of-the-art accuracy, but the cost of pairwise execution of ML models is prohibitive. Existing algorithms, such as embedding-based blocking and sampling, aim to reduce this cost. However, they either fail to provide statistical guarantees (leading to errors up to 79% higher than expected) or become as inefficient as uniform sampling. We propose blocking-augmented sampling (BaS), which simultaneously achieves statistical guarantees and high efficiency. BaS optimally orchestrates embedding-based blocking and sampling to mitigate their respective limitations. Specifically, BaS allocates data tuples in the cross product into two regimes based on the failure modes of embeddings. In the regime of false negatives, BaS uses sampling to estimate the result. In the regime of false positives, BaS applies embedding-based blocking to improve efficiency. To minimize the estimation error given a budget for ML executions, we design a novel two-stage algorithm that adaptively allocates the budget between blocking and sampling. Theoretically, we prove that BaS asymptotically outperforms or matches standalone sampling. On real-world datasets across different modalities, we show that BaS provides valid confidence intervals and reduces estimation errors by up to 19× compared to state-of-the-art baselines.

Funding

  • Google

Cite

APA

Zhu, Y., Jin, T., Mo, C., & Kang, D. (2026). Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees. Proceedings of the ACM on Management of Data, 4(3), 1-28. https://doi.org/10.1145/3802004

Vancouver

Zhu Y, Jin T, Mo C, Kang D. Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees. Proceedings of the ACM on Management of Data. 2026;4(3):1-28. doi:10.1145/3802004

BibTeX
@article{Zhu2026,
  author = {Zhu, Yuxuan and Jin, Tengjun and Mo, Chenghao and Kang, Daniel},
  title = {Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--28},
  doi = {10.1145/3802004}
}
Start for free →