An index engine may receive historical path data characterizing transportation paths in terms of associated conditions, and may define path segments of varying levels of granularity based on the historical path data, wherein relatively shorter path segments have relatively finer levels of granularity than those of path segments of relatively coarser levels of granularity. The index engine may then index each path segment, based on its corresponding level of granularity and its associated conditions. Then, a query processor may receive a query for a new transportation route, and determine a predicted transportation time for the new transportation route, using the indexed path segments.