Relational Approximations for Subspace Primitives

Perhaps the most basic algorithmic question to ask about the join $J$ of the tables $T_1,T_2,\mathrm{\dots },T_m$ is whether it is non-empty – does it have at least one row/point in it? This turns out to be NP-Complete [7, 10, 9]. Indeed, a simple reduction from 3CNF-SAT has the property that the number of rows in the join is exactly the number of satisfying assignments to the input formula. (This is a good spot to emphasize that in this paper, the number $d$ of features and the number $m$ of tables are not viewed as constants.)

Given this state of affairs, the approach taken by papers in this area is to assume that the join has some additional structure that makes such basic algorithmic tasks tractable. The most common assumption is that the join is acyclic – this is a combinatorial assumption about how the features are distributed across the tables, and we define it in the next section. Assuming acyclic joins lets us use dynamic programming to solve certain algorithmic questions in polynomial time [2, 1]:

1. 1.

   Compute the number of rows in the join $J$

2. 2.

   Compute the maximum of the squared $l_2$ norm of rows in the join, that is, ${\max }_{q\in J}{\sum }_{i\in C}{q}_i^2$.

These algorithmic tasks are special cases of a sum-product query. This is a query $Q(J)$ over the join $J$ of the form

where $(R,⨁,⨂)$ is a commutative semiring over a set $R$. Corresponding to feature $i\in C$, $F_i:ℝ\to R$ is an easy to compute function with range $R$. For example, for the query asking for the number of rows in the join, $R$ is the set of integers, $F_i$ is the constant function that takes on the value $1$, $⨂$ is multiplication over the integers, and $⨁$ is addition over the integers. For computing the maximum of the squared $l_2$ norm of the rows, $R$ is the set of real numbers, $F_i(x)=x^2$, $⨂$ is addition over the reals, and $⨁$ is the $\max$ function.

The authors in [9] study sum-product queries under constraints on the rows of the join. They allow constraints of the form ${\sum }_{i\in C}{g}_i(q_i)\le \beta$, where $g_i:ℝ\to ℝ$ is an easy-to-compute function, and $\beta$ is a constant. They consider the problem of evaluating a sum-product query over those rows in the join that satisfy the given set of constraints. They show that with two constraints, such problems are not only NP-hard but also hard to approximate to within any multiplicative factor. Concretely, they show it is NP-hard to determine if there is a row $q$ in the join $J$ that satisfies the linear constraint ${\sum }_i{q}_i=0$. This is via a reduction from the Partition problem, where we want to determine if a given set of positive integers can be partitioned into two sets whose sums are equal. Thus, it is a weak NP-hardness result [6]. The linear constraint ${\sum }_i{q}_i=0$ is equivalent to the two linear inequality constraints ${\sum }_i{q}_i\ge 0$ and ${\sum }_i{q}_i\le 0$.

On the other hand, the authors in [9] show that with just one inequality constraint, and some additional technical assumptions, there is a randomized approximation scheme for sum-product queries that guarantees a multiplicative $(1+ϵ)$-approximation, for any given parameter $ϵ>0$. For instance, they use this general result to get a polynomial-time $(1+ϵ)$-approximation for the following counting problems:

1. 1.

   Count the number of rows in the join that lie in a given half space ${\sum }_i{a}_i{q}_i\le \beta$.

2. 2.

   Count the number of rows in the join that lie within a given ball ${\sum }_i{(q_i-y_i)}^2\le r^2$ (centered at point $y$ and having radius $r\ge 0$).

The authors in [12] study the $k$-means problem, and show how the $k$-means++ algorithm [3] for constructing a coreset can be implemented in the relational setting, thus deriving an $O(1)$-approximation for the $k$-means problem. Their core technical result is a polynomial-time sampling algorithm that, given a set $c_1,c_2,\mathrm{\dots },c_j$ of centers in ${ℝ}^{|C|}$, outputs a row $q\in J$ with probability proportional to the square of the Euclidean distance of $q$ to the nearest center. This sampling result is surprising given the hardness of closely related problems. In particular, the problem of counting the number of rows in the join whose closest center is $c_1$ is NP-hard even for $j=2$, and hard to approximate to within any multiplicative factor for $j=3$. The technique of rejection sampling plays a key role in their sampling result.

Very recently, the authors in [5] present fast deterministic and randomized relational approximation algorithms for the $k$-median and $k$-means clustering problems assuming the dimension $d$ is a constant. The authors in [4] present a method for constructing a coreset for certain optimization problems in machine learning. The work that we have reviewed builds on a body of theoretical and experimental research on relational algorithms. We refer the reader to [9, 12, 5, 4] for surveys of this prior work.

