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

<p>In practice (AFAIK), the standard way of facing this problem is by the usage of <em>distance oracles</em>, 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.</p>

<p>The <a href="http://arxiv.org/pdf/1305.3314v1.pdf" rel="nofollow">lastest result I'm aware of</a>, 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$.</p>

<p>Alternatively, if you're looking for a stretch smaller than 2, I suggest looking at <a href="http://web.engr.illinois.edu/~agarwa16/pubs/less_than_2.pdf" rel="nofollow">this paper</a>.</p>

CC BY-SA 3.0
2014-04-26T08:57:12.907Z
2014-04-26T22:19:53.883Z
2014-04-26T22:19:53.883Z
R B
<p>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?</p>

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

<p>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.</p>

<graph-algorithms><ds.data-structures><shortest-path>
Shortest distance/path between two households
Derrek Whistle
# Shortest distance/path between two households

(Asked by: username_0 on 2014-04-25)

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.

**Tags:** graph-algorithms, ds.data-structures, shortest-path


---

## 1 answers

### Answer by username_1 on 2014-04-26. Score: 6 | Accepted answer

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](http://arxiv.org/pdf/1305.3314v1.pdf), 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](http://web.engr.illinois.edu/~agarwa16/pubs/less_than_2.pdf).


---

