Color Distance Oracles and Snippets: Separation Between Exact and Approximate Solutions

Let $𝐌$ be a metric space with distance function $d(\cdot ,\cdot$). Let $S\subseteq 𝐌$ be a set of points where $\left|S\right|=n$. Let $𝒞$ be a set of colors. For sake of convenience we assume that $𝒞=[|𝒞|]$. Each point $p$ $\in$ $S$ has an associated color $c_p\in 𝒞$. For a color $c\in 𝒞$, let $P_S(c)=\{p\in S|c_p=c\}$. When $S$ is clear from context we abuse notation and denote $P(c)=P_S(c)$.

For sets of points $A,B\subset 𝐌$ and a point $p\in M$, let $d(p,A)={\min }_{p^{\prime }\in A}\{d(p,p^{\prime })\}$ and let $d(A,B)={\min }_{p^{\prime }\in A}\{d(p^{\prime },B)\}={\min }_{p^{\prime }\in A,\widehat{p}\in B}\{d(p^{\prime },\widehat{p})\}$. We extend the definition of $d$ to inputs of colors as follows. For colors $c,c^{\prime }\in 𝒞$ and point $p\in 𝐌$, let $d(p,c)=d(p,P(c))$ and let ${\delta }_{c,c^{\prime }}=d(c,c^{\prime })=d(P(c),P(c^{\prime }))$. We say that ${\delta }_{c,c^{\prime }}$ is the color distance between $c$ and $c^{\prime }$. A natural problem is to construct a color distance oracle (CDO), which is defined as follows.

In this paper we consider metrics defined by locations in an array of size $s$, and so the metric is the set¹¹1Throughout this paper for a positive integer $k$ we denote $[k]=\{1,2,,\mathrm{\dots },k\}$. $[s]$, and the distance function of two points $p$ and $q$ is $d(p,q)=\left|p-q\right|$.

A natural generalization of a colored set is to allow each $p\in S$ to be associated with a nonempty set of colors $c(p)\subseteq 𝒞$, and in such a case $S$ is said to be multi-colored. This version of the CDO problem is called the multi-color distance oracle (MCDO) problem. In general, representing $c(p)$ costs $\mathrm{\Theta }(|c(p)|)$ space by explicitly listing all colors in $c(p)$. Thus, the input size is $n={\sum }_{p\in S}|c(p)|$.

Nevertheless, there are interesting cases in which the lists of colors for each point are not required to be given explicitly. One such example, which we focus on, is when for every two colors $c,c^{\prime }\in 𝒞$, either one of the sets $P(c)$ and $P(c^{\prime })$ contains the other, or the two sets are disjoint. In such a case, we say that $𝒞$ has a color hierarchy with respect to $S$ (a formal terminology is that ${\{P(c)\}}_{c\in 𝒞}$ is a laminar family), represented by a rooted forest (i.e., each tree has a root) $T_S$ of size $O(|𝒞|)$. Each color $c$ is associated with a vertex $u_c$ in $T_S$, such that the descendants of $u_c$ are exactly all the vertices $u_{c^{\prime }}$ whose color $c^{\prime }$ satisfies $P(c^{\prime })\subseteq P(c)$. We convert the forest $T_S$ to a rooted tree by adding a dummy root vertex and making the dummy root the parent of all of the roots of the trees in the forest.

With the aid of $T_S$, a multi-colored set $S$ that admits a color hierarchy can be represented using only $O(n+|𝒞|)$ machine words, because it suffices to store $T_S$ and associate with each point $p$ just one color $c$ (the color with the lowest corresponding vertex in $T_S$); the other colors of $p$ are implicit from $T_S$ (the colors on the path from $u_c$ to the root of $T_S$). Notice that $|𝒞|>n$ implies that there are at least two colors with the same point set. Thus, we make the simplifying assumption that all colors have different point sets²²2If we happen to have several colors with the same point set, we ignore all of them but one during preprocessing, and use a straightforward mapping from the original coloring to the reduced coloring during query time., and so the input size is $O(n)$.