From prior work, it is evident that in the relational setting, the study of the complexity of very fundamental geometric problems yields surprising answers. More of the terrain needs to be explored to form a better picture of the computational complexity. Motivated by this, we consider the following Distance to $k$-Subspace problem: Given a set $S=\{s_1,s_2,\mathrm{\dots },s_k\}$ of orthogonal unit vectors, compute the maximum Euclidean distance of a row in the join to $span(S)$, the subspace spanned by $S$. As a reminder, we are assuming an acyclic database. The Distance to Subspace problem is a basic primitive for other tasks including the subspace approximation problem [8]. We obtain the following results.

1. 1.

   We show, in Section 4, that the Distance to $k$-Subspace problem is NP-hard even for $k=1$.

2. 2.

   We present a polynomial-time $\sqrt{d}$-approximation for the Distance to $k$-Subspace problem. To do so, we introduce a generalization of the join and compute measures on that generalization. This is likely to be an algorithmic tool of independent interest. As a consequence of our technique, we show that the row rank of the join $J$ can be computed exactly in polynomial time. These results are presented in Section 3.

3. 3.

   Next, we ask if for constant $k$, we can get a multiplicative $(1+ϵ)$-approximation for the Distance to $k$-Subspace problem, for any $ϵ>0$. The distance of a row $q$ in the join from the given $k$-subspace can be written as $A(q)-B(q)$, where $A(q)$ and $B(q)$ are both non-negative polynomials. $A(q)$ and $B(q)$ can individually be maximized/minimized using prior work on sum-product queries, but obviously this does not, by itself, give us a way of maximizing the difference $A(q)-B(q)$.

   Instead, we keep track of all possible values of the pair $(A(q),B(q))$ in our dynamic program. However, there can be an exponential number of such pairs, as is to be expected for an NP-hard problem. We can keep track of suitably discretized values of $(A(q),B(q))$, but to get a polynomial-time algorithm using this approach, we need the instance to be well-conditioned in the following sense: the maximum 2-norm of rows in the join (that is, Distance to the $0$-Subspace) is at most polynomially larger than the Distance to the given $k$-subspace.

   Our main technical contribution here is to show that the Distance to $k$-Subspace problem can be reduced to polynomially many instances of the same problem that are well-conditioned. To obtain such a reduction, one tool we develop is a proof that there exists a $k$-subspace spanned by $k$ of the standard basis vectors that is “close” to any given $k$-subspace. Overall, our reduction gives us a $(1+ϵ)$-approximation (Section 4) for the Distance to $k$-Subspace problem.

4. 4.

   We observe, in Section 4, that our $(1+ϵ)$-approximation to Distance to $k$-Subspace can be used as a primitive to obtain a ${(2(1+ϵ))}^k$-approximation for finding a $k$-subspace that minimizes the maximum Euclidean distance to the join. When the point set is given explicitly (as opposed to implicitly via the join), this is well known as the $l_{\mathrm{\infty }}$-subspace approximation problem [14]. The running time of our algorithm is polynomial for constant $k$. Our approximation factor for subspace approximation is large, and this result serves to illustrate the usefulness of the Distance to Subspace approximation primitive, which is the main focus of this work.

We emphasize that our work addresses the regime where the number $d$ of features and the number $m$ of tables are part of the input, and are not treated as constants. We are primarily focussed on the approximation guarantee that we can get with polynomial running time; we do not explore further optimizations of the running time.

We say that our database of $m$ tables is acyclic if there is a tree $\tau$ with $O(m)$ nodes, each associated with one of our input tables, that has the following properties:

1. 1.

   Each table in the database is associated with at least one node.

2. 2.

   For each feature $i\in C$, the set of nodes whose tables contain $i$ induces a connected subgraph of the tree.

Note that for technical reasons, we allow a table to be associated with more than one node of the tree $\tau$. Given an acyclic database, such a tree $\tau$ can be computed in polynomial time; see for example [9].

Note that each row of the join $J=T_1\bowtie T_2\mathrm{\cdots }\bowtie T_m$ is formed by picking one row from each table associated with each node of $\tau$, such that the chosen rows are pairwise compatible, and then concatenating the chosen rows. For an acyclic database, it suffices to check compatibility between pairs of rows chosen from nodes that are neighbors in the tree $\tau$. This follows from the properties of an acyclic database. This is the crucial property of acyclic databases that allows one to evaluate certain queries on the join efficiently via dynamic programming.

For the purpose of dynamic programming, it will be convenient to view the tree $\tau$ as rooted. Furthermore, we can assume that each internal node of $\tau$ has exactly two children. This is without loss of generality: If there is a node $\alpha$ with exactly one child ${\alpha }^{\prime }$, we can make ${\alpha }^{\prime }$ the left child of $\alpha$ and add a right child whose table is a copy of $\alpha$’s. If a node $\alpha$ has $j>2$ children, then replace $\alpha$ with a complete binary tree with $j-1$ internal nodes and $j$ leaves, which will now correspond to the original $j$ children of $\alpha$. The table at each of the $j-1$ internal nodes will be a copy of the table at $\alpha$.

