<p>There have been many results on distance oracles and approximate distance oracles for directed graphs. A distance oracle for a graph is a data structure which can be queried on any pair of vertices (u,v) and returns the distance from u to v. It might also return the path realizing this distance. A good place to start (for the undirected case) would be:</p>

<p>Mikkel Thorup and Uri Zwick. Approximate distance oracles.
Journal of the ACM, 52(1):1–24, 2005.</p>

<p>For the directed case you should check out:</p>

<p>Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick,
Reachability and distance queries via 2-hop labels
SIAM Journal on Computing 32, 1338--1355 (2003).</p>

<p>Some other works also manage to construct such data structures which are also dynamic, that is, it is possible to update the data structure with changes to the graph.</p>

CC BY-SA 3.0
2012-05-23T17:29:31.900Z
Hey Tonatan, Thanks for your answer.  I forgot to mention one of my constraints, which is that any data structure taking space $O(v^2)$ is too large (~ 1PB) for my environment.  I'll add this to the question.
dacc
CC BY-SA 3.0
2012-05-28T20:55:39.783Z
Actually, I'm finding some improved approaches that only take $O(v^{3/2})$ space, so a distance oracle could work!
dacc
CC BY-SA 3.0
2012-05-28T21:22:45.887Z
Hard to say what will pan out, but your reply garnered the most upvotes, so I'll make this a democratic "accept".  Thanks to everyone who responded!
dacc
CC BY-SA 3.0
2012-05-23T08:50:21.427Z
2012-05-23T08:50:21.427Z
Yonatan
<p>Just an initial association—one kind of preprocessing based only on distances is <a href="http://hetland.org/research/2009/metric.pdf" rel="nofollow">metric indexing</a>. There are even some <a href="http://en.wikipedia.org/wiki/BK-tree" rel="nofollow">specific, simple structures</a> for integer metrics, like in your case. That'll only let you retrieve all nodes within a given distance, but maybe you could use the basic ideas somehow?</p>

<p>For example, one common idea in metric indexing is is to use <em>sample objects</em> as pivot points in the distance space, and to use the triangle inequality to find cheap heuristics and bounds for the (expensive) actual distance. Applied to your example of a graph $G=(V,E)$ with $n$ nodes under the unit-weight graph geodesic $d(\cdot,\cdot)$, you could select a subset $P\subset V$ of $m$ pivot nodes, and then pre-compute an $n\times m$ matrix $T$ of distances. </p>

<p>Assuming one-to-one shortest path (given your mention of $A^*$), if you're going from $s$ to $t$, you would then fetch two rows $x=T[s]$ and $y=T[t]$, and compute $h(s,t)=L_\infty(x,y)$, which is simply $\max_{i=1\ldots m} |x_i-y_i|$. Because of the triangle inequality, this will be a lower bound to the the actual distance $d(s, t)$, i.e., $h(s,t)\leq d(s,t)$. (See <a href="http://hetland.org/research/2009/metric.pdf" rel="nofollow">my tutorial</a> for a more thorough explanation.) The heuristic is (as mentioned) guaranteed to be a lower bound, and the more pivots you add, the tighter it will (probably) be. Randomly selected pivots work well in practice, so the method is really simple.</p>

<p>In metric indexing, this lower-bounding heuristic is used for filtering out candidate objects during search (we only want close objects, so those guaranteed to be far away are eliminated). In your case, you could use the bound as a heuristic for $A^*$. Because it's a lower bound, $A^*$ will work correctly, and the number of pivots is a parameter for you to set. The more memory you have, the better your heuristic will be. It works for any starting node and any ending node, and it's really simple. And, as requested, for a constant number of pivots, it takes $\mathcal{O}(n)$ memory.</p>

<p>As for the number of pivots needed—there is some contention in general. Some people claim the optimal number grows with data size (e.g., logarithmically), and some claim it's a function of the inherent hardness of the distance function, regardless of problem size. I guess you could experiment. And while there are specialized algorithms for picking out good pivots, you could just try random ones first; they usually work quite well.</p>

<p>(Come to think of it, I once read some papers on using <em>waypoint</em> or somesuch with $A^*$. I don't remember the details, but that, too, was based on selecting some representative nodes and using them—probably in a manner at least <em>similar</em> to what I've described. I have a look and see if I can find that material again.)</p>

