Pre-processing for Search

Resources explaining Landmarks, Reach, and Shortcuts

• Latest version of slides explaining Landmarks, Reach, and Shortcuts

• Paper Introducing Landmarks

• Paper Introducing Reach

• Paper Comparing all of these algorithms

Google Maps Transfer Patterns

• Add time dependent nodes to your graph and precompute lowest cost routes for disjoint subsets — ESA transfer patterns (2010)

• Encode time domain data in frequency space and modify Dijkstra to work in that sparse representation — SIGSPATIAL frequency (2014)

• Cluster nodes in subgraphs to minimize precomputation costs — ALENEX scalable transfer patterns (2016)