After applying these two operations, we have that each internal node of $\tau$ has exactly two children. The total number of nodes in $\tau$ is $O(m)$. The join is unchanged: we have merely added copies of some of the original tables. Finally, $\tau$ still witnesses the fact that the database is acyclic, as is readily checked. We will refer to $\tau$ as the join tree of the database.

For a node $\alpha$ in the tree $\tau$, we use $T_{\alpha }$ to denote the table at node $\alpha$, and $J_{\alpha }$ to denote the join of all the tables in the subtree rooted at $\alpha$. We “assign” each feature $i\in C$ to the highest node in tree $\tau$ whose table contains feature $i$ as a column. By highest, we mean the node closest to the root of $\tau$. Let ${\widehat{C}}_{\alpha }$ denote the set of features assigned to node $\alpha$, and $C_{\alpha }$ denote the set of features assigned to nodes in the subtree rooted at $\alpha$. For a row $r$ in table $T_{\alpha }$, we denote the set of rows in the join $J_{\alpha }$ that are compatible with $r$ by $J_{\alpha }\bowtie r$. The notation is reasonable as this set of rows is indeed the result of a join of $J_{\alpha }$ and a table containing the single row $r$.

Suppose that for each feature $i\in C$, we are given a function $V_i:ℝ\to {ℝ}^{\mu }$, where $\mu \ge 1$ is identical across all features. We assume that these functions are easily computed. In fact, for the application here, we assume that $V_i(x)$ is given explicitly for each value $x$ of feature $i$ that occurs in any of the input tables. For any any row $r$ in the join $J$, let $V(r)={\sum }_{i\in C}{V}_i(r_i)$. Finally, let $V(J)=\{V(r)|r\in J\}$.

One illustrative example is to let $V_i(x)=(0,0,\mathrm{\dots },\underset{i-\text{th entry}}{\underbrace{x}},\mathrm{\dots },0)\in {ℝ}^d$, where we recall that the feature set $C$ is $\{1,2,\mathrm{\dots },d\}$. Then for any row $r$ in the join $J$ of the tables, $V(r)={\sum }_{i\in C}{V}_i(r_i)=r$. Thus, $V(J)=J$. We will see more interesting examples shortly.

We are interested in computing measures of the point set $V(J)$. But this seems generally harder for $V(J)$ than for $J$. For example, there is a polynomial-time algorithm for computing ${\max }_{r\in J}{\Vert r\Vert }_2^2$ using sum-product queries. However, computing ${\max }_{q\in V(J)}{\Vert q\Vert }_2^2$ seems harder. Fortunately, we can show a positive result for the $||\cdot |{|}_{\mathrm{\infty }}$ norm.

We begin by showing that using the above implicit representation, we can efficiently maximize the $l_{\mathrm{\infty }}$ norm of the projection onto the orthogonal complement of the given $k$-subspace.

Our algorithm for computing $E_k$ is as follows. Let $proj(a,span(S))$ be the projection of a vector $a$ on the subspace spanned by $S$.

We state some useful properties of this algorithm:

We will use the new orthonormal basis $𝒫=\{p_1,p_2,\mathrm{\dots },p_k\}$ for $span(S)$. Therefore we will use the notation $span(𝒫)$ for the subspace $span(S)$ in the following sections.

Recall that $I\subseteq [d]$ is the set of indices corresponding to the standard basis vectors in $E_k$. For each $i\in I$, let ${\alpha }_i^{\ast }$ be the node in the join tree such that $i\in {\widehat{C}}_{{\alpha }_i^{\ast }}$. See Section 2 for a reminder of these concepts. Let $𝒜=\{{\alpha }_i^{\ast }|i\in I\}$; we use $𝒜=\{{\alpha }_1,{\alpha }_2,\mathrm{\dots },{\alpha }_{|𝒜|}\}$ to denote the elements of the set. We can write the join $J$ as

We therefore compute $\text{D}(J\bowtie r_1\bowtie r_2\bowtie \mathrm{\dots }\bowtie r_{|𝒜|},span(𝒫))$ for each row combination $\{r_1,r_2,\mathrm{\dots },r_{|𝒜|}\}$, and return the maximum of these quantities. The number of row combinations is $O(n^k)$, which is polynomial as $k$ is a constant. In the remainder of Section 4, we fix a single row combination $\{r_1,r_2,\mathrm{\dots },r_{|𝒜|}\}$, and explain our approximation scheme for calculating $\text{D}(J\bowtie r_1\bowtie r_2\bowtie \mathrm{\dots }\bowtie r_{|𝒜|},span(𝒫))$. We will continue to use $J$ to denote the new join. For each $1\le i\le |𝒜|$, we delete all rows in the table $T_{{\alpha }_i}$ except $r_i$. Let $r^{\ast }=r_1⨝r_2⨝\mathrm{\dots }⨝r_{|𝒜|}$.