Coresets for Relational Data and The Applications
Authors: Jiaxiang Chen
Qingyuan Yang
Ruomin Huang
Hu Ding
Venue: NeurIPS 2022 Accept (2022)
Keywords: coreset
relational data
optimization

Abstract: 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.

Coresets for Relational Data and The Applications
Jiaxiang Chen'
Qingyuan Yang²
Ruomin Huang'
Hu Ding"?
Sccooo of Data Science
School of Computer Science and Technology
University of Science and Technology of China
{czar, yangqingyuan, hrm}@mail www.uutt.... edu. cn, hww.hhudnuut.eeeeeee.o wew.euuutcceu........
Abstract
A coreset is 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 available to process explicitly. However, this assumption may not hold in real-world scenarios. In this paper, consider the problem coresets construction over relational data. Namely, the data 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 with pseudo-cube" that build coreset from bottom up. Moreover, our approach can neatly circumvent several troublesome issues of relational learning problems [Khamis al., PODS 2019]. Under mild assumptions, show that our coresct approach can be applied for the machine learning tasks, such as clustering, logistic regression and SVM
Introduction
As the rapid development of information technologies, we are often confronted with large-scale data in many practical scenarios. To reduce the computational complexity, number of data summarization techniques have been proposed 46) Coreset is a well-known sampling technique for compressing large-scale data sets 4 27.
Roughly speaking, for given large data set P, the coreset approach is to construct a new (weighted) set P that approximately preserves the structure of P, and meanwhile P rather than
the size |P| is much smaller than Pl. Therefore, if we run existing algorithm P. the runtime can be significantly reduced and the computational quality (e.g., the optimization objectives for the machine learning tasks [53)) can be approximately guaranteed. In the past decades, the coreset techniques have been successfully applied for solving many optimization problems, such Gaussian mixture models [39] and
k-means clustering 27 20
logistic regression 33 44).
continual learning
Usually we assume that the input data is stored in matrix such that the coreset algorithm can easily access the whole data. But this assumption may not hold in real-world scenarios. For example, according to the Kaggle 2017 "State of Data Science Survey", 65.5% of the data sets relational data. Namely, the data is decoupled into several relational tables, and we cannot obtain the data matrix (which is also called the "design matrix") unless joining all the tables. Relational database has very large and fast growing market this big data era. It is expected to reach USD 122.38 billion by 2027 (48. Relational database has several favorable properties (54), e.g., the decoupled relational data can save large amount of space, and it is friendly to several common statistical queries such as the aggregate functions COUNT, SUM and AVG in SQL. In recent years, the study
"Corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

"in-database learning" has gained a significant amount of attention in the areas of machine learning
and data management 45
37
However, constructing a coreset for relational database is much more challenging. Suppose there are relational tables and the size of the largest table is N. Let be the number of the tuples obtained by joining all the tables, and then n. can be as large as ONN)) ) 7 (we illustrate an instance of joining two tables in Table [.. Obviously it will take extremely large time and space complexities to join all the tables and train a model on such scale of data. To remedy this issue, a straightforward idea is trying to complete the computing task without explicitly constructing the design matrix. Unfortunately, even for some very simple computational tasks, their implementations on relational data can be NP-hard.
To see why these implementations are so hard, we can consider the following simple clustering assignment task (which is often used building block for coresets construction (27 20]): suppose the cluster centers have already been given, and we want to determine the size of each cluster.
Note that if we have the design matrix, this task trivial (just assign each point its nearest center, and then calculate the cluster sizes based on the assignment). However, if the data is decoupled into several relational tables, the problem of computing the assignment can be quite complicated. Khamis et al. (36] recently defined the problem of answering Functional Aggregate Queries (FAQ) in which some of the input factors are defined by a collection of Additive Inequalitie between variables (denote by FAQ-AI(m), where m is the number of additive inequalities). The problem of computing the clustering assignment can be formulated as an instance of FAQ-AI(k: - 1) (to determine the cluster membership for one point (tuple), we need to certify that its distance to its own cluster center is lower than the distances to the other k centers). Recently, Khamis et al. ( showed that evaluating even a FAQ-AI(1) instance is #P-hard, and approximating (AQ-AT(m)) instance within any finite factor is NP-hard for any m > 1. Moseley et al. 42] also showed that even approximating the clustering assignment to any factor is NP-hard for k 2 3. An intuitive understanding is that the query satisfying those inequalities require to access the information of each tuple on all the dimensions, where it is almost equivalent to constructing the entire design matrix.
1.1 Our Contributions
We consider Empirical Risk Minimization (ERM) problems in machine learning 56 Let Id be the data space. The training set P = {P1. P2. PP C Rd. But we assume that this set P is not explicitly given, where it is decoupled into 8 relational tables (the formal definitions are shown in Section 2). The goal is to learn the hypothesis 0 (from the hypothesis space HiI) so as minimize the empirical risk
- Σ ((0.p)) n2
F(0)
where /(s,-) is the non-negative real-valued loss function.
Several coresets techniques on relational data have been studied very recently. Samadian et al. [49 showed that the simple uniform sampling yields a coreset for regularized loss minimization problems (note the uniform sampling can be efficiently implemented for relational database (59)). Their sample size is θ (nt dim), where x E (0, 1) (usually λ is set to be 1/2 in practice) and dim is the VC dimension of loss function (usually it is O(d)) Thus the size can be θ (Vn- d). which is too large especially for high dimensional data. Curtin et al. [22] constructed a coreset for k-means clustering by building weighted grid among the input s tables: the coreset yields 9-approximation for the clustering objective. Independently, Ding et al. [24] also applied the "grid" idea to achieve a
(9 + >)approximation for k-means clustering with distributed dimensions (attributes). The major drawback of this "grid" idea is that the resulting coreset size can be as large as A which is exponential in the number of tables s. Moseley et al. 42 recently proposed coreset for k-means clustering on relational data by using the k-means++ initialization method [6]. however, their approximation ratio too high (> 400) for real-world applications. Moreover, the coresets techniques proposed in (22) 224 [4] can only handle k-means clustering, and it is unclear that whether they can be extended for other machine learning problems the form of
2 'Each additive inequality defines a constraint for the query: for example, in SVM, the "positive" class is detined by the inequality w)) > O, where w the normal vector of the separating hyperplane.

---

In this paper, we aim to develop an efficient and general coreset construction method for optimizing ① on relational data. First, we observe that real- world data sets often have low intrinsic dimensions (e.g, nearby a low-dimensional manifold) 10] Our coreset approach is inspired by the well-known Gonzalez's ' algorithm for k-center clustering [2 The algorithm greedily selects k points from the input point set, and the & balls centered at these selected k points with some appropriate radius can cover the whole input; if the input data has a low intrinsic dimension (e.g., the doubling dimension in Definition 3) the radius is no larger than upper bound depending on k. Therefore, the set of cluster centers (each center has the weight equal to the corresponding cluster size) can serve as a coreset for the ERM problem (I), where the error yielded from the coreset is determined by the radius. Actually this k-center clustering based intuition has been used to construct the coresets for various applications before 34 21
However, we have address two challenging issues for realizing this approach on relational data. First, the greedy selection procedure for the it cluster centers cannot be directly implemented for relational data. Second, it hard to obtain the size of each cluster especially when the balls have overlap (the & balls can partition the space into as many as 2 parts). Actually, both of these two issues can be regarded as the instances of FAQ-AI(K- - 1) which are NP-hard to compute 3 42)
Our approach relies on a novel and casy-to-implement structure called "aggregation tree with pseudo-cube". We build the tree from bottom to up, where each relational table represents leaf. Informally speaking, each node consists of a set of k cluster centers which is obtained by merging its two children; each center also associates with a "pseudo-cube" region in the space. Eventually, the root of the tree yields qualified coreset for the implicit design matrix. The aggregation manner can help us to avoid building the high-complexity grid coreset as [22] (4] Also, with the aid of "pseudo-cube" we can efficiently estimate the size of each cluster without tackling the troublesome FAQ-AI counting issue
Comparing with the previous coresets methods, our approach enjoys several significant advantages. For example, our approach can deal with more general applications. In fact, for most ERM problems in the form of (T) under some mild assumptions, we can construct their coresets by applying our approach. Also our coresets have much lower complexities. It is worth emphasize that our coreset size is independent of the dimensionality d; instead, it only depends on the doubling dimension of the input data.
1.2 Other Related Works
The earliest research relational data was proposed by Codd [18] A fundamental topic that is closely related to machine learning on relational data is how to take uniform and independent samples from the full join results [13). Recently, Zhao al. [59) proposed random walk approach for this problem with acyclic join; Chen and Yi [15 generalized the result to some specific cyclic join scenarios.
3 42), there also exist number of results on other machine learning problems over relational data. Khamis al. [4] and Yang al. [57] respectively considered training SVMs and SVMs with Gaussian kernel on relational data. For the problem of linear regression on relational data, is common The algorithms for training Gaussian Mixture Models and Neural Networks on relational data were also studied recently 17). We also refer the reader to the survey paper [5] for more details learning over relational data.
Beside the aforementioned works [45 35 22
24,
36
the factorization techniques (50 2
2 Preliminaries
Suppose the training set for the problem 1 set of n points in Rdd, and is decoupled into s relational tables {Ti. T.} with the feature (attribute) sets {Di....,D.k D.}. Let D = =, D, and therefore the size [D] = d. Actually, each table T, can be viewed as projection of P onto a subspace spanned by D: To materialize the design matrix of P. a straightforward way is to compute the join over these s tables. With a slight abuse of notations, we still use " "P" to denote the design matrix. We also let [s] {1,2...., 3) for simplicity.
3

---

T
T2
T
72
d1
22
d2
d3
d1
d2
d3
1
1
1
2
1
4
4
2
2
3
1
2
1
3
3
3
3
3
3 3
3
Table An illustration for the join over two tables.
Definition 1 (Join) The join over the given tables returns n x d design matrix P T1 b4 ... De
To, such that for any vector (point) p E IR E P if and only if E [s], Proin, (p) E Tú where Projd, (p) is the projection of p on the subspace spanned by the features of Dz.
Table is a simple illustration for joining two relational tables. To have a more intuitive understanding of join, we can generate hypergraph G = (V, E). Each vertex of V corresponds to an individual feature of D; each hyperedge of & corresponds to an individual relational table T. and it connects all the vertices (features) of Dj. Then we can define the acyelic and eyclic join queries. A join acyclic if the hypergraph G = (V, E) can be ablated to be empty by performing the following operation iteratively: if there exists vertex that connects with only one hyperedge, remove this vertex together with the hyperedge. Otherwise, the join is cyclic. A cyclic query usually is extremely difficult and has a much higher complexity than that of an acyclic query. For example, for cyclic join, it even NP-hard to determine that whether the join is empty or not [41]. Fortunately, most real-world joins are acyclic, which allow us to take full advantage relational data. Similar with most of the previous articles on relational learning 3 4) we also assume that the join of the given tables is acyclic in this paper.
Counting is one of the most common aggregation queries on relational data. It returns the number of tuples that satisfy some particular conditions. The counting on an acyclic join (without additive inequalities) can be implemented effectively via dynamic programming (25). But when the additive inequalities are included, the counting problem can be much more challenging and we may even need to materialize the whole design matrix [3] For example, to count the tuples of (t E T1 D4 T2 & || < 5) in Table we need to check the whole design matrix Tj pa T2 for selecting the tuples that satisfy the constraint "114112 < 5".
For the machine learning problems studied in this paper, we have the following assumption for the loss function in T
Assumption (Continuity) There exist real constants a, 2 0, [0, 1). such that for any p.q E TRd. and any in the hypothesis space, we have
(f(0p) (00,4) allp- d11 (00
where || 11 is the Euclidean norm in the space.
Remark Different machine learning problems have different values for or, 3 and z. For example, be any small number
for the k-means clustering, we have = = 2, and O(2) (where in (0, 1)): for the k-median clustering, we have = 1, B = 0 and a = 1. Actually for a large number of problems, B small or even 0, e.g., the logistic regression and SVM with soft margin problems have the value 3 = O.
We define the following coreset with both multiplicative error and additive error. We are aware that the standard coresets usually only have multiplicative errors 43 27 However, the deviation bounds for the ERM problems with finite training data set only yield additive error guarantees and the additive error is usually acceptable in practice [8] [5). So the coresets with additive error have been also proposed recently
(9. Let given), and denote by A the diameter of P (i.e., the largest pairwise distance of P).
{pi P2.... : Pn. be the training set (which is not explicitly
Definition ((E1,62) -2).--CCrsesse Suppose 6 E (0, 1) and e2, > O. The (61, (arse22_-ooo -coreset, denoted as P. is a point set (cr,"., } with a weight vector W = [wi, W2,-.., ...,..., W p)] satisfying that
F(O) E =1 A²
(3)

---

for any 0 in the hypothesis space HI, where F(0)
E w. f0.((0..))
Ei= mi
Usually we want the coreset size [P] to be much smaller than |.). So we can run our algorithm P and save a large amount of running time.
As mentioned in Section 1.1 also assume that the training set P has low intrinsic dimension. "Doubling dimension" is a widely used measure for indicating the intrinsic dimension of a given data set [40) Roughly speaking, it measures the growth rate of the given data in the space. Recently it has gained lot of attention for studying its relation to coresets and machine learning problems [3 32
19
For any IRd and r 2 O, we use (c, r) to denote the ball centered at with radius r.
Definition& 3 (Doubling Dimension) The doubling dimension of a data set P is the smallest number such that for any p Pand 2 0, Pr B(p, 2r) is always covered by the union of most 2 balls with radius r.
It is easy to obtain the following proposition by recursively applying Definition
Bogg times.
Claim For a given data set and radius 0, P has the doubling dimension p, then can be covered by ( ( balls of radius
3 Relational Coreset via Aggregation Tree
In this section, we present an efficient coreset construction method for relational data. First, we introduce the technique of aggregation tree with pseudo-cube. Actually there is an obstacle for obtaining the coreset from the aggregation tree. The weight of each point of the coreset determined by the size of its corresponding pseudo-cube; however, the pseudo-cubes may have overlap and challenging to separate them in the environment of relational data. To explain our idea more clearly, we temporally ignore this "overlap" issue and show the "ideal" coreset construction result in Section 3.1 Then we show that the overlap issue can be efficiently solved by using random sampling and some novel geometric insights in Section 3.2
Recall that our input (Di...., D.}. Also D = U, D: and |D] = d. For ease of presentation, we generate new feature set D, for each D; follows: initially, i) starting from i to s, we let D; DA D.). is easy to see that U, D. = D, and Vi, E i j. D,nD, = 0. With a slight abuse notations, we also use Dj to represent the subspace spanned by the features of D; (so the Cartesian product Dj ... x D2 is the the whole space Re.). For any point set Q C TR (resp., any point E IRd)) and any subspace H of Rdd, we use Proj (Q) (resp., Proj (c)) to denote the projection of Q (resp.. c)
of relational tables (Ti...., T3} with the feature (attribute) sets
onto H.
3.1 Coreset Construction
Since coreset construction algorithm is closely related to the Gonzalez's 's algorithm for k-center clustering 29) we briefly introduce first. Initially, it arbitrarily selects a point from P. say c, and sets C {ci): ); then it iteratively selects new point that is farthest to the C, i.e., arg maxpe mingec ||p gll. and adds to C. After & iterations, we obtain k: points in C' (suppose C (oi... C& }). The Gonzalez's algorithm yields 2-approximation for k-center clustering. If the optimal radius of k-center clustering on P is Topt. then P can be covered by the k balls B[c,, 2).
B(ck, 2ropt). Together with Claim I for any given radius r > O, we know that we run the Gonzalez's 's algorithm on P with setting B(cr,)) r)...................... .... B(cr, r) (since Tapt < r/22). If we set r to be small enough, the obtained C' can be good approximation (informally coreset) for P.
(24) y", the set P can be covered by the balls
However, as mentioned in Section such k-center clustering approach cannot be implemented on relational data since it is equivalent to an instance of FAQ-AI(k 1). A straightfoward idea to remedy this issue to run the Gonzalez's algorithm in each subspace D,, and then compute the Cartesian product to build grid of size k* as the methods of [22 24 But this approach will result in an exponentially large coreset g., there are = tables and k = 1000). Below, we introduce our algorithm that can achieve coreset with mrasi-polynomial size.
5

---

Coreset
Figure 1: For the example in the figure, k = 4. When merging two children, we have Cr, and Cv. from two disjoint subspaces (the purple points). Then we build the grid, and select Cr (the red points) by running the Gonzalez's algorithm on the grid points.
Our high-level idea. We construct a bottom-to-top tree T where each relational table T; corre- sponds to leaf. For each node v E T, associated with a set of components: an index set I [s]. the spanned subspace H₂ = Ie, D. and a collection of centers C2 = fcr.1.... ... Cy,k) C H₂. The center set C₂ determines a set of pseudo-cute cubess (as Definition bellow) in Hy. Obviously, for a leaf node (table) of T; the index set I, {i) and the space H, D;; we directly
the Gonzalez's algorithm on the projection of P D; to obtain the set C.. Then, we grow the tree T from these leaves. For each parent node Upp, we compute grid Cv, x C., of size h² by taking the Cartesian product of the center sets from its two children My and vy; then we remove the "empty" grid points (we will explain the meaning of "empty" after Definition 4 and run the Gonzalez's s algorithm on
the remaining grid points, which are denoted as Cn x Cy., to achieve the set C. The index set I,, = In U Iu., and the subspace Hy, Hy, Hv,, Finally, the set Cr, of the root node vo yields a coresct for the point set P. See an illustration the aggregation tree in Figure T
It is worth noting that our aggregation tree approach is fundamentally different to the hierarchical decomposition tree methods that were commonly studied doubling metrics BD [2] and other tree structures like kd-tree [23]. They build their trees from top to bottom, while our approach is from bottom to top, Actually, our approach can be viewed as a "compressed" version of the grid coreset
methods (22 24 where deal with a grid of size at most k2 each time. Also, the accumulated error can be also bounded since the height of T O(lgg 8).
Definition (Pseudo-cube) Given an index set S [s). a point e E H = Iher D, and a number 2 0, we define the pseudo-cube
PC)(c, = II
B (PProj
GET
where Proj (c) is the projection of onto the subspace D..
nice property of pseudo-cube cube that is Cartesian product of a set of regions from those subspaces D,s, More importantly, it does not involve any cross-table constraints or additive inequalities. Consequently, counting the size of pseudo-cube is easy to implement over the relational data. Another property is that the Cartesian product of two pseudo-cubes still a pseudo-cube, but in new subspace with higher dimension. When we take the grid of the two center sets from two children nodes, we also obtain k2 pseudo-cubes. For each pseudo-cube, we count its size (i.e., the size of its intersection with P); if the size is 0, we call the corresponding grid point is "empty" and remove it before running the Gonzalez's s algorithm on the grid.
Let d(A,, B) maX.eA minge ||a 6| for any two sets A and B in Rd (i.c., the directed Hausdorff Distance). First, for each / 0, 1, ... [log s]. we define key value (P),C,) is at the h-th level of T). By using these LAS, we present our coreset construction approach in Algorithm I
Ln
(5)
Theorem Suppose the loss function f(:.)) satisfies Assumption
If we ( (1)+ (2)+3(logo), Io a) = (02)o(((0g))))) in Algorithm the returned set Cyn

---

Algorithm 1 AGGREGATION TREE
Input: A set of relational tables (T...... T,) and parameter ls (the coreset size).
Output: A weighted point set as the coreset.
1. Initialize an empty aggregation tree T; when a node v of T is constructed, is associated with an index set I, and its corresponding subspace Hy, and set of k centers C₁ (Cu,11..... Cu,k C Hy.
2. Construct leaf nodes ..,...., v/} corresponding to the tables at the 0-th level: run the Gonzalez's algorithm to select centers for each table T, on the subspace D. Also obtain the value Lo defined in (5)
3. Let Children (V1....,yy) v33 and Parent 0. Initialize h 0 to indicate the current level
on T.
4. For h = to [log s]:
(a) Initialize 4, = 0:
(b) While [Chi Chilldren >= 2:
i. Select two different nodes V4, V/ from Children, and Children Children \ (2,,
ii. Compute the Cartesian product to construct grid Cv Cu, with k22 centers in the space
Hv x Haji
ii. For each CE Cr, x CuN, perform the operation "COUNT" to count the size of fo E PI
Projs., (p) E PCr,, (Proiи,, (c), I1- & Proin., (p) PCr., (Prois., (c), La- In-1);
iv. Remove from Cz, x Cu. if the size is O, and then obtain Cv, Cvy that is the set of remaining non-empty grid points;
Construct parent node run the Gonzalez's s algorithm on Cv, x Cuy to obtain set C.
of ls centers, let 4. max(h,, d(Cu, Cuyy Co)), I, Iv U Un, and H, Hv, Hyj:
vi. Parent Parent U {w}:
(c) L, = (4, + 12L;-1):
(d) Children Children Parent Parent
5. Let vo be the root node; for each Cva.á E Cv., we assign a weight w, IP n PCY., (Cog,i; [1) (actually, this is not accurate expression since the pseudo-cubes may have overlap with each other, and we will address this issue in Section 3.2)
return the set Cn, with the weights "ui,"..,hh"
with the weights {wi,.... wg} yields a (B, -coreset. The time complexity of constructing the tree O (sk2 (N,TVNNNA, s, d) *k²), where (NN, 8, d) is the complexity of performing the counting each time M (for counting an acyclic join, Le (NN s, d. = 0 (sdf N log(N))).
Remark Note that our coreset size is muasi-polynomial since has a factor 20((oo But we would like to emphasize that this factor usually is small for most practical problems. For example, in the standard TPC-H benchmark [47]. is no larger than 8, although the design matrix over joining the tables can be quite large.
To prove the above theorem, we first introduce the following key lemma. We let ro A. From
Claim we know that the entire data set P can be covered by k balls with radius ro-
Lemma For each h 0, 1.. flog s]. La < 3/ 13
31
Proof. Since the Gonzalez's algorithm yields an approximation factor 2, from Claim I we know that Lo < 2ro- Then we consider the case h > 1. Suppose the algorithm constructing the /-th level of T. In Step 4b we repeatedly select two nodes v4, Py from the (h - 1)-th level that form a parent node at the level. Let Copt be the optimal solution of the k-center clustering on Proj Proj xHa, (P). Since P can be covered by & balls with radius ro. so can the projection Proj xH., (P). That is,
d( d(Projn,, xHI, (P), Copt) S ro-
(6)
7

---

Also, since d(Projn,,, (P),Cu) I Lh-1 and d(Projn,, (P), Cv,) - Ln-1, we have
d H(Proj xH,, Cz Cvg) V2
Note that we use Cv. x Cv. instead of Cv. x Cv. in the above 7). The reason is that the Cartesian product Cv x Cv, may contain some "empty" grid points (see Algorithm [ step 4(b)(ii)), and the
distance bound "V2Ln-1" does not hold for them.
Together with 6 we know
d(Cu, Cwy: Copt) S V
That is, we run k-center clustering on Cv2 x Cuys the optimal radius should be no larger than Tu + 22 So we run the 2-approximation Gonzalez's algorithm on Cv. x CuN and obtain the center set Cv, then
a aCCr, Ciyy C2) 2(ro V2Ln-1).
(9)
Further, combine and 9 and obtain
a d(Proj May (P), 2(r + v2Tn-1) + 2L
(10)
For each Cr2 E Cv, we construct a pseudo-cube
II
(c..), + V2Ln-1) + V2Ln-1).
(11)
tET,,Ur
Then we know that Proj H (P) is covered by the union of the obtained pseudo-cuhes. Because
22, Together with Lo S 2ro. [4] = 4,, U45 < 2h, we have La I (2(ro 22 (2
solve this recursion function and obtain L, - 33h 22 23
To-
Comma[[iidicateee that the difference between Cr,, and P is bounded in the space. To prove it is qualified coreset with respect to the ERM problem ( we also need to assign a weight to each point of Cug. In Step15 of Algorithm we set weight w; |P PCJ., (Cro.i, Lo et) ]l (for simplicity, we temporarily assume these pseudo-cubes are disjoint, and leave the discussion on the overlap issue
Section 3.2 The detailed proof of Theorem Tis is placed our full paper 14
Remark In a real implementation, if the coreset size is given (e.g. 5% of the input data size Pl), given
directly set the value for to Algorithm [ Another scenario is that restricted variance between P and the output Cvo (i.e., the difference d (,P, Cv.,) ) is required to be no larger than threshold). Then from a small constant ko, we can try k = ko, 2kg, 2 kig .., until the difference is lower than the threshold.
try the value for k via doubling search. For example, starting
3.2 The Overlap Issue
We consider the k pseudo-cubes PCT., (Cog,is Looo =1). < S k, obtained from Algorithm I Since Vo the root, it easy know Ing = [s] and Hr, Rdd. For the sake of simplicity, we use PC; to denote the pseudo-cube PCJ.., (Crg.i ; [og and L to denote L[tog= below.
these pseudo-cubes are disjoint, we can simply set the weight w; = |P n PC,| as Step 5 of Algorithm [ However, these pseudo-cubes may have overlaps and such an assignment for the weights cannot guarantee the correctness of our coreset. For example, a point E P is covered by two pseudo-cubes PC,, and PC we should assign g only one pseudo-cube. Note that this overlap issue is trivial if the whole data matrix P is available. But it can be troublesome for relational data, because is quite inefficient to perform the counting on their union P n (PC., U UP,,,). Moreover, the l pseudo-cubes can partition the space into as large as 2 different regions, and challenging to deal with so many overlaps.
8

---

Fortunately, we can solve this issue by using random sampling, The key observation is that we can tolerate a small error on each weight wp. Let d E (0, 1). If we obtain set of approximate weights
W = [w1, " wxk ,.k that satisfy w/ E (1 + 8)w; for 1 S i S k, then we have
&
(0, Cro.a) E (1
Σ
wif( Con.s),
(12)
i=1
for any 8 in the hypothesis space H. We can use the following idea to obtain a qualified W
High-level idea. Without loss of generality, we assume all the k pseudo-cubes are not empty (otherwise, we can directly remove the empty pseudo-cubes). Then we consider the pseudo-cubes one by one. For PC1, we directly set wi = |P n PC1 Suppose currently we have already obtained the values w(.... .... Whd and try to determine the value for w/ We take a uniform sample of m points from P P +1 by using the sampling technique for relational data [59]. Each sampled point corresponds binary random variable x: if it belongs to PC \ (U PC,), 1; otherwise, x = O. m is sufficiently large, from the Chernoff bound, we can prove that the sum of these m random variables (denote by g) over can serve good estimation of
PP (PC \ PC,))
+io+1
| PC
(13)
Thus set w
PP |Pn (PC \ Pc.))
remaining issue of the above method that the ratio Ti++1 can be extremely small, that is, we have to set m to be too large for guaranteeing the multiplicative "1 + 8" error bound. Our idea for solving this issue from the geometry. If Tig+1 extremely small, we label PC as a "light" pseudo-cube. Meanwhile, it should has at least one "heavy" neighbor from [PC1, PC ). The reason that a small + implies that there must exist some S v1 S ig. such that the intersection P PCP PC,, takes significant part of P n pp And we label PC,, of PC Moreover, the distance between PC,, and PC should be bounded (since they have overlap in the space). Therefore, we can just ignore PC and use PC, to represent their union PC, UP This idea can help us to avoid taking a too large sample for light pseudo-cube. Overall, have the following theorem, and the detailed proof is placed to full paper [14]
"heavy" neighbor
Theorem 2 Suppose the loss function f(-,-) satisfies Assumption 7 and E1 > B. If we set k in k²
Algorithm / as Theorem ! and let 2 O (( -3 log {) where X (0, the returned set Owp with the weights W yields a (61, 62) coreset with probability 1 - A. The sampling procedure takes md) time.
4 Experimental Evaluation
We evaluate the performance of our relational coreset on three popular machine learning problems, the SVM with soft margin (a O(10112), = 0, and 1). the me.ns clustering (a - O 3 == 6, and z = 2, where 6 can be any small number in (0. 1)). and the logistic regression (a = ([) 0. and
1). All the experimental results were obtained server equipped with 3.0GHz Intel CPUs and 384GB main memory. Our algorithms were implemented in Python with
PostgreSQL 12.10. We release our codes at Github (28).
Data sets and Queries. We design four different join queries (QI-Q4) on three real relational data sets. Q1 and Q2 are designed on labeled data set HOME CREDIT [1), and
them to solve the SVM and logistic regression problems. Q3 and Q4 are foreign key joins (3) designed on the unlabeled data sets YELP [58) and FAVORITA 26 respectively, and we use them to solve the k -e-means clustering problem.
construct the complete design matrix and run the training algorithm directly on it. (2) ORI-GON: construct P as ORIGINAL, run the Gonzalez's 's algorithm [29] on / to obtain the centers, and then run the training algorithm on the centers. (3) UNIFORM: the relational uniform sampling algorithm [59]. (4) RK-MEANS: the relational means algorithm 22 (5) RCORE: our relational coreset approach.
Baseline methods. We consider five baseline methods for comparison. (1) ORIGINAL:
We use "k." instead of "k" to avoid being confused with the coreset size

---

We consider both the running time and optimization quality. We record the end-to-end runtime that includes the design matrix/coreset construction time and the training time. For the optimization quality, we take the objective value F(0*) obtained by ORIGINAL as the optimal objective value; for each baseline method, we define "Approx."= F(0)=F(0") where F(0) the objective value obtained by the method.
F(0*)
Coreset size
200
400
600
800
1000
ORIGINAL
> 21600
End-to-end runtime (s)
ORI-GON
3808
5208
6606
8044
9434
UNIFORM
34
35
35
36
38
RCORE
208
288
363
446
531
ORI-GON
1.41
1.50
1.29
1.12
0.95
Approx.
UNIFORM
2.22
2.60
2.09
2.23
2.14
RCORE
0.92
0.31
0.27
0.16
0.02
Table 2: The results of SVM on Q1.
Q4
Ori Gon
Uniform
Ro--mees MCCore Liniform
Ori-Don
Pok-means
3000
FeCora
2000
200
Corchutinn The
2000
Ausage Loss
150
3000
100
500
Figure 2: The results of -mens Q4.
Due to the space limit, we only present part of the results (Table and Figure 2p here. In general, ORIGINAL and ORI-GON are the most time-consuming ones because they need to construct the whole design matrix and perform the operations (like train the models or run the Gonzalez's 's algorithm) on the data (even if the queries are foreign key joins). UNIFORM is always the fastest one, because only takes the simple uniform sampling procedure; but its overall optimization performance is relatively poor. Except ORIGINAL, our RCORE has the best optimization quality for most cases with acceptable running time. We leave the more detailed experimental results to our full paper [14].
Conclusion
In this paper, we propose a novel relational coreset method based on the aggregation tree with pseudo-cube technique. Our method can be applied several popular machine learning models and has provable quality guarantees. In future, there are also several interesting problems deserved to study, e.g., the relational coresets construction for more complicated machine learning models, and the privacy-preserving issues for relational coresets when the input data contains sensitive attributes.
Acknowledgements
The research of this work was supported in part by National Key R&D program of China through grant 2021 YFA 1000900 and the Provincial NSF of Anhui through grant 2208085MF163 We also want to thank the anonymous reviewers for their helpful comments.
10

---

References
[1] M. Abo Khamis, H. Q. Ngo, and Rudra. Faq: questions asked frequently. In Proceedings of the 35th ACM CEGMOD-SIGACT-SIAA Symposium on Principles of Database Systems, pages 13-28, 2016.
[2] M. Abo Khamis, H. Q. Ngo, X. Nguyen, Olteanu, and M. Schleich. In-database learning with sparse tensors. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAA Symposium on Principles of Database Systems, pages 325-340, 2018.
[3] M. Abo-Khamis, S. Im, B. Moseley, K. Pruhs, and A. Samadian. Approximate aggregate queries under additive inequalities. In Symposium Algorithmic Principles of Computer Systems (APOCS), pages 85-99. SIAM, 2021.
[4] M. Abo-Khamis, S. Im, B. Moseley, K. Pruhs, and Samadian. A relational gradient descent algorithm for support vector machine training. In Symposium on Algorithmic Principles of Computer Systems (APOCS), pages 100-113. SIAM, 2021.
[5] S. Acharya, P. B. Gibbons, Poosala, and Ramaswamy. Join synopses for approximate query answering. In A. Delis, C. Faloutsos, and S. Ghandeharizadeh. editors, SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1-3, 1999, Philadelphia, Pennsylvania, USA, pages 275-286. ACM Press, 1999.
[6] D. Arthur and S. Vassilvitskii. k-means++: the advantages of careful seeding. In SODA '07, 2007.
[7] A. Atserias, M. Grohe, and Marx. Size bounds and query plans for relational joins. SIAM J. Comput., 42(4):1737-1767, 2013.
[8] O. Bachem, M. Lucie, S. H. Hassani, and A. Krause. Uniform deviation bounds for k-means clustering. In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 283-291. PMLR, 2017.
[9] O. Bachem, M. Lucic, and A. Krause. Scalable k -means clustering via lightweight coresets. In Y. Guo and F. Farooq, editors, Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, KDD 2018, London, UK, August 19-23, 2018, pages 1119-1127. ACM, 2018
[10] M. Belkin. Problems of learning on manifolds, 2003.
[11] Z. Borsos, M. Mutny, and A. Krause. Coresets via bilevel optimization for continual learning and streaming. Advances in Neural Information Processing Systems, 13:14877- 2020.
[12] T.H.. H. Chan, A. Gupta, B. M. Maggs, and S. Zhou. On hierarchical routing in doubling metrics. ACM Transactions on Algorithms (TALG), 12(4):1-22, 2016.
[13] S. Chaudhuri, R. Motwani, and V. R. Narasayya. On random sampling over joins. In A. Delis, C. Faloutsos, and S. Ghandeharizadeh, editors, SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1-3, 1999, Philadelphia, Pennsylvania, USA, pages 263-274, ACM Press, 1999.
[14] J. Chen, Q. Yang, R. Huang, and H. Ding. Coresets for relational data and the applications, 2022. URL httph: /tapps://arxiv..o owaziii.g////.....o abs//210.22222// 04249
[15] Y. Chen and K. Yi. Random sampling and size estimation over cyclic joins. In 23rd Interna- tional Conference Database Theory (ICDT 2020). Schloss Dagstuhl-LLeiniiz-eentee für Informatik, 2020.
[16] Z. Cheng and N. Koudas. Nonlinear models over normalized data. In 2019 IEEE 35th International Conference Data Engineering (ICDE), pages 1574-1577. IEEE, 2019.
[17] Z. Cheng, N. Koudas, Z. Zhang, and X. Yu. Efficient construction of nonlinear models over normalized data. In 37th IEFE International Conference on Data Engineering, ICDE 2021, Chania, Greece, April 19-22, 2021, pages 1140-1151. IEEE, 2021.
11

---

[18] E. F. Codd. A relational model of data for large shared data banks (reprint). Commun. ACM, 26 (1):64 69, 1983.
[19] V. Cohen-Addad, A. E. Feldmann, and D. Saulpic. Near-linear time approximation schemes for clustering in doubling metrics. J. ACM, 6866):4411444344, 2021.
[20] V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn. A new coreset framework for clustering. In S. Khuller and V. V. Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 169-182. ACM, 2021.
[21] C. Coleman, C. Yeh, S. Mussmann, B. Mirzasoleiman, P. Bailis, P. Liang, J. Leskovec, and M. Zaharia. Selection via proxy: Efficient data selection for deep learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[22] R. R. Curtin, B. Moseley, H. Q. X. Nguyen, D. Olteanu, and M. Schleich, Rk-means: Fast clustering for relational data. In S. Chiappa and R. Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy]. volume 108 of Proceedings of Machine Learning Research, pages 2752. PMLR, 2020.
[23] M. de Berg, O. Cheong. M. van Kreveld, and M. H. Overmars. Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008
[24] H. Ding, Liu, L. Huang, and Li. K-means clustering with distributed dimensions. In M. Balcan and K. Q. Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY. USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 1339-1345 JMLR.org, 2016.
[25] M. E. Dyer. Approximate counting by dynamic programming. In L. L. Larmore and M. X. Goemans, editors, Proceedings of the 35th Anmual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 693-699, ACM, 2003.
[26]
Favorita.
Favorita
dataset.
https: htops:://www..t kag.ke......o...... com/ c/
[27] D. Feldman. Core-sets: An updated survey. WIREs Data Mining Knowl. Discov., 10(1), 2020.
[28] Github. Source code of our relational coreset approach. https://github: htw.tttuu.coooooooo com/cjo zar Coresets-for-Reett wew.rfoo-eeaaaiian--laaaaaaaaaa. Data- and - Ape--pppppicinnss
[29] F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci., 38:293-306, 1985.
[30] S. Har-Peled and M. Mendel. Fast construction of nets in low-dimensional metrics and their applications. SIAM Journal on Computing, 148- 2006.
[31] HomeCredit.
Home credit dataset.
cow com/dataset/
databetaal/dataTd-6811
[32] L. Huang, S. H. Jiang, J. Li, and X. Wu. Epsilon-coresets for clustering (with outliers) in doubling metrics. In M. Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 814-825. IEEE Computer Society, 2018.
[33] J. H. Huggins, T. Campbell, and T. Broderick. Coresets for scalable bayesian logistic regression. In D. D. Lee, M. Sugiyama, U. von Luxburg. Guyon, and Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 4080 4088, 2016.
[34] Indyk, S. Mahabadi, M. Mahdian, and V. Mirrokni. Composable core-sets for diversity and coverage maximization. In R. Hull and M. Grohe, editors, Proceedings of the 33rd ACM CIGMOD-SIGACT-SIGAAN Snowbird, UT, USA, June 22-27, 2014, pages 100-108. ACM, 2014.
Symposium on Principles of Database Systems, PODS 14,
12

---

[35] M. A. Khamis, H. Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich. In-database learning with sparse tensors. In J. V. den Bussche and M. Arenas, editors, Proceedings of the 37th ACM SIGMOD-SIGACCTSIIGA Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 325-340. ACM, 2018.
[36] M. A. Khamis, R. R. Curtin, B. Moseley, H. Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich. Functional aggregate queries with additive inequalities. ACM Trans. Database Syst. 45(4): 17:1-17:41, 2020.
[37] M. A. Khamis, S. Im, B. Moseley, K. Pruhs, and A. Samadian. A relational gradient descent algorithm for support vector machine training. In M. Schapira, editor, 2nd Symposium Algorithmic Principles of Computer Systems, APOCS 2020, Virtual Conference, January 13, 2021, pages 100-113. SIAM, 2021.
[38] Y. Li, M. Long, and A. Srinivasan. Improved bounds the sample complexity of learning. Journal of Computer and System Sciences, 62(3):516-527, 2001.
[39] M. Lucic, M. Faulkner, A. Krause, and D. Feldman. Training gaussian mixture models at scale via coresets. J. Mach. Learn. Res., 18: 18:11611116::: 2017.
[40] Luukkainen. Assouad dimension: antifractal metrization, porous sets, and homogeneous measures. Journal of the Korean Mathematical Society, 35(1):23-76, 1998.
[41] D. Marx. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM, 60(6):42:1 -2:511, 14,54212 2013.
[42] B. Moseley, K. Pruhs, A. Samadian, and Wang. Relational algorithms for k-means clustering. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Schloss Leibuhhl-LLibbiiizeetruuu für Informatik, 2021.
[43] A. Munteanu and C. Schwiegelshohn. meetsoss and history: A theoreticians design pattern for approximation and streaming algorithms. Künnstliche Intell., 32(1):37-55 2018.
[44] A. Munteanu, C. Schwiegelshohn, C. Sohler, and D. P. Woodruff. On coresets for logistic regression. In K. David, K. Geihs, M. Lange, and G. Stumme, editors, 49, Jahrestagung der Gesellschaft für Informatik, 50 Jahre Gesellschaft für Informatik Informatik für Gesellschaft, INFORMATIK 2019, Kassel, Germany, September 23-26, 2019, volume P-294 of LNI, pages 267-268. GI, 2019.
[45] H. Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich. In-database factorized learning. In J. Reutter and D. Srivastava, editors, Proceedings of the I Ith Alberto Mendelzon International Workshop on Foundations of Data Management and the Web, Montevideo, Uruguay, June 7-9, 2017, volume 1912 of CEUR Workshop Proceedings. CEUR-WS.on WS.rg 2017.
[46] J. M. Phillips. Coresets and sketches. CoRR, abs/1 000/16601001..... 2016.
[47] M. Pöss and C. Floyd. New TPC benchmarks for decision support and web commerce. SIGMOD Rec., 29(4):64-71, 2000.
[48] Report. Relational Database Management System Market: Industry Analy- sis and Forecast 2021-2027:
By Type, Deployment, End users, and Region
2022.
URL https:// //t::///www /www www.maiinimmm www.massmmiiemakkreeteeeaccccccc wwtee/ccc..c./.raeeeeeee com/markett-eeort.... oaaaall-eeattttalllaaaalaaaaeaae wwwaeeeeaaaaagmaeaeeeeeeeee htw.://mmattttttttteeaaattt///se
[49] A. Samadian, K. Pruhs, B. Moseley, Im, and R. Curtin. Unconditional coresets for regularized loss minimization. In International Conference on Artificial Intelligence and Statistics, pages 482-492. PMLR, 2020.
[50] M. Schleich, Olteanu, and R. Ciucanu. Learning linear regression models over factorized joins. In Proceedings of the 2016 International Conference on Management of Data, pages 3-18, 2016.
[51] M. Schleich, D. Olteanu, M. A. Khamis, H. Q. Ngo, and X. Nguyen. Learning models over relational data: A brief tutorial. CoRR, abs/1911.0651 2019.
13

---

[52] O. Sener and S. Savarese. Active learning for convolutional neural networks: A core-set approach. International Conference on Learning Representations. 2018.
[53] S. Sra, S. Nowozin, and S. J. Wright. Optimization for machine learning. Mit Press, 2012.
[54] S. Sumathi and S. Esakkirajan. Fundamentals of relational database management systems, volume 47. Springer, 2007.
[55] M. Telgarsky and S. Dasgupta. Moment-based uniform deviation bounds for k-means and friends. In C. J. C. Burges, L.. Bottou, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 2940-2948, 2013.
[56] V. Vapnik. Principles of risk minimization for learning theory. In E. Moody, S. J. Hanson, and R. Lippmann, editors, Advances in Neural Information Processing Systems 4, (NIPS Conference, Denver, Colorado, USA, December 2-5, 1991], pages 831-838. Morgan Kaufmann, 1991.
[57] K. Yang. Y. Gao, L. Liang, B. Yao, S. Wen, and G. Chen. Towards factorized svm with gaussian kernels over normalized data. 2020 IEEE 36th International Conference on Data Engineering (ICDE), pages 1453-1464. IEEE, 2020.
[58) Yelp.
Yelp
dataset.
[59] Z. Zhao, R. Christensen, F. Li, X. Hu, and K. Yi. Random sampling over joins revisited. In Proceedings of the 2018 International Conference on Management of Data, pages 1525-1539, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 5
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main perimental results (either in the supplemental material or as URL)? [Yes] Detailed experimental results are in our supplement.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses cxisting assets, did you cite the creators? [Yes]] In supplement material.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [No]
14

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "qIpXhxqrABK", "reviewer": "Reviewer_ZRDo", "summary": "The paper proposes an algorithm for constructing a coreset from relational data without materializing the data matrix by joining the tables. The paper improves over previous work by considering ML tasks other than clustering and by avoiding a coreset size exponential in the number of tables. The produced coresets have a bound on the error on the empirical risk that has both a multiplicative and an additive component.\n\nThe result is a achieved by using an aggregation tree that builds the coreset bottom up from the individual tables.\nAt each level of the tree Gonzalez's clustering algorithm for $k$-center clustering is applied to obtain local coresets that are then combined in the parent node building so called pseudo-cubes. The weights of the points in the final coreset\nare obtained by counting the intersection of pseudo-cubes with the original dataset. To avoid overcounting due to pseudo-cubes overlapping, sampling is used.\n\nThe supplementary material shows experiments on three datasets for k-means clustering, SVM and logistic regression.\nThe speedup obtained for SVM and LR with respect to the materialization case is of one or two order of magnitude.\nIn clustering, the comparison with R$k$-means show that the approach is advantageous when there are more than 3 tables both in terms of time and of solution quality.", "questions": "\n1) Please define the concepts mentioned above\n2) Please provide a proof of Claim 1\n3) Please explain how the fact that nodes from different level may be combined does not pose problems for the proofs.\n4) In the experiments, the Home Credit dataset has binary attributes, not real attributes. Please explain why this does not pose problems with your method.", "limitations": "Yes, the limitations of the approach has been presented. The work does not have negative social impacts.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The difference with related work is clearly highlighted, in particular with the R$k$-means algorithm of [Curtin et al 2020]: the proposed algorithm tackles other tasks besides clustering, is not limited to coresets exponential in the size of the number of tables and the experiments show it is faster, so the originality is high.\n\nTechnically the paper appears sound, even if it is difficult to check for a non expert in the domain because of the use of specific terminology that is not introduced:\n1) In equation 3, $\\Delta$ appears without definition\n2) From line 185 we learn that $\\Delta$ is the diameter of the dataset, but the concept of diameter is not defined.\n3) Claim 1 is non obvious and should be proved. Moreover, the number $(\\frac{\\Delta}{r})^\\rho$ may be non integer, how do you deal with such a case?\n4) Line 211 speaks of the optimal radius of $k$-center clustering without defining it\nAnother technical problem is the assumption that a node at level h of the aggregation tree is built from two nodes at level h-1: however, if the number of tables is not a power of 2, at one point you will have to combine two nodes at different levels. Does this poses a problem to the proofs?\n\nThe presentation is overall clear, apart from the undefined concept mentioned above. \"Additive inequalities\" should be defined as well. In the algorithm, the variable $Parent$ is unnecessary: the algorithm would be simpler and easier to understand if point (d) would simply be $Children=Children \\cup \\{ \\nu \\}$.\n\nThe significance of the contribution is high, as the speedups that can be obtained are impressive especially for SVM and LR.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SWcZWbryEB", "reviewer": "Reviewer_SwdD", "summary": "This paper claims that when given a relational database that is normalized, we don't need to explicitly create the design matrix by denormalizing the data and then sample them with the coresets. In other world when the data ialredy given compressed as a normalized database we can reduce them further with coresets without having to create a huge temporary dataset. If we know the application of coresets such as logistic regression and SVMs we use the recent results of the FAQ method to push the computations before the joins.", "questions": "Given the impressive speedups where we can think of SVMs and logistic regression as fast block operators, what else can we do?", "limitations": "Although the results on SVMs and logistic regression are impressive, the truth is that these methods are already fast and streaming methods like vopal wabbit are already popular. It would be interesting to see how this technique would apply to deep learning. It is true that after the first layer the fully connected layers are not relational anymore. There is a special type of neural networks like the columns neural networks https://arxiv.org/pdf/1904.06950.pdf that preserve the relational structure. ", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper presents the use of some fundamental database algorithms such as FAQ in a classic machine learning problem the SVMs.  The assumption that the data can be relational is valid and true in real-world scenarios. Relational data have been neglected by the ML community despite their popularity. The paper provides solid theoretical explanation of the method with complexity bounds. \nThe benchmarks show impressive speedups, but I would have preferred more extensive experiments. \nI was also not very happy with the lack of references on kd-trees and other related ones. The method they propose looks like a relational kd-tree, or there seems to be a connection. I think it is worth exploring. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "9TtegLUsuLH", "reviewer": "Reviewer_tvSG", "summary": "The manuscript tackles the problem of learning a hypothesis that minimises the the mean loss value of all training data points. The data points are in this case only implicitly given as an acyclic join of relational tables. The manuscript proposes how to select a (possibly weighted) subset of the data points (core set) that is sufficiently representative for approximate solutions of the minimisation problem (multiplicative error $\\epsilon_1$, additive error $\\epsilon_2$), but aims to achieve significant speed-ups due to the reduced data size. The proposed approach traverses the relational tables directly without materialising the design matrix or join result.", "questions": "Q1 What percentage of relational datasets (e.g., in the referenced Kaggle 2017 \"State of Data Science Survey\") do not allow to materialise the design matrix due to prohibitive computation/storage costs (using mainstream relational database systems on modern hardware)? This question relates to W1 & W2.\n\nQ2 It is argued on l. 39 that the join of tables can be as large as $O(N^s)$. In case of foreign-key joins (see W1) the join of the tables can of course not exceed $N$, but the join result can certainly be vastly larger when joining along non-keys or if it's a cross join (cartesian product). Do join queries with result size in $O(N^s)$ commonly arise in practice (excluding cross joins that likely allow for much simpler methods)? This question relates to W2.\n\nQ3 Suppose it would be feasible to efficiently materialise the join, what are the remaining challenges due to the relational data, e.g., would it be possible to directly apply Gonzalez's algorithm or would there still be an overlap issue? This question relates to W2.\n\nQ4 Which SQL queries are supported over the base tables? This question relates to W3.\n\nQ5 Why are they called \"pseudo cubes\"? Fig. 1 seems to allude to the geometrical analogy, but it is not completely clear what it aims to explain / how it aims to help. This question relates to W4.", "limitations": "The experimental study from the supplemental material is not discussed much in the main paper and seems to be rather limited, i.e., it does not even seem to provide a proof of concept of the proposed methods (see W1). Thus, it would be useful to extend the empirical study to cover queries that would motivate the proposed approach better and add the derived insights in the main paper.\n\nWhile the work commonly talks about \"relational data\" which raises the expectation of supporting any type of SQL query it seems to be limited to a narrow set of operators (see W3). It would therefore be good to clarify which subclass of relational queries is supported by the proposed approach and why it is a sufficiently important subclass (see Q4).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nS1 The general problem of the paper seems well-motivated. The premise of the paper is very interesting.\n\nThe authors convincingly argue for the importance of relational data in the context of machine learning and core sets are a practical tool to efficiently deal with larger sets of data in a way that formally bounds the utility loss.\n\nS2 There are some potentially significant and non-trivial results that could be also useful beyond the targeted scope\n\nAlthough it is difficult to fully understand all ideas (see W4), the general ideas seem interesting and may be useful beyond coreset construction.\n\nS3 Apart from the concerns of W1-W5, the general quality of the paper is good (presentation, soundness, non-trivial contributions, relevant topic) \n\nThe paper is generally well-written, it touches upon many interesting results in prior work and reasonably uses existing ideas (Gonzalez's algorithm, doubling dimension).\n\n**Weaknesses**\n\nW1 Central claim from the abstract (l.7: \"it is expensive to directly materialize the data matrix by joining the tables\") is not substantiated\n\nMost relational queries only feature \"foreign key joins\" which do not pose much of a challenge computation-wise (see Definition 4.1 in \"Join Synopses for Approximate Query Answering\" by Achyara et al @ SIGMOD'99). For instance, all 3 queries in the experimental study (supplementary material) appear to be \"foreign key joins\" and the TPC-H benchmark (widely used in database literature) also only features foreign key joins. Note that the authors of [52] had to come up with their own queries (\"QX\", \"QY\" etc) that are not part of the TPC-H benchmark to motivate their work over the TPC-H data. Thus, it would be crucial to demonstrate that it is actually too expensive materialize the data matrix for common types of queries, i.e.:\n\n- Consider relational queries with joins along non-key columns with many-to-many-relations (e.g., quasi-identifiers in record linkage).\n- Report excessive runtimes (lower bounds suffice) of join materialisation using some modern relational database management system\n\nSome more details on foreign key joins:\n\nBig relational tables are full of redundancies which is extremely inconvenient for database updates and wastes a lot of space. Thus, database normalization splits these big tables into smaller tables. One of these smaller tables (\"main table\") has the same number of rows as the big table. By joining that table with the other tables along their \"foreign key\" column values, one reconstructs the big table. Thus, foreign-key joins can be thought of as the inverse operation of database normalization.  For instance in the experimental study (supplementary material) the table \"Application\" serves as the main table for Q1 & Q2 and \"Review\" serves as the main table for Q3 (\"main table\" has same number of rows as join result). Materialising foreign key joins can be done extremely efficiently, especially with main memory databases  (e.g., see the online demo at https://hyper-db.de/interface.html that demonstrates this quite convincingly). It is also trivial to sample from foreign key joins (see Achyara et al @ SIGMOD'99 ; one first samples the main table and then joins the main table sample with the other tables). Join sampling as in [52] is not particularly beneficial for foreign key joins, because it requires prebuilt index structures for all base tables. Thus, if the work is aimed at foreign key joins, it would be useful to adapt the approach to it.\n\nW2 Motivation unclear if join result can actually be materialised (see W1)\n\nIf the join can be materialised, there is no \"relational data problem\" as one can simply compute the design matrix and it is becomes unclear what the manuscript does differently compared to prior work (and it already seems to heavily rely on existing ideas such as Gonzalez’s algorithm). \n\nW3 The proposed approach only supports a narrow subset of relational queries.\n\nThe proposed approach inherits the limitations of [52] which for instance does not support arbitrary selections over the join result such as the widely used DISTINCT operator. In contrast, materialising the join allows all operations supported by relational database systems.\n\nW4 The presentation could be improved on some central parts of the paper\n\nFor instance the description of the \"high-level\" idea (l. 222 and following) does not provide a lot of intuition (apart from \"bottom to top\" vs \"top to bottom\") and relies a lot on  technical statements. It is often not clear how one sentence relates to the last, i.e., an overarching logical narrative seems to be missing here. Similarly, the naming and description of the \"pseudo-cube\" is a bit confusing. The description of the algorithm complexity is also difficult to read (l. 343).\n\nW5 The work is not particularly conclusive\n\nDue to a lack of theoretical/empirical baselines it is difficult to judge how useful the proposed techniques are compared to naive approaches (e.g., full materialization) and how much room for improvement is left by the proposed techniques.\n\nW6 Minor issues\n\n- l.117 What are the (not purely theoretical) insights from Chen and Yi [13] with regards to specific cyclic join scenarios and what about relaxing a cyclic join to an acyclic one as in [52] and reject any results that violate the join conditions that complete the cycle?\n- l.192 \"pesudo-cube\" => \"pseudo-cube\"\n- l.318 \"we call [...] as a ''light pseudo-cube''\" => \"we refer to [...] as a ''light pseudo-cube''\"\n\nPurely a suggestion: using $\\varepsilon$ (varepsilon) instead of $\\epsilon$ (epsilon); the supplement references 4 papers, but two of them, i.e., [1] and [2], are not referenced or discussed in the main paper. Perhaps it would be useful to reference and discuss them in the main paper as well.\n\n**Edit after author rebuttal / reviewer discussion**\n\nOverall recommendation raised from reject to weak accept, presuming that the authors fulfil their commitments to address the major concerns in the manuscript as discussed:\n\n* Add baseline *\"join-then-Gonzalez\"* to experimental evaluation that joins the relations and then runs something akin to Gonzalez's algorithm to obtain a coreset (also add uniform random sampling as a naive baseline)\n* Add a query over the missing public dataset from the Rkmeans work [20] and report all results for all queries (which would reveal when exactly the new methods offer a substantial benefit over *\"join-then-Gonzalez\"*)\n* Clarify that extremely common problem instances (foreign key joins) do not pose much of a challenge as the join size cannot exceed the table sizes and could also be handled with a simple combination of existing methods such as *\"join-then-Gonzalez\"* (thus, the focus of the work as in prior works is on harder problem instances that are also featured in the experiments)\n* Report a meaningful summary of experimental results in the main paper", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "3oGq2on4Rwf", "reviewer": "Reviewer_FGi9", "summary": "The paper addresses the problem of finding a coreset for a given\ndataset and objective function, i.e., a (smaller and weighted) set of \ndata points s.t. the objective on those points is always bounded \nfrom below and above by a linear combination of the objective \nvalue of the dataset and a suitable power of the data set radius. \nThe paper addresses esp. the coreset problem, when the dataset \nis relational and given only implicitly as set of yet unjoined \nrelations, and materializing the join is too expensive. The authors \npropose an algorithm that generalizes the well-known initialization \nscheme of k-means-clustering, to select the next cluster center as \nthe data point with maximal distance to all previously selected \nones. Their algorithm starts from coresets of the individual relations\nand then consecutively combines two subspaces by computing the \ncoresets of the cartesian products of the coresets of the two \ncomponent spaces. Each core point gets as weight the number\nof data points closest to it.\n\nThey prove that for objectives whos variation is bound from above\nby a linear combination of a power of the L2-distance and the value \nof one of the two elements, and a carefully chosen coreset size their \nalgorithm actually yields a coreset  \n\nIn the appendix, the authors compare their method against materialization\nand rk-means [3] and find their method to be both, faster and more\naccurate.\n", "questions": "The problem addressed in this paper looks interesting, but not easy to \ntackle. The proposed algorithm follows a plausible overall approach\nand its correctness could be proven. \n\nTo me, as an outsider of this research direction, the paper and its\ncontributions look fine. \n\nWhat is not clear to me: Alg. 1 in principle should also deliver correct\nresults for the (trivial?) edge case s=1. But in this case it just yields the \ndata points choosen as initial k-means cluster centers. What good \nproperties do they have say for logistic regression, as guartanteed\nby your theorem 1? Maybe explaining the algorithm from this angle\nmay make it more accessible to people outside your immediate field?\n\nSmall points:\n- p. 3 \"D=\\bigunion_i D_i\": I found that initially difficult to understand as\n  it is never said what \"D_i\" is and it later on is used in expressions such as\n  \"proj_{D_i}\" where you usually would expect a space. Saying that \"D_i\"\n  here denotes a set of (usually overlapping) column names would be helpful.\n- eq. 3: \"\\Delta\" is only defined on the next page. \n  \"F(\\theta)\" is undefined.\n- p.5 \"optimal radius\" is not explained.   \n", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strong points:\ns1. the problem addressed looks pretty complicated.\ns2. the proposed algorithm follows a plausible overall approach and is\n  provided in detail. \ns3. the algorithm is proven to be correct; esp. a coreset size is derived. \n\nweak points:\nw1. the paper is dense and not easy to follow. \nw2. experiments can only be found in the appendix.\nw3. the (way simpler?) special case of a single relation is not 100% clear. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept