Coresets for Relational Data and The Applications
This addresses the challenge of efficient machine learning on relational databases for data scientists, though it is incremental as it extends coreset techniques to a new data format.
The paper tackles the problem of constructing coresets for relational data, where data is stored in separate tables and materializing it is expensive, by proposing an aggregation tree with pseudo-cube method that reduces computational complexity and applies to tasks like clustering, logistic regression, and SVM.
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.