# Preprocessing Sparse, Directed Non-Planar Graphs for Faster Shortest Path

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

• 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: cstheory.stackexchange.com/questions/8911/… – Sasho Nikolov May 23 '12 at 5:08
• 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 May 23 '12 at 17:48
• in that case your question seems like a duplicate of the question i posted a link to above – Sasho Nikolov May 23 '12 at 20:26
• this seems closely related, coincidentally posted recently. k-shortest path in a large sparse graph – vzn May 24 '12 at 3:28
• 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 May 24 '12 at 3:33

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.

• 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 May 23 '12 at 17:29
• Actually, I'm finding some improved approaches that only take $O(v^{3/2})$ space, so a distance oracle could work! – dacc May 28 '12 at 20:55
• 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 May 28 '12 at 21:22

Just an initial association—one kind of preprocessing based only on distances is metric indexing. There are even some specific, simple structures 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 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.)

• 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 May 24 '12 at 9:46

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

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

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.

• Thanks for this -- I like Sommer's treatment of the Thorup and Zwick material a lot. =) – dacc May 28 '12 at 23:14