Thus, a natural extension of Problem 1 is the following.

Let $a$ and $b$ be real numbers such that the preprocessing and query times of a MCDOCH algorithm are $\tilde{O}(n^a)$³³3Throughout this paper we use the notation $\tilde{O}(\dot{)}$ to suppress sub-polynomial factors. and $\tilde{O}(n^b)$, respectively. A tradeoff algorithm for the MCDOCH problem was presented in [17], where given parameter $1\le \tau \le n$, the query time is $\tilde{O}(n^b)=\tilde{O}(\tau )$ and the preprocessing time is $\tilde{O}(n^a)=\tilde{O}(n^2/\tau )=\tilde{O}(n^{2-b})$. When ignoring sub-polynomial factors, this upper bound tradeoff is given by $a+b=2$ where $0\le b\le 1$ and $1\le a\le 2$. Notice that the same tradeoff applies to the CDO problem.

In addition to the tradeoff algorithms, [17] proved a 3SUM based conditional lower bound (CLB) tradeoff⁴⁴4The CLB tradeoff stated here is straightforward to derive from the statement of Theorem 4 in [17]. of $a+2b\ge 2$ for the CDO problem (and hence for the MCDOCH problem), even when $𝐌$ is defined by locations in an array. Their CLB holds also for approximate versions of the CDO problem (see Theorem 8 in [17]), where for a fixed $\alpha >1$, the answer to a color distance query between $c$ and $c^{\prime }$ is required to be between ${\delta }_{c,c^{\prime }}$ and $\alpha \cdot {\delta }_{c,c^{\prime }}$.

By designing a reduction from the snippets problem to the MCDOCH problem, [17] were able to design an algorithm for the snippets problem with essentially the same tradeoff: for a chosen parameter $1\le \tau \le |T|$ their snippets algorithm uses $\tilde{O}({|T|}^2/\tau )$ preprocessing time and answers queries in $\tilde{O}(|P_1|+|P_2|+\tau )$ time. The main idea in the reduction is to construct the suffix tree of $T$, assign a color to each vertex in the suffix tree, and for each leaf $\mathrm{\ell }$ in the suffix tree, the corresponding location in $T$ is assigned all of the colors on the path from $\mathrm{\ell }$ to the suffix tree root. It is straightforward to see that the colors define a hierarchy and that $T_S$ is exactly the suffix tree.

The upper bound curve of $a+b=2$ and the CLB tradeoff of $a+2b\ge 2$ form a complexity gap for the snippets and (approximate) CDO problems, which was left open by [17]. Moreover, based on the combinatorial Boolean Matrix Multiplication (BMM) hypothesis, [17, Theorem 8] implies that any algorithm that beats the $a+b=2$ curve, even for approximate versions, must use non-combinatorial techniques, such as fast matrix multiplication (FMM) algorithms.

We remark that the CLB tradeoff given in [17] is based on a reduction from a SetDisjointness problem to the (approximate) CDO problem, and at the time [17] was published, the SetDisjointness problem was known to exhibit the same upper bound tradeoff and 3SUM based CLB tradeoff [18]. However, recently Kopelowitz and Vassilevska-Williams [19] closed this complexity gap by, among other ideas, using FMM techniques. Thus, a natural question to ask is whether FMM can assist in obtaining improved algorithms for CDO problems.

We close the complexity gap for the $(1+\epsilon )$ approximation versions of CDO and $MCDOCH$, where $𝐌$ is defined by locations in an array. Formally, the problems are defined as follows.

Our first main result is a new tradeoff algorithm for ACDO, which is stated by the following theorem. Notice that the time complexities presented are dependent on $\omega \ge 2$, which is the exponent of $n$ in the runtime of the fastest FMM algorithm on two squared matrices of size $n\times n$. The currently best upper bound on $\omega$ is given by [2]. However, for clarity, we choose to express our tradeoffs in terms of $\omega$. We remark that ACDO is a special case of AMCDOCH, and so Theorem 6 implies Theorem 5. However, Theorem 5 is used in the proof of Theorem 6, so we explicitly state both theorems.

