4
$\begingroup$

If you wanted to know the shortest distance/path between two household addresses, which data structure(s) would you use to return the answer efficiently?

Say you are considering the set of all households in the United States (~100 million).

I am struggling to come up with a practical data structure considering the input size is so big. Dijkstra's seems too inefficient, but I'm guessing there is a way to preprocess the paths to make such a query possible.

$\endgroup$
6
$\begingroup$

This problem is well considered and learned in recent decades as every GPS device faces this problem.

In practice (AFAIK), the standard way of facing this problem is by the usage of distance oracles, which usually (or more correctly, used to) approximate the distance between every two nodes by keeping only a $k\times n$ distances tables for a well-selected $k$ vertices.

The lastest result I'm aware of, keep a data structure of size $O(kn^{1+1/k})$, answering queries in $O(1)$ time and giving a stretch (i.e. the return value $\delta$ is promised to suffice $d\leq \delta \leq d\cdot s$). of $2k-1$.

Alternatively, if you're looking for a stretch smaller than 2, I suggest looking at this paper.

$\endgroup$
2
$\begingroup$

This answer has a few drawbacks: it gives a $+2/4/6$ additive approximation to the correct answer, and it only applies to undirected, unweighted graphs. I think there is no comparable system known for weighted graphs or exact computations, but I could be wrong about that.

A $k$-emulator of an undirected, unweighted graph $G = (V, E)$ is a weighted graph $H = (V, E', w)$ with the property that for any $u, v \in V$, we have $\delta_G(u, v) \le \delta_H(u, v) \le \delta_G(u, v) + k$. A $k$-spanner is an unweighted subgraph $H = (V, E')$ of $G$ with the same property.

There is an easy way to construct a $4$-emulator $H$ of any graph $G$ such that $H$ has only $O(n^{4/3})$ edges. It's based on the paper All Pairs Almost Shortest Paths by Dor, Halperin, and Zwick. Here's a summary:

  1. If a node has fewer than $n^{1/3}$ neighbors, then add all edges incident on that node.
  2. From your remaining nodes, greedily select the remaining node with the most neighbors. Declare this to be a "cluster center," and then temporarily set aside this node and all its neighbors. Repeat until you're out of nodes. Let $C$ be the final set of cluster centers. There is a proof in the paper mentioned above that guarantees that $C$ is only $O(n^{2/3})$ big.
  3. Add to $H$ the edge from each cluster center to each of its neighbors.
  4. For each $c, c' \in C$, add to $H$ a single weighted edge from $c$ to $c'$ of weight $\delta_G(c, c')$.

It's easy enough to see that steps $1$ and $4$ require $O(n^{4/3})$ edges, and step $3$ requires $O(n)$ edges. Additionally, the error incurred by $H$ is only $+4$: for any $u, v$ in $G$, we know that $H$ contains a shortest path between two nodes of distance at most $1$ from $u$ and $v$ respectively, so the claim follows from the triangle inequality.

This paper also mentions a method that gives $O(n^{3/2})$ edges and $+2$ error. Just modify: in step $1$ add edges to nodes with fewer than $n^{1/2}$ neighbors, and in step $4$, add a weighted edge from each cluster center to each $v \in V$ (rather than each $c \in C$).

If you'd rather think about spanners, you have a few options:

  1. A +2 spanner on $O(n^{3/2})$ edges
  2. A +4 spanner on $O(n^{7/5})$ edges, due to Shiri Chechik
  3. A +6 spanner on $O(n^{4/3})$ edges

Surprisingly, for the +2 and +6 spanners, the relevant algorithm is simply while $H$ is not a $+k$ spanner, find a pair of nodes that violates the condition and add its path to $H$. The algorithm is simple, but the argument behind it is somewhat nasty. If you're interested, read Knudsen.

Hope that helps!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.