What would be the ideal way to store a mid size graph data model so it could be walked in a couple of milliseconds?

In a single "very strong" server, I've seen this implemented using incidence lists (http://en.wikipedia.org/wiki/Graph_(abstract_data_type)). Given that your graph is extremely sparse, it does not make sense to store the graph as an uncompressed matrix. To achieve the latency you're talking about, you'll need to store the entire graph structure in memory (or on SSDs). In a distributed environment, the most efficient way to do this is to use a distributed key-value store, and store the graph structure in an adjacency list. For a first-level traversal, you simply fetch the node's adjacency list. For subsequent levels, you do a scatter-gather. I have seen this implemented in an extremely high-load environment and achieve 1-5ms the majority of the time. The long tail is often not as pretty. You might want to have a look at FlockDB (https://github.com/twitter/flockdb). It's important to recognize that you are still bound by the laws of physics. I have a feeling that you're graph is likely a social graph. In such situations, there is often (very) heavy skew. That is, there will be certain nodes with far greater edges than the average/median. In these situations, you need to be realistic about performance expectations. Typically, in these situations, we implement heuristic business rules to deal with the issue. One thing you haven't mentioned is whether there is meta-data associated with your nodes/edges. If so, that tends to complicate things slightly, though the solutions above should still be valid, with a few minor tweaks. You might also have a look at Twitter's in-memory graph database, Cassovary (http://engineering.twitter.com/2012/03/cassovary-big-graph-processing-library.html). It seems to be skewed more towards data mining, rather than low-latency queries, but it might be worth a look.

DIY in-memory. Any language can provide structures which will brute-force this quite easily. You need to provide an indication of node-size and number of clients/parallel queries since latency is your concern. It would also help if you described the problem a little more. I may well be missing some intrinsic complexity.