Well, in this blog post we are going to review several papers and understand the techniques that are utilized in order to tackle several problems related to areas such as nearest neighbor problems, the facility location problem, and so on.

I am going to study and explain three papers which have led to a dynamic solution for the facility location problem.

Ok, I think in the series of the several papers that I am going to review, the data structure designed by James Lee and his co-author is a revealing piece.

Nearest-neighbor search (NNS) is the problem of preprocessing a set $S$ of $n$ points lying in a huge (possibly infinite) metric space $(M,d)$ so that, given a query $q \in M$, one can efficiently locate the nearest point to $q$ among the points in $S$.

Let $q$ be the query and $a \in S$ the closest point to $q$ in $S$. Then a $(1+\varepsilon)$-NNS algorithm is one which, given $q$, returns some $s \in S$ such that

So while it is NP-hard to return the nearest neighbor, it is worthwhile to examine whether we can approximate the answer in an efficient manner. Lee and his co-author used a very interesting classic idea: move from coarse to fine approximation. In a sense, their data structure is analogous to the binary search algorithm, with an extra twist and turn. Moreover, they employ the idea of doubling dimension as a means to count the complexity of the algorithm that they propose.

The doubling dimension of a metric space $(X,d)$, denoted in this post by $\dim(X)$, is the minimum value $\rho$ such that every set in $X$ can be covered by $2^{\rho}$ sets of half the diameter. (The diameter of a set $S \subseteq X$ is

)

A metric space is called doubling if its doubling dimension is $O(1)$. This notion of dimension measures the “volume growth” of $X$.

So, following the paper, we want to prove the following result:

Theorem. Let $(S,d)$ be a finite metric space with doubling dimension $\dim(S)$ and aspect ratio $\Delta=\Delta_S$, defined as

Then there exists a dynamic data structure for approximate nearest-neighbor search with the following properties:

1. The data structure uses $O(n)$ space if $S$ is doubling.
2. It answers $(1+\varepsilon)$-nearest-neighbor queries in

time.

1. It supports insertions and deletions in

time.

Moreover, in most applications,

and therefore

The running time depends exponentially on $\dim(S)$. Furthermore, in the distance-oracle model, where access to the ambient metric space is restricted to distance queries, this exponential dependence on the doubling dimension is necessary.

So let us first follow a simplified version of the data structure.

Let $(S,d)$ be the metric space against which queries are performed. For the sake of this informal discussion, assume that the minimum interpoint distance in $S$ satisfies

Under this assumption, the aspect ratio $\Delta$ is simply the diameter of $S$.

In what follows, for a subset $R\subseteq S$ and a point $x\in M$, we define

Let $k=\log \Delta$, and for each $i=0,1,\ldots,k$, let $Y_i$ be a $2^i$-net of $S$. For every point $y\in Y_i$, define the set

where $\gamma$ is a constant to be specified later.

So what are we going to do here? We are providing details from coarse to fine for the underlying data structure! And $L_{y,i}$ gives us a means to search through the metric space. I would rather call them approximate $2^{i-1}$ neighbors of the given point. So we have a means of sparsifying the metric space, and we build a tree based on the sparsification. It is obvious that we can build the nets in a greedy manner.

Since $L_{y,i}\subseteq Y_{i-1}$, and $Y_{i-1}$ is a $2^{i-1}$-net, any two distinct points of $L_{y,i}$ satisfy

Hence, the minimum interpoint distance in $L_{y,i}$ is $2^{i-1}$.

Moreover, by the definition

every point of $L_{y,i}$ lies within distance $\gamma 2^i$ of the center $y$. Therefore, for any $z_1,z_2\in L_{y,i}$, the triangle inequality gives

Thus,

Consequently, the aspect ratio of $L_{y,i}$ is bounded by

which is a constant.

So, in order to count the number of children of any node in the tree, we use the doubling property and use that to count the number of children.

Lemma. Let $(S,d)$ be a metric space, and let $Y\subseteq S$. If the aspect ratio of the metric induced on $Y$ is at most $\alpha$, where $\alpha\ge 2$, then

Proof. Let

and

be the minimum and maximum interpoint distances in $Y$, respectively. Assume that

Notice that $Y$ is contained in a ball of radius

centered at any point of $Y$.

Applying the definition of doubling dimension iteratively, this ball (and hence $Y$) can be covered by

balls of radius

Each such ball can contain at most one point of $Y$. Indeed, if two distinct points of $Y$ were contained in the same ball, then by the triangle inequality their distance would be at most

contradicting the definition of $d_{\min}$.

Therefore,

When $S$ is a doubling metric, the Lemma implies that

where the hidden constant depends only on the choice of $\gamma$ (and the doubling dimension of $S$).

Furthermore, the top-level net $Y_k$ contains exactly one (arbitrary) point, which we denote by

Given a query point $q\in M$, we first set

Then, iteratively for

we find the point in

that is closest to $q$, and update $y$ to be this point for the next iteration.