CC BY-SA 3.0
2012-05-24T09:46:26.870Z
By the way: Actually computing $T[\cdot,\cdot]$ is also an interesting problem, I guess. In your case, with a really sparse graph, just running BFS from every node in $P$ would probably be fine. But I wonder if the more general “some pairs shortest paths” problem has any solutions better than just using solutions for the “all pairs” problem. I don't immediately see how that would work, though. (E.g., the Floyd-Warshall algorithm would still have to examine subproblems that involve all start- and end-nodes, as far as I can see.) Oh, well.
Magnus Lie Hetland
CC BY-SA 3.0
2012-05-24T09:05:38.217Z
2012-05-24T09:49:32.203Z
2012-05-24T09:49:32.203Z
Magnus Lie Hetland
<p>you dont mention your data type, which certainly helps to narrow the literature, but it appears that much or even most literature related to this is based on finding shortest paths in highway networks.</p>

<p>this is a new phd thesis that looks promising &amp; focuses on sparse graphs</p>

<ul>
<li><a href="http://www.sommer.jp/csom_phdthesis.pdf" rel="nofollow">Approximate Shortest Path and Distance Queries in Networks</a> by christian sommer</li>
</ul>

<p>this paper discusses shortest path heuristics that work well with low space requirements</p>

<ul>
<li><a href="http://research.microsoft.com/pubs/115272/soda10.pdf" rel="nofollow">Highway Dimension, Shortest Paths, and Provably Efficient Algorithms</a> by Abraham et al, microsoft research</li>
</ul>

<p>as I mention in a comment many real world graphs are "small world" which tend to have highly connected hubs. have not seen papers that specifically use/exploit this property for shortest path estimation however here is one that considers the question generally, considering the existence of effective decentralized [ie using local information] short-path algorithms &amp; proving they must exist for some graphs.</p>

<ul>
<li><a href="http://www.cs.cornell.edu/home/kleinber/swn.pdf" rel="nofollow">The Small-World Phenomenon: An Algorithmic Perspective</a>
by Jon Kleinberg</li>
</ul>

CC BY-SA 3.0
2012-05-28T23:14:14.303Z
Thanks for this -- I like Sommer's treatment of the Thorup and Zwick material a lot. =)
dacc
CC BY-SA 3.0
2012-05-24T03:46:59.877Z
2012-05-24T03:59:43.293Z
2012-05-24T03:59:43.293Z
vzn
<p>I'm trying to preprocess a very large and sparse directed graph in order to do faster shortest path searches.  The vertices have no natural distance function, and the edges are unweighted.</p>

<p>One thought I had was to try and use a force directed graph layout algorithm to project the graph into space.  This way I could use cartesian distance for ASTAR and maybe get some improvements.</p>

<p>Constraint: There are so many vertices that any solution requiring a data with $O(n^2)$ space isn't viable.  However $O(n)$ space is fine, which is what made me think about assigning spacial coordinates to each vertex and doing distance calculations.</p>

<p>Any thoughts on this idea or others?</p>

<p>Thanks,</p>

<p>- Dan</p>

<p>UPDATE: For anyone interested, here's a paper that discusses my initial idea exactly: <a href="http://www.siam.org/meetings/alenex05/papers/02d.wagner.pdf" rel="nofollow">http://www.siam.org/meetings/alenex05/papers/02d.wagner.pdf</a></p>

