This question is very similar to this, save in Java.
I am working with 2D map data, where nodes are represented as integers and each edge has a positive traversal cost. I need to store and access the fastest path node sequence (route) between every node pair in a graph (from 200 to 250k nodes). Route information does not change over time. Within a single program run, I need to access this data around 100 million times, so access efficiency is as vital as storage efficiency.
I have precomputed (thanks to Python):
- From each origin node
i, the previous node to the destinationj, along the route:k - The (time) cost of the route between
iandj:c(i,j)
From this, I can easily precompute the route between i and j by following the k nodes from j back to i. Doing this on the fly, however, is very inefficient, as we often repeat the same construction procedure.
Thus, I (believe that I) need to precompute and store the fastest path node sequences for each pair i and j. I have implemented the following, both of which are too memory intensive:
Map<origin, Map<destination, LinkedList<Integer>>>LinkedList<Integer>[origin][destination]
Where a LinkedList<Integer> represents the route between the origin i and destination j.
I highly suspect that many routes contain common subsequences. In Java, is there a method of identifying (via precompute or otherwise), these common subsequences, thus vastly reducing the memory required to store the collection of routes, yet maintaining access efficiency? For example, to traverse an N-ary Tree (from i to j), where each node is either a unique or common subsequence of routes?
