  Computing shortest distances is one of the fundamental problems on graphs,
and remains a {\em challenging} task today. {\em Distance} {\em landmarks} have
been recently studied for shortest distance queries with an auxiliary data
structure, referred to as {\em landmark} {\em covers}. This paper studies how
to apply distance landmarks for fast {\em exact} shortest distance query
answering on large road graphs. However, the {\em direct} application of
distance landmarks is {\em impractical} due to the high space and time cost. To
rectify this problem, we investigate novel techniques that can be seamlessly
combined with distance landmarks. We first propose a notion of {\em hybrid
landmark covers}, a revision of landmark covers. Second, we propose a notion of
{\em agents}, each of which represents a small subgraph and holds good
properties for fast distance query answering. We also show that agents can be
computed in {\em linear time}. Third, we introduce graph partitions to deal
with the remaining subgraph that cannot be captured by agents. Fourth, we
develop a unified framework that seamlessly integrates our proposed techniques
and existing optimization techniques, for fast shortest distance query
answering. Finally, we experimentally verify that our techniques significantly
improve the efficiency of shortest distance queries, using real-life road
graphs.