CC BY-SA 3.0
2012-05-23T05:08:41.180Z
of course you can find all shortest paths and put them in $O(n^2)$ size data structure. I assume this is a bad solution, so what are your constraints? also is this related: http://cstheory.stackexchange.com/questions/8911/computing-distances-with-approximation-less-than-2-in-general-graphs
Sasho Nikolov
CC BY-SA 3.0
2012-05-23T17:48:56.033Z
Hey Sasho,  Thanks for your comment.  Yes, anything with $O(n^2)$ space comes out to ~ 1PB, which is too big.  That's the only constraint I can think of, besides needing to beat vanilla BFS in speed of course.
dacc
CC BY-SA 3.0
2012-05-23T20:26:22.433Z
in that case your question seems like a duplicate of the question i posted a link to above
Sasho Nikolov
CC BY-SA 3.0
2012-05-24T03:28:51.743Z
this seems closely related, coincidentally posted recently. [k-shortest path in a large sparse graph](http://cstheory.stackexchange.com/questions/11497/k-shortest-path-in-large-sparse-graph)
vzn
CC BY-SA 3.0
2012-05-24T03:33:31.737Z
my question is if the graph has some kind of property/pattern in the connectivity that can be exploited; many real world graphs do. the first graph type to look for is "small world graphs" which in these, some "hub" nodes have high connectivity. then you can estimate distances by focusing on the shortest distance between nodes going through the nearby hubs. have not seen this algorithm written up in a paper but there are many papers on small world graphs.
vzn
CC BY-SA 3.0
2012-05-24T14:57:48.663Z
@dacc -- Just to make sure I understand, you are fine with approximately shortest paths; is that right? I assume so since you are talking about embedding the graph into a space and/or using heuristics like $A^{\star}$. Also, are you looking for one-way distances or round-trip distances? The latter part of the question is important for the directed graph case.
Rachit
CC BY-SA 3.0
2012-05-25T09:25:26.573Z
My suggestion (pivoting) is actually quite close to your idea of using force-directed layout and $A^*$. If you use two pivots, you will get the same space usage as your idea (i.e., two “coordinates”), but the $A^*$ will not be approximate (as in your version), but exact (as the pivot-based heuristic is a guaranteed lower-bound). Also, you can add more pivots/“dimensions” for greater heuristic accuracy (and therefore search speed).
Magnus Lie Hetland
CC BY-SA 3.0
2012-05-28T20:50:27.310Z
@Rachit Approximate shortest paths are fine, and I'm only interested in one-way distances.
dacc
CC BY-SA 3.0
2012-05-28T20:52:11.100Z
@MagnusLieHetland I like your idea of pivot points -- I'll have to look into why it's suitable for ASTAR.  Don't completely understand how it works yet.  I think I've also seen this approach called "landmarks" instead of pivots.  Something like this? http://www.cs.uleth.ca/~grant/papers/aigames08.pdf
dacc
CC BY-SA 3.0
2012-05-28T20:53:16.870Z
@vzn I think there are many small world subgraphs, but no global characteristic of that kind.  It's also not hierarchal like a road network.
dacc
CC BY-SA 3.0
2012-05-29T08:19:23.817Z
Ah! Yes, I wrote something about “waypoints” but this landmark stuff was what I was thinking about. (Explains why I could find it ;-) Yes, that is quite similar—the landmarks could also be used as pivots. A quick explanation of pivoting w/one pivot $p$: The distance $st$ is lower-bounded by the inverted triangle inequality, $|sp–pt|$ (because shortest-path distances are metric). If you have many pivots, just take the maximum (which could be described as $L_\infty$ between the node-pivot-distance vectors; but you can ignore that part, if you want). The bound can then be used in $A^*$.
Magnus Lie Hetland
CC BY-SA 3.0
2012-05-29T08:24:28.083Z
By the way: If you're only interested in one-way distances/directed graphs, you'd have to make sure to take direction into account (i.e., drop the $|\,\cdot\,|$). Use the *directed* triangle inequality, $sp \leq st + tp$, which yields the bound $st \geq sp - tp$. (So … if, for example, you have a DAG, or just no out-edges from your destination $t$, this lower bound would be a rather unhelpful $-\infty$ ;-)
Magnus Lie Hetland
<ds.algorithms><graph-theory><shortest-path>
Preprocessing Sparse, Directed Non-Planar Graphs for Faster Shortest Path
dacc
# Preprocessing Sparse, Directed Non-Planar Graphs for Faster Shortest Path

(Asked by: username_0 on 2012-05-23)

I'm trying to preprocess a very large and sparse directed graph in order to do faster shortest path searches. The vertices have no natural distance function, and the edges are unweighted.

One thought I had was to try and use a force directed graph layout algorithm to project the graph into space. This way I could use cartesian distance for ASTAR and maybe get some improvements.

Constraint: There are so many vertices that any solution requiring a data with $O(n^2)$ space isn't viable. However $O(n)$ space is fine, which is what made me think about assigning spacial coordinates to each vertex and doing distance calculations.

Any thoughts on this idea or others?

Thanks,

- Dan

UPDATE: For anyone interested, here's a paper that discusses my initial idea exactly: <http://www.siam.org/meetings/alenex05/papers/02d.wagner.pdf>

**Tags:** ds.algorithms, graph-theory, shortest-path

> **Comments:**
> **username_1**: of course you can find all shortest paths and put them in $O(n^2)$ size data structure. I assume this is a bad solution, so what are your constraints? also is this related: http://cstheory.stackexchange.com/questions/8911/computing-distances-with-approximation-less-than-2-in-general-graphs  
> **username_0**: Hey Sasho,  Thanks for your comment.  Yes, anything with $O(n^2)$ space comes out to ~ 1PB, which is too big.  That's the only constraint I can think of, besides needing to beat vanilla BFS in speed of course.  
> **username_1**: in that case your question seems like a duplicate of the question i posted a link to above  
> **username_2**: this seems closely related, coincidentally posted recently. [k-shortest path in a large sparse graph](http://cstheory.stackexchange.com/questions/11497/k-shortest-path-in-large-sparse-graph)  
> **username_2**: my question is if the graph has some kind of property/pattern in the connectivity that can be exploited; many real world graphs do. the first graph type to look for is "small world graphs" which in these, some "hub" nodes have high connectivity. then you can estimate distances by focusing on the shortest distance between nodes going through the nearby hubs. have not seen this algorithm written up in a paper but there are many papers on small world graphs.  
> **username_3**: @username_0 -- Just to make sure I understand, you are fine with approximately shortest paths; is that right? I assume so since you are talking about embedding the graph into a space and/or using heuristics like $A^{\star}$. Also, are you looking for one-way distances or round-trip distances? The latter part of the question is important for the directed graph case.  
> **username_4**: My suggestion (pivoting) is actually quite close to your idea of using force-directed layout and $A^*$. If you use two pivots, you will get the same space usage as your idea (i.e., two “coordinates”), but the $A^*$ will not be approximate (as in your version), but exact (as the pivot-based heuristic is a guaranteed lower-bound). Also, you can add more pivots/“dimensions” for greater heuristic accuracy (and therefore search speed).  
> **username_0**: @username_3 Approximate shortest paths are fine, and I'm only interested in one-way distances.  
> **username_0**: @MagnusLieHetland I like your idea of pivot points -- I'll have to look into why it's suitable for ASTAR.  Don't completely understand how it works yet.  I think I've also seen this approach called "landmarks" instead of pivots.  Something like this? http://www.cs.uleth.ca/~grant/papers/aigames08.pdf  
> **username_0**: @username_2 I think there are many small world subgraphs, but no global characteristic of that kind.  It's also not hierarchal like a road network.  
> **username_4**: Ah! Yes, I wrote something about “waypoints” but this landmark stuff was what I was thinking about. (Explains why I could find it ;-) Yes, that is quite similar—the landmarks could also be used as pivots. A quick explanation of pivoting w/one pivot $p$: The distance $st$ is lower-bounded by the inverted triangle inequality, $|sp–pt|$ (because shortest-path distances are metric). If you have many pivots, just take the maximum (which could be described as $L_\infty$ between the node-pivot-distance vectors; but you can ignore that part, if you want). The bound can then be used in $A^*$.  
> **username_4**: By the way: If you're only interested in one-way distances/directed graphs, you'd have to make sure to take direction into account (i.e., drop the $|\,\cdot\,|$). Use the *directed* triangle inequality, $sp \leq st + tp$, which yields the bound $st \geq sp - tp$. (So … if, for example, you have a DAG, or just no out-edges from your destination $t$, this lower bound would be a rather unhelpful $-\infty$ ;-)  

---

## 3 answers

### Answer by username_5 on 2012-05-23. Score: 4 | Accepted answer

There have been many results on distance oracles and approximate distance oracles for directed graphs. A distance oracle for a graph is a data structure which can be queried on any pair of vertices (u,v) and returns the distance from u to v. It might also return the path realizing this distance. A good place to start (for the undirected case) would be:

Mikkel Thorup and Uri Zwick. Approximate distance oracles.
Journal of the ACM, 52(1):1–24, 2005.

For the directed case you should check out:

Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick,
Reachability and distance queries via 2-hop labels
SIAM Journal on Computing 32, 1338--1355 (2003).

Some other works also manage to construct such data structures which are also dynamic, that is, it is possible to update the data structure with changes to the graph.

> **Comments:**
> **username_0**: Hey Tonatan, Thanks for your answer.  I forgot to mention one of my constraints, which is that any data structure taking space $O(v^2)$ is too large (~ 1PB) for my environment.  I'll add this to the question.  
> **username_0**: Actually, I'm finding some improved approaches that only take $O(v^{3/2})$ space, so a distance oracle could work!  
> **username_0**: Hard to say what will pan out, but your reply garnered the most upvotes, so I'll make this a democratic "accept".  Thanks to everyone who responded!  

---

### Answer by username_4 on 2012-05-24. Score: 2

Just an initial association—one kind of preprocessing based only on distances is [metric indexing](http://hetland.org/research/2009/metric.pdf). There are even some [specific, simple structures](http://en.wikipedia.org/wiki/BK-tree) for integer metrics, like in your case. That'll only let you retrieve all nodes within a given distance, but maybe you could use the basic ideas somehow?

For example, one common idea in metric indexing is is to use *sample objects* as pivot points in the distance space, and to use the triangle inequality to find cheap heuristics and bounds for the (expensive) actual distance. Applied to your example of a graph $G=(V,E)$ with $n$ nodes under the unit-weight graph geodesic $d(\cdot,\cdot)$, you could select a subset $P\subset V$ of $m$ pivot nodes, and then pre-compute an $n\times m$ matrix $T$ of distances.

Assuming one-to-one shortest path (given your mention of $A^\*$), if you're going from $s$ to $t$, you would then fetch two rows $x=T[s]$ and $y=T[t]$, and compute $h(s,t)=L\_\infty(x,y)$, which is simply $\max\_{i=1\ldots m} |x\_i-y\_i|$. Because of the triangle inequality, this will be a lower bound to the the actual distance $d(s, t)$, i.e., $h(s,t)\leq d(s,t)$. (See [my tutorial](http://hetland.org/research/2009/metric.pdf) for a more thorough explanation.) The heuristic is (as mentioned) guaranteed to be a lower bound, and the more pivots you add, the tighter it will (probably) be. Randomly selected pivots work well in practice, so the method is really simple.

In metric indexing, this lower-bounding heuristic is used for filtering out candidate objects during search (we only want close objects, so those guaranteed to be far away are eliminated). In your case, you could use the bound as a heuristic for $A^\*$. Because it's a lower bound, $A^\*$ will work correctly, and the number of pivots is a parameter for you to set. The more memory you have, the better your heuristic will be. It works for any starting node and any ending node, and it's really simple. And, as requested, for a constant number of pivots, it takes $\mathcal{O}(n)$ memory.

As for the number of pivots needed—there is some contention in general. Some people claim the optimal number grows with data size (e.g., logarithmically), and some claim it's a function of the inherent hardness of the distance function, regardless of problem size. I guess you could experiment. And while there are specialized algorithms for picking out good pivots, you could just try random ones first; they usually work quite well.

(Come to think of it, I once read some papers on using *waypoint* or somesuch with $A^\*$. I don't remember the details, but that, too, was based on selecting some representative nodes and using them—probably in a manner at least *similar* to what I've described. I have a look and see if I can find that material again.)

> **Comments:**
> **username_4**: By the way: Actually computing $T[\cdot,\cdot]$ is also an interesting problem, I guess. In your case, with a really sparse graph, just running BFS from every node in $P$ would probably be fine. But I wonder if the more general “some pairs shortest paths” problem has any solutions better than just using solutions for the “all pairs” problem. I don't immediately see how that would work, though. (E.g., the Floyd-Warshall algorithm would still have to examine subproblems that involve all start- and end-nodes, as far as I can see.) Oh, well.  

---

### Answer by username_2 on 2012-05-24. Score: 1

you dont mention your data type, which certainly helps to narrow the literature, but it appears that much or even most literature related to this is based on finding shortest paths in highway networks.

this is a new phd thesis that looks promising & focuses on sparse graphs

* [Approximate Shortest Path and Distance Queries in Networks](http://www.sommer.jp/csom_phdthesis.pdf) by christian sommer

this paper discusses shortest path heuristics that work well with low space requirements

* [Highway Dimension, Shortest Paths, and Provably Efficient Algorithms](http://research.microsoft.com/pubs/115272/soda10.pdf) by Abraham et al, microsoft research

as I mention in a comment many real world graphs are "small world" which tend to have highly connected hubs. have not seen papers that specifically use/exploit this property for shortest path estimation however here is one that considers the question generally, considering the existence of effective decentralized [ie using local information] short-path algorithms & proving they must exist for some graphs.

* [The Small-World Phenomenon: An Algorithmic Perspective](http://www.cs.cornell.edu/home/kleinber/swn.pdf)
  by Jon Kleinberg

> **Comments:**
> **username_0**: Thanks for this -- I like Sommer's treatment of the Thorup and Zwick material a lot. =)  

---