If, at some stage, we reach a point such that

then we stop the procedure and output the current value of $y$. Otherwise, after completing all iterations, we output the final value

First, notice that the running time of this algorithm is at most

since finding the closest point to $q$ among a list $L_{y,i}$ takes constant time. This follows from the fact that every list has size

It remains only to prove that the output point $y$ is a $3$-approximation to the nearest neighbor. Let $a\in S$ be the true nearest neighbor of $q$. We need to show that

To this end, let $j$ be such that

but

i.e., the step in which the distance does not decrease by a factor of $2$. Since the closest $2^{j-1}$-net point to $a$ satisfies

the closest $2^{j-1}$-net point to $a$ is contained in $L_{y,j}$. Let $y^*\in Y_{j-1}$ be such that

We need to show that

In this case, we have $y^*\in L_{y,j}$. Using the triangle inequality,

Therefore, choosing

suffices.

This shows that the descent process “tracks” the closest net point to $a$. Now, we have

Hence,

Since

we conclude that

Therefore, $y$ is a $3$-approximate nearest neighbor of $q$.

Similar arguments show that if the algorithm terminates with

then $y$ is actually the closest point to $q$ in $S$, because we have a $1$-net and we have the closest point to $a$ in the set $L_{y,i}$.

For a technical reason, the above data structure does not support efficient deletions and might require space

The main remedy for these latter problems is to choose $Y_i$ to be a $2^i$-net of $Y_{i-1}$ rather than a $2^i$-net of $S$.

Let us get into the main algorithm.

Let

and call every value $r\in\Gamma$ a scale. Only $O(\log\Delta)$ of these scales are relevant; the remaining scales are trivial.

For every $r\in\Gamma$, let $Y_r$ be an $r$-net of $Y_{r/2}$. We define

for all scales

For every $r\in\Gamma$ and every $y\in Y_r$, …

so we are making the details more coarse by only having the nets in $Y_i$ instead of $S$.

For every $r\in\Gamma$ and every $y\in Y_r$, the data structure stores a list of the nearby points to $y$ among the $(r/2)$-net $Y_{r/2}$. This scale-$r$ navigation list of $y$ is defined as

where $\gamma>0$ is a universal constant.

So we are roughly halving the distance at each step.

Lemma. For every scale $r$, the following properties hold:

1. Covering: \(d(z,Y_r)<2r\) for every $z\in S$.

2. Packing: \(d(x,y)\geq r\) for every $x,y\in Y_r$ with $x\neq y$.

The proofs are easy, and the first one follows by induction. So, it adheres to our intuition of having a rougher estimation while also helping us to preserve space in our algorithm.

We also have the following lemma.

Lemma. The size of every navigation list is at most

which has the same proof as before.

The data structure maintains this point $y_{\mathrm{top}}$ and the cutoff scale

for the sake of bootstrapping most of the operations.

Third, for all scales

the net $Y_r$ is equal to $S$. Therefore, for scales

every point $x\in S$ has a trivial list

These trivial lists can be represented succinctly by storing, for every $x\in S$, a scale $r_x\in\Gamma$ below which all lists of $x$ are trivial. For the sake of analysis, define

Lemma. The cutoff scales satisfy

and

Consequently, every point has

non-trivial navigation lists.

The proof is easy.

Combining the above results, we obtain an upper bound on the total space required by the data structure. Specifically, the space complexity is

For each point $x\in S$, the non-trivial navigation lists of $x$ are stored using, for example, a balanced search tree. This requires linear space and supports the operations find, insert, and delete in logarithmic time.

It then follows from Lemma 2.3 that inserting a new navigation list for a point can be performed in time

Theorem. The size of the data structure is

words.

Proof. The proof bounds the size using a charging argument.

Definition. A subset $Z_r\subseteq Y_r$ is called non-proper if it contains only one point $x$ and

Otherwise, $Z_r$ is called proper.

Algorithm: Approx-NNS

Input: $q\in X$ and $\varepsilon>0$.

1. Set

and

1. While

and $Z_r$ is proper, do:

a. Set

b. Set

1. Return the point $z\in Z_r$ for which

is minimal.

Lemma. Let $a$ be a closest point to $q$ among $S$. Then every set $Z_r$ computed by Procedure Approx-NNS contains a point $z_r$ such that

Lemma. Procedure Approx-NNS outputs a point whose distance from $q$ is at most

Proof. Let $r^*$ be the value of $r$ at the end of the procedure. It suffices to prove that

because then the proof follows from the choice made in line 5 of the procedure.

There are two conditions in line 2 that may cause the while-loop to terminate. First, consider the case where

By the previous lemma, we know that

Combining the above inequalities, we obtain

Substituting this bound back into the previous inequality gives

as desired.

Consider now the case where $Z_{r^*}$ is non-proper. We may assume that

otherwise the claim is immediate.

For analysis, suppose we continue the procedure without the condition that $Z_r$ is proper. This process must terminate, since

while