Combining Theorem 6 with the reduction of the snippets problem to the MCDOCH problem given in [17], we obtain the following tradeoff for a $1+\epsilon$ approximation version of the snippets problem.

We remark that it is straightforward to adapt our ACDO and AMCDOCH algorithms (and hence our new approximate snippets algorithm) to return the two points (one of each color) that define the distance being returned (or the locations of the two patterns in the approximate snippets problem). For details, see the full version [12].

We remark that by combining the reduction given in [17, Theorem 8] from SetDisjointness to the CDO problem with the CLBs for SetDisjointness given in [19, Theorem 6] for the case of $\omega =2$ (which some researchers believe should be obtainable), Theorems 5, 6 and 7 are all conditionally optimal⁵⁵5For Theorems 5 and 6, the optimality follows directly from applying [17, Theorem 8] and [19, Theorem 6]. For Theorem 7, the optimality follows since an approximate solution for the snippets problem can be used to solve ACDO on an array as follows: treat each color as a character, and then the array becomes a string. Preprocess the string using the snippets algorithm, so that given an ACDO query on two colors $c,\widehat{c}$, query the snippets algorithm with patterns $P=c$ and $\widehat{P}=\widehat{c}$. Thus, the ACDO lower bound applies to approximate snippets. (up to subpolynomial factors). A natural question to ask is whether one can design exact algorithms with the same tradeoff bounds. We provide evidence that this is not possible, based on a strong version of the popular all-pairs shortest paths (APSP) conjecture [7], thereby demonstrating a separation between CDO and ACDO.

The Strong-APSP hypothesis, introduced by Chan, Vassilevska-Williams and Xu [7], states that for a graph with $\widehat{n}$ vertices⁶⁶6We use $\widehat{n}$ to differentiate from $n=|S|$ in the various CDO problems., even if all of the edge weights are in⁷⁷7Actually, in [7] the weights are bounded by ${\widehat{n}}^{3-\omega }$, but since $\omega \ge 2$ we can bound the weights by $\widehat{n}$. $[\widehat{n}]$, APSP still does not have a truly subcubic algorithm. A closely related problem to APSP is the $(min,+)$-matrix product problem, where the input is two $\widehat{n}$ by $\widehat{n}$ matrices $A=\{a_{i,j}\}$ and $B=\{b_{i,j}\}$, and the output is the matrix $D=\{d_{i,j}\}$ where $d_{i,j}={\min }_{1\le k\le \widehat{n}}(a_{i,k}+b_{k,j})$. Shoshan and Zwick [24] showed that solving APSP with weights $[M]$ is equivalent (in the sense of having the same runtime) to solving $(min,+)$-matrix product with entries in $[O(M)]$. Thus, the Strong-APSP hypothesis implies that there is no truly subcubic time $(min,+)$-matrix product algorithm even when all of the entries are in $[\widehat{n}]$.

By reducing $(min,+)$-matrix product with entries in $[\widehat{n}]$ to MCDO, we are able to prove the following CLB in Section 6, which matches the upper bound given in [17].

Moreover, we are able to leverage the ideas used in the proof of Theorem 8 to reduce $(min,+)$-matrix product with entries in $[\widehat{n}]$ to CDO via a randomized reduction, thereby obtaining a CLB under the assumption that the Strong-APSP hypothesis holds even for randomized algorithms (either in expectation or with high probability).

The proof of Theorem 9 is based on the proof of Theorem 8, combined with probabilistic techniques in order to create instances that are not multi-colored. Due to space considerations, the proof is given in the full version [12]

Theorem 9 combined with Theorem 5 implies that the exact version of CDO is strictly harder than the approximate version. Moreover, we remark that the CLBs for CDO apply also to the snippets problem, since the special case of $𝐌$ defined by locations in an array is captured by the snippets problem when $P_1$ and $P_2$ are each a single character. Thus, the CLB of Theorem 9 applies also to the snippets problem, and so the exact version of the snippets problem is also strictly harder than the approximate version.