# Coresets for Relational Data and The Applications

arXiv: https://arxiv.org/abs/2210.04249 · HTML: https://mlsanity.com/paper/2210.04249/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 66 references that are in the map.
- First posted on arXiv 9 Oct 2022.

## Builds on (most cited first, 19 of 19)

- [Selection via Proxy: Efficient Data Selection for Deep Learning](https://mlsanity.com/paper/1906.11829/) (2019)
- [Coresets via Bilevel Optimization for Continual Learning and Streaming](https://mlsanity.com/paper/2006.03875/) (2020)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [varepsilon-Coresets for Clustering (with Outliers) in Doubling Metrics](https://mlsanity.com/paper/1804.02530/) (2018)
- [FAQ: Questions Asked Frequently](https://mlsanity.com/paper/1504.04044/) (2015)
- [Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics](https://mlsanity.com/paper/1812.08664/) (2018)
- [Moment-based Uniform Deviation Bounds for k-means and Friends](https://mlsanity.com/paper/1311.1903/) (2013)
- [Size bounds and query plans for relational joins](https://mlsanity.com/paper/1711.03860/) (2017)
- [Rk-means: Fast Clustering for Relational Data](https://mlsanity.com/paper/1910.04939/) (2019)
- [Relational Algorithms for k-means Clustering](https://mlsanity.com/paper/2008.00358/) (2020)
- [Functional Aggregate Queries with Additive Inequalities](https://mlsanity.com/paper/1812.09526/) (2018)
- [Learning Models over Relational Data: A Brief Tutorial](https://mlsanity.com/paper/1911.06577/) (2019)
- [A Relational Gradient Descent Algorithm For Support Vector Machine Training](https://mlsanity.com/paper/2005.05325/) (2020)
- [Approximate Aggregate Queries Under Additive Inequalities](https://mlsanity.com/paper/2003.10588/) (2020)
- [Efficient Construction of Nonlinear Models over Normalized Data](https://mlsanity.com/paper/2011.11682/) (2020)

## Built on by (most cited first, 1 of 1)

- [Metric k-clustering using only Weak Comparison Oracles](https://mlsanity.com/paper/2601.19333/) (2026)

## Abstract (arXiv)

A coreset is a small set that can approximately preserve the structure of the original input data set. Therefore we can run our algorithm on a coreset so as to reduce the total computational complexity. Conventional coreset techniques assume that the input data set is available to process explicitly. However, this assumption may not hold in real-world scenarios. In this paper, we consider the problem of coresets construction over relational data. Namely, the data is decoupled into several relational tables, and it could be very expensive to directly materialize the data matrix by joining the tables. We propose a novel approach called ``aggregation tree with pseudo-cube'' that can build a coreset from bottom to up. Moreover, our approach can neatly circumvent several troublesome issues of relational learning problems [Khamis et al., PODS 2019]. Under some mild assumptions, we show that our coreset approach can be applied for the machine learning tasks, such as clustering, logistic regression and SVM.