Moreover, the returned point remains unchanged, because all further sets $Z_r$ for $r<r^$ contain the same single point as $Z_{r^}$. It is easy to see that the above analysis (including Lemma 2.4) also applies to the modified procedure. Therefore, both the modified and the actual procedure satisfy

In fact, if the procedure stops with a non-proper set $Z_r$, then it returns the unique closest point to $q$ in $S$. This follows by applying the same modified-procedure argument with an arbitrarily small $\varepsilon>0$.

Lemma. Procedure Approx-NNS runs in time

Proof. Since the distance between any two points of

is at least $r/2$, Lemma 1.2 implies that

A simpler bound is obtained by separately bounding the number of iterations of the procedure and the running time of a single iteration. For the first part, consider the number of iterations performed by the procedure.

Theorem. The data structure can be updated after inserting a point into $S$ in time

This update includes

distance computations.

Proof sketch. The main idea is that, regardless of how the nets were constructed, each $r$-net $Y_r$ can be updated after an insertion of a new point $q$ by either adding $q$ to $Y_r$ or leaving it unchanged.

This follows by induction on the scale $r$. For the base case, consider a sufficiently small scale $r$. By definition, $Y_r$ contains all points of $S$, and therefore $q$ must be added to this net.

For the inductive step, first assume that the update to $Y_{r/2}$ leaves it unchanged. In this case, $Y_r$ also remains unchanged. Otherwise, suppose that $q$ is added to $Y_{r/2}$. We then update $Y_r$ by adding $q$ to it if and only if

This guarantees that $Y_r$ remains an $r$-net of $Y_{r/2}$ (although other valid updates are also possible).

To decide whether

we use a set $Z_r$ that contains all points of $Y_r$ that are sufficiently close to $q$.

Recall that the net $Y_r$ is maintained only through its navigation lists. Therefore, adding $q$ to $Y_r$ requires constructing the scale-$r$ navigation list of $q$ and updating the scale-$2r$ navigation lists of nearby points. Both tasks are performed using the sets $Z_r$.

The proof uses induction on the scale $r$ to decide whether a new point $q$ should be added to the net $Y_r$.

Base case (smallest scale). At the finest scale, $Y_r$ contains all points of $S$ by definition. Therefore, the new point $q$ must be added to $Y_r$.

Inductive step. Assume that the update rule is correct for the smaller scale $r/2$. We consider two cases.

1. $q$ is not added to $Y_{r/2}$.

In this case, $q$ is already within distance less than $r/2$ of some point in $Y_{r/2}$. Hence, it is also covered at scale $r$, and there is no need to add $q$ to $Y_r$.

1. $q$ is added to $Y_{r/2}$.

Now we decide whether $q$ should also be added to $Y_r$. The condition is whether $q$ is sufficiently far from all existing points of $Y_r$:

If this condition holds, we add $q$ to $Y_r$. Otherwise, $Y_r$ remains unchanged.

This update rule preserves the invariant that $Y_r$ is an $r$-net of $Y_{r/2}$.

Step 3: Using $Z_r$ for efficient distance checks.

A naive check of the condition

would require computing the distance from $q$ to every point in $Y_r$, which is too expensive.

Instead, the algorithm maintains a local set $Z_r$ that contains all points of $Y_r$ that are sufficiently close to $q$. Since $S$ has bounded doubling dimension $\dim(S)$, the number of points that can exist in such a local neighborhood while maintaining the packing property of the net is bounded by

Therefore, it is sufficient to check the distance between $q$ and the points in $Z_r$. If no point in $Z_r$ is within distance $r$ of $q$, then

and we add $q$ to $Y_r$. Otherwise, $Y_r$ remains unchanged.

Step 4: Updating the navigation lists.

If $q$ is added to $Y_r$, the update of the data structure is not complete yet. The navigation lists, which connect points between consecutive scales, must also be updated.

First, we construct the scale-$r$ navigation list of $q$, which contains the nearby points of $q$ in the coarser net $Y_{2r}$.

Second, we update the scale-$2r$ navigation lists of all nearby points in $Y_{2r}$ by adding $q$ as one of their neighbors.

The set $Z_r$ is used to identify exactly the points whose navigation lists must be updated. Since $Z_r$ has size bounded by

the update remains local and can be performed efficiently.

The final update time is

The complexity can be understood as follows.

Local work. At each scale, the algorithm only examines the local set $Z_r$. By the doubling dimension bound,

Therefore, the distance computations and navigation-list updates performed at a single scale require

time.

Data structure overhead. The navigation lists are maintained using balanced search trees. Each insertion or update of a navigation list requires an additional

overhead. Therefore, the total update time is

Moreover, at each of the $O(\log\Delta)$ scales, the algorithm computes distances only to the

points in the corresponding local set $Z_r$. Hence, the total number of distance computations is

And the scale is handled automatically by the insertion update.

References

• R. Krauthgamer and J. R. Lee, Navigating Nets: Simple Algorithms for Proximity Search. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 798–807. PDF