I thought the problem is to interface the data and the pathfinding algorithm is relatively trivial. I don't understand that a TeleAtlas CD suffices for a car navigation system and we can't use the information on that CD. Also I don't understand why a car navigation system can do the route finding in a few seconds and we can't? Do they use better CPU as the StrongArm?

Finding a path is relatively trivial, I got that working in about an hour. But doing it quickly is more difficult. For instance we could optimize the path finding algorithm by only considering roads that are going towards our final target (or at least bring us closer to it). However this way we won't see that if we drive in the wrong direction for 2 blocks that there is a much faster highway to get us there. If we keep track of every possiblity we've evaluated it is trivial to find shortcuts that we happen to have seen before or avoid going down the same street that leads to a dead-end when backtracking. But we don't have memory to remember all possible paths we looked at previously.

Same way with accessing the dataset. Of course we can read through the whole file and draw whatever street happens to fall within the boundaries of the display (or area that we are looking at during routing). That would mean reading several MB (or even GB) for each screen redraw.

For instance, I've been playing with the Tiger/Line dataset for Pennsylvania. There are 9160094 line segments (not all of these are actually streets). So having an index to quickly find the 50-100 segments around my current location is very important, otherwise I have to check every line to see if it happens to intersect with the currently displayed area. All the magic to do this efficiently is in the spatial indexes, which is why those are such a closely guarded secret.

They also might be using a CPU that is more efficient at floating point calculations and doesn't run a software mp3 decoder and visualizations at the same time, but the strongarm should be good enough.