The Hub Labeling Alogorithm



Andrew Goldberg, Microsoft Research

Monday, January 23, 2012
4:00 PM,
5130 Upson Hall




This is a survey of Hub Labeling results for general and road networks.                                                                                                         
Given a weighted graph, a distance oracle takes as an input a pair of vertices and returns the distance between them. The labeling approach to distance oracle                                                                                                 
design is to precompute a label for every vertex so that distances can be computed from the corresponding labels. This approach has been introduced by                                                                                                    
[Gavoille et al. '01], who also introduced the Hub Labeling algorithm (HL). HL has been further studied by [Cohen et al. '02].                                                                                                                              
We study HL in the context of graphs with small highway dimension (e.g., road networks). We show that under this assumption HL labels are                                                                                                         
small and the queries are sublinear. We also give an approximation algorithm for computing small HL labels that uses the fact that shortest path set                                                                                                         
systems have small VC-dimension.                                                                                                                                                
Although polynomial-time, precomputation given by theory is too slow for continental-size road networks. However, heuristics guided by the theory are                                                                                                    
fast, and compute very small labels. This leads to the fastest currently known practical distance oracles for road networks.                                                                                                                             
The simplicity of HL queries allows their implementation inside of a relational database (e.g., in SQL), and query efficiency assures real-time response.                                                                                                       
Furthermore, including HL data in the database allows efficient implementation of more sophisticated location-based queries. These queries can be combined                                                                                                     
with traditional SQL queries. This approach brings the power of location-based services to SQL programmers, and benefits from external memory implementation                                                                                                   
and query optimization provided by the underlying database.                                                                                                                     
Joint work with Ittai Abraham, Daniel Delling, Amos Fiat, and Renato Werneck