I'd be very concerned if download size wouldn't scale with the size of the map, so I'm not quite sure what your point is. Nobody uses lookup tables for routing

I'd be very concerned if download size wouldn't scale with the size of the map, so I'm not quite sure what your point is. Nobody uses lookup tables for routing (that would require quadratic space to store). If you really want to use something that could be described as lookup tables (even though "set intersection" would be more accurate), have a look at hub labeling. But that still requires a lot of space and isn't particularly suitable for traffic updates, so it's clearly not what any of the maps services use, online or offline.