In computational geometry, dimensionality is a curse. Take the (approximate) nearest neighbor search problem as an example: 1D easy peasy, 2D a whole new level, and \(\log(n)\)-D a completely different world.
Let’s restrict ourselves to low-dimensional spaces. (High-dimensional spaces are too hard for me.) To set the stage for what I will be writing about, let’s ask: Is there any way to reduce a problem in \(\mathrm{R}^d\) for any constant \(d\geq 2\) to 1D? It’s a bold question, and I am definitely NOT the first asker. How about a bolder question: reducing a dynamic problem in \(\mathrm{R}^d\), where points are inserted/deleted dynamically, to a dynamic problem in 1D?
I doubt if we will ever get satisfying answers to these questions. However, locality-sensitive orderings (LSO), the subject of this post, provides a very good answer to both questions: it basically reduces a problem in 2D or above to 1D, even in the dynamic setting. This was eye-opening when I first saw LSO. Over the last few years, I have been trying to understand LSO and extending it to a more general setting of doubling metrics. We have made progress in this direction, which I will also include in this post.
1. What is a Locality-Sensitive Ordering?
Locality-sensitive ordering (LSO) was introduced in a remarkable paper by Chan, Har-Peled, and Jones in 2018. The formal definition is somewhat cryptic, and it took me a while to internalize it. By “a while,” I mean “a long while.”
Locality-sensitive ordering (LSO) in \(\mathbb{R}^d\): Given a point set \(P \in \mathbb{R}^d\), an \(\epsilon\)-LSO is a set \(\Sigma\) of linear orderings such that for every two points \(x,y \in P\), there exists an ordering \(\sigma \in \Sigma\) such that for every point \(z \in \sigma[x,y]\):
\[\min\{\lVert xz\rVert_2, \lVert yz\rVert_2\} \leq \epsilon \cdot \lVert xy \rVert_2 \qquad (1)\]
Here \(\sigma[x,y]\) denotes all the points between (and including) \(x\) and \(y\) in the ordering \(\sigma\). Ordering \(\sigma\) is called the canonical ordering of the pair \((x,y)\).
Equation (1) essentially says that every point in \(z\in \sigma[x,y]\) is either close to \(x\) or to \(y\) relative to the distance \(\lVert xy\rVert_2\). Therefore, one can read the definition of LSO as: for every two points \(x,y\), there exists an ordering \(\sigma\in \Sigma\) such that all the points between \(x\) an \(y\) in \(\sigma\) are close to \(x\) or \(y\). Note that Equation (1) implies that every point \(z\in \sigma[x,y]\) is in one of the two balls \(B(x,\epsilon \cdot \lVert xy \rVert_2 )\) and \(B(y,\epsilon \cdot \lVert xy \rVert_2 )\). It is possible that some points in the two balls are not in \(\sigma[x,y]\), as illustrated below.
Figure 1: A canonical ordering \(\sigma\) of \(x\) and \(y\), and the two balls \(B(x,\epsilon \cdot \lVert xy \rVert_2 )\) and \(B(y,\epsilon \cdot \lVert xy \rVert_2 )\).
Remarkably, the cryptic definition of LSO could be used to reduce a problem in \(\mathbb{R}^d\) to a problem on the (1D) line \(\mathbb{R}\). Many problems that are hopelessly complicated on the plane (2D) become very simple, if not trivial, in 1D. This makes LSO a powerful reduction; we will see this in some applications below.
The main result of Chan, Har-Peled, and Jones is that one can construct an \(\epsilon\)-LSO with a constant number of orderings in \(\mathbb{R}^d\) when \(\epsilon\) and \(d\) are constant.
Theorem 1 (Chan, Har-Peled, and Jones): For every \(\epsilon \in (0,1)\) and any given point set \(P \in \mathbb{R}^d\), one can construct an \(\epsilon\)-LSO for \(P\) with \(O_{\epsilon,d}(1)\) orderings.
I will use \(O_{\epsilon,d}\) notation to hide a dependency on \(d\) and \(\epsilon\). The precise dependency on \(\epsilon\) and \(d\) in the size of \(\Sigma\) is \(O(\epsilon^{-d}\log(1/\epsilon))\). This paper relaxes the definition of LSO slightly, and improves the size of \(\Sigma\) by a factor of \(1/\epsilon\).
It’s time to see LSO in action. The applications of LSO are listed in increasing order of sophistication. The last two applications really set LSO apart from other data structures. A good point to keep in mind is that all of these problems are much easier in 1D.
1.1. Closest pairs and neighbors
Let’s look at the classical closest pair problem: Given a point set \(P\in \mathbb{R}^d\), find a pair of points whose distance is smallest among all the pairs of points in \(P\). In 1D, the two points in the closest pair are next to each other. The same is true for LSO:
Observation 1: Let \(\Sigma\) be an \(\epsilon\)-LSO of a point set \(P \in \mathbb{R}^d\) for some \(\epsilon < 1\). Let \((x,y)\) be the closest pair in \(P\). Then \(x\) and \(y\) are adjacent in its canonical ordering \(\sigma\).
This is because for any \(z\in \sigma[x,y]\) such that \(\lVert xz\rVert_2 \leq \epsilon \lVert xy\rVert_2\) for \(\epsilon < 1\), then \(z = x\) since \((x,y)\) is the closets pair. Observation 1 means that if we are given a \(1/2\)-LSO \(\Sigma\), then to find a closets pair, all we have to do is checking adjacent pairs in every ordering in \(\Sigma\), and there are only \(O_{d}(n)\) such pairs.
A bit more sophisticated example along the same line of reasoning is \((1+\epsilon)\)-approximate nearest neighbor, \((1+\epsilon)\)-ANN. A \((1+\epsilon)\)-ANN of a point \(x\in P\) is another point \(y \in P\) such that:
\[\lVert xy\rVert_2\leq (1+\epsilon)\lVert xx^*\rVert_2,\]
where \(x^*\not= x\) is the closest point of \(x\) in \(P\).
Observation 2: Let \(\Sigma\) be an \(\epsilon\)-LSO of a point set \(P \in \mathbb{R}^d\) for some \(\epsilon < 1\). Then for any point \(x\), there exists an ordering \(\sigma\in \Sigma\) such that one of its (at most two) neighbors \(y \in \sigma\) is a \((1+\epsilon)\)-ANN.
The ordering \(\sigma\) in Observation 2 is the canonical ordering of the pair \((x,x^{\ast})\), and any point \(y \in \sigma[x,x^{\ast}]\) is a \((1+\epsilon)\)-ANN of \(x\); one of them is a neighbor of \(x\) in \(\sigma\).
Observation 2 gives us a simple linear time algorithm to find a \((1+\epsilon)\)-ANN of all the points in \(P\) given its \(\epsilon\)-LSO \(\Sigma\): checking all neighboring pairs in \(\Sigma\).
1.2. Spanners
A spanner of a point set \(P\in \mathbb{R}^d\) is an edge-weighted graph \(H\) with vertex set \(P\), and for every edge \((x,y)\in E(H)\), its weight in \(H\) is exactly \(\lVert xy\rVert_2\). \(H\) is a \((1+\epsilon)\)-spanner if:
\[d_H(x,y) \leq (1+\epsilon)\lVert xy\rVert_2 \qquad \text{for every pair }(x,y)\in P\times P\]
The goal is to construct a \((1+\epsilon)\)-spanner for any given point set \(P\) with \(O_{\epsilon,d}(n)\) edges. The distance preservation factor \(1+\epsilon\) is called the stretch.
To describe a spanner \(H\), we simply specify the edge set of \(H\); the weight of every edge is automatically set to be the Euclidean distance of its endpoints. There are so many ways to construct a \((1+\epsilon)\)-spanner. Here we construct it from an \(\epsilon\)-LSO. Can you guess? Check your answer by clicking on the text below:
Spanner from LSO:
Take the union of all orderings in the LSO: add an edge (x,y) to H if x and y are adjacent in some ordering.
Clearly \(\lvert E(H)\rvert = O_{\epsilon,d}(n)\) given an \(\epsilon\)-LSO with \(O_{\epsilon,d}(1)\) orderings. Showing that the distance is preserved up to \((1+\epsilon)\) is bit tricker and induction will work.
Lemma 1: \(H\) is a \((1+5\epsilon)\)-spanner when \(\epsilon \leq 1/10\).
Proof: Consider an arbitrary pair of points \((x,y)\). By induction on \(\lVert xy\rVert_2\), we assume that the distance between every pair \((a,b)\) such that \(\lVert ab\rVert_2 < \lVert xy\rVert_2\) is preserved up to \((1+5\epsilon)\) in \(H\).
Let \(\sigma\) be the canonical ordering of \((x,y)\). Then (some thought is needed to see this) there exist two points \(z_x\not= z_y\in \sigma[x,y]\) such that:
- \(\lVert xz_x\rVert_2 \leq \epsilon \lVert xy\rVert_2\) and \(\lVert yz_y\rVert_2 \leq \epsilon \lVert xy\rVert_2\).
- \(z_x\) and \(z_y\) are adjacent in \(\sigma\).
(It is possible that \(z_x = x\) and \(z_y = y\).) By triangle inequality:
\[\lVert z_xz_y\rVert_2 \leq (1+2\epsilon)\lVert xy\rVert_2\]
Since \(\epsilon < 1\), both \(\lVert xz_x\rVert_2\) and \(\lVert yz_y\rVert_2\) are smaller than \(\lVert xy\rVert_2\), and therefore, by induction:
\[d_H(x,z_x) \leq (1+5\epsilon)\lVert xz_x\rVert_2 \leq (1+5\epsilon)\epsilon \lVert xy\rVert_2\]
The same holds for \(yz_y\): \(d_H(x,z_y) \leq (1+5\epsilon)\epsilon \lVert xy\rVert_2\). Since \(z_x\) and \(z_y\) are adjacent in \(\sigma\), there is a direct edge \((z_x,z_y) \in H\), and therefore \(d_H(z_x,z_y) = \lVert z_xz_y\rVert_2\). Thus, we have:
\[d_H(x,y) \leq d_H(x,z_x) + d_H(z_x,z_y) + d_H(z_y,y) \leq \left((1+5\epsilon)2\epsilon + (1+2\epsilon)\right) \lVert xy\rVert_2 \leq (1+5\epsilon) \lVert xy\rVert_2\]
when \(\epsilon \leq 1/10\).
1.3. Fault-Tolerant Spanners
A \((1+\epsilon)\)-spanner \(H\) of a point set \(P\in \mathbb{R}^d\) is \(f\)-vertex-fault-tolerant (\(f\)-VFT) if for any subset \(F\subseteq P\) of at most \(f\) points, \(H\setminus f\) remains a \((1+\epsilon)\)-spanner of \(P\setminus F\). In other words, deleting at most \(f\) points from \(P\) and \(H\) still leaves us with a \((1+\epsilon)\)-spanner of the remaining points. Points in \(F\) are called faulty points.
When I first learned about the concept \(f\)-vertex-fault-tolerant \((1+\epsilon)\)-spanner and tried to think how I would construct one, I got nowhere. And existing constructions in the literature are not clean either.
One can see that any vertex in an \(f\)-VFT must have a degree at least \(f+1\), since otherwise, by deleting all the neighbors of a vertex \(v\) with a degree at most \(f\), we no longer can preserve distances from \(v\) to other points. Therefore, \(\Omega(n\cdot f)\) edges are needed, and \(O(nf)\) is the number of edges we aim to get.
1D case: For 1D, constructing a \(f\)-VFT spanner is indeed very simple (though not trivial), and you can get an exact spanner (\(\epsilon = 0\)) with \(O(n\cdot f)\) edges. Click below to see the answer.
f-VFT in 1D:
For every point p, add (at most 2f+2) edges from p to its f+1 predecessors and f+1 successors on the line.
The number of edges is at most \(2nf = O(nf)\).
To see fault tolerance, observe that for any two non-faulty points \(x\) and \(y\), if the number of points between them is at most \(f\), then \(x\) and \(y\) will have a direct edge. Otherwise (some moments of thought here), there will be a path from \(x\) to \(y\) “along the line” that only contains non-faulty points. Thus, the stretch is \(1\).
Higher dimensions: Now you can probably guess how to construct an \(f\)-VFT \((1+\epsilon)\)-spanner from an \(\epsilon\)-LSO \(\Sigma\): applying the 1D construction to each ordering \(\sigma \in \Sigma\). Easy peasy!
To show fault tolerance, given a faulty set \(F\), one simply deletes \(F\) from \(\Sigma\), getting \(\Sigma’\). Two key observations: (1) \(\Sigma’\) is an \(\epsilon\)-LSO of \(P\setminus F\) and (2) every two adjacent points in any ordering \(\sigma’\in \Sigma’\) is connected by an edge in \(H\setminus F\). Thus, the argument in Lemma 1 (for spanners) above implies that \(H\setminus F\) is a \(1+\epsilon\)-spanner of \(P\setminus F\).
1.4. Reliable Spanners
This application is (much?) more sophisticated, and it’s COOL!
The notion of a reliable spanner (introduced by Bose, Dujmović, Morin, and Smid) is so strong that I could not believe that it existed the first time I learned about it. As discussed above, an \(f\)-VFT spanner needs \(\Omega(nf)\) edges, so if the number of faults \(f = \Omega(n)\), we have no choice but to add almost all pairwise edges. But there are scenarios where \(f = \Omega(n)\), say, a storm ravages the electrical grid. Can we still have a notion of spanners that can provide some sort of guarantees where \(\Omega(n)\) failures occur? For the notion to be useful, it must be possible to construct one with \(\tilde{O}(n)\) edges. And here it is:
Reliable Spanner: A \((1+\epsilon)\)-spanner \(H\) for a point set \(P \in \mathbb{R}^d\) is a \(\nu\)-reliable if for every faulty set \(F\subseteq P\), there exists another set \(F^+\supseteq F\), called the faulty extension of \(F\), such that:
- \(\lvert F^+ \rvert\leq (1+\nu) \lvert F \rvert\).
- for every \(x,y \not\in F^+\), their distance is preserved in \(H[P\setminus F]\):
\[d_{H[P\setminus F]}(x,y) \leq (1+\epsilon)\lVert xy\rVert_2\]
Think of the faulty extension \(F^+\) as points in the vicinity of \(F\), which are also affected. We want (1) the faulty extension to be not bigger than \(F\) and (2) as long as points that are not in the vicinity of the faulty set, their distances are preserved.
If you know expander graphs, then the kind of guarantee by reliable spanners is very similar to that of expanders. Indeed, the paper introducing the spanner made this connection explicit. What is interesting about a reliable spanner is that you can construct one whose size does not depend on \(F\). Therefore, you still can get a meaningful guarantee even when \(F = \Omega(n)\).
Theorem 2 (Buchin, Har-Peled, Oláh): For every \(\epsilon, \nu \in (0,1)\), and any point set \(P \in \mathbb{R}^d\), one can construct a \(\nu\)-reliable \((1+\epsilon)\)-spanner for \(P\) with \(O_{\epsilon,d,\nu}(n\log(n)(\log\log n)^6)\) edges.
As you might well guess, the construction used LSO to reduce the 1D case. Even in 1D, constructing reliable spanners remains very non-trivial. In this case, a lower bound of \(\Omega(n\log n)\) on the number of edges was established by Bose, Dujmović, Morin, and Smid.
2. LSO in doubling (and other) metrics
The work of Chan, Har-Peled, and Jones opened the possibility of having an \(\epsilon\)-LSO for metrics of bounded doubling dimension. In this paper with Arnold Filtser, we worked out an \(\epsilon\)-LSO for doubling metrics.
Theorem 3 (LSO in doubling metrics): For every \(\epsilon \in (0,1)\) and any given point set \(P\) in a metric of doubling dimension \(d\), one can construct an \(\epsilon\)-LSO for \(P\) with \(O_{\epsilon,d}(1)\) orderings.
The same paper introduced different variants of LSOs for different types of metric spaces. If you are curious about these variants, do check out the paper. In a follow-up work, Arnold worked out LSO for high-dimensional spaces.
3. Dynamic LSO
In the dynamic setting, the point set \(P\) is dynamically changed by point insertions or deletions. The goal is to update the geometric construction (e.g., a spanner) when a point is deleted from or inserted to \(P\) in \(o(n)\) time, and ideally in \(O(\log n)\) time.
In all of the applications in Section 1, except reliable spanners, one can easily maintain the solution \(O(\log n)\) time in 1D. All of these problems become extremely difficult even in 2D in the dynamic setting. On the other hand, if one can dynamize an LSO, one could get a reduction to the simple 1D case. Therefore, as Chan, Har-Peled, and Jones observed, a dynamic LSO would become a powerful tool for solving dynamic problems. Surprisingly, their construction of LSO in \(\mathbb{R}^d\) can be easily dynamized, exploiting Euclidean geometry.
Theorem 4 (Chan, Har-Peled, and Jones): For any point set \(P\in \mathbb{R}^d\) undergoing dynamic updates (point insertions/deletions), one can maintain an \(\epsilon\)-LSO \(\Sigma\) in \(O_{\epsilon,d}(\log n)\) time per point update.
My PhD student An La and I are interested in dynamizing the LSO in doubling metrics in Section 2. Unlike the Euclidean case, points in doubling metrics are not equipped with “coordinates.”Instead, one assumes a distance oracle access: given two points, we can call the oracle to compute their distance in \(O(1)\) time. (In the Euclidean case, simply computing the Euclidean distance from their coordinates would realize the oracle.)
We aim to get \(O(\log n)\) time per point update in doubling metrics. This means that when a new point \(p\) arrives, we can only compute the distance from \(p\) to \(O(\log n)\) other points to do the update. In Euclidean metric, in addition to distance computation, one could figure out the relative location of a point w.r.t other points by performing bitwise operations on the coordinate; the dynamic LSO of Chan, Har-Peled, and Jones used this idea. Our new paper shows that distance computation is enough for getting a dynamic LSO. As a result we get a host of new dynamic algorithms for various problems in doubling metrics.
Theorem 5 (Dynamic LSO in doubling metrics): For every \(\epsilon\in (0,1)\) and \(d\), we can maintain an \(\epsilon\)-LSO for a dynamic point set \(P\) in a doubling metric of dimension \(d\) in \(O_{\epsilon,d}(\log n)\) time per update.
Our construction of the LSO is very sophisticated. It took “us” a long while to figure out all the missing components (by “us”, I mean my student An La, who came up with all of these). I would love to see a simpler construction. My excuse is that a much simpler problem, namely maintaining a dynamic net tree, currently does not have a simple solution. Let’s make it an open problem:
Open problem: Design a simple dynamic algorithm for maintaining a net tree in doubling metrics with \(O(\log n)\) time per update.