I/O efficiency of highway hierarchies
Riko Jacob, Sushant Sachdeva · Repository for Publications and Research Data (ETH Zurich) · 2006
Recently, Sanders and Schultes presented a shortest path algorithm, named Highway Hierarchies, for fast point-to-point shortest path queries. They report extremely quick average queries on the road network of USA. We consider the I/O efficiency of the algorithm and investigate how a good graph layout affects the average query time. We experiment with a few layout heuristics and obtain a speed-up factor of around 1.3 as compared to the default layout and around 1.7 as compared to a random layout.