Patent ID: 8560573

Claim:
A map difference data generation apparatus comprising: a most recent map data storage device that stores primary most recent map data indicating a connection status of a node and a link of a map; a supplementary map data storage device that stores primary supplementary map data indicating a connection status of the node and the link, which is initially equal to the primary most recent map data; a map update reflection device that generates secondly most recent map data and secondly supplementary map data according to an update of a first link in the primary recent map data when map update for updating the first link is established, and generates tertiary most recent map data and tertiary supplementary map data according to an update of a second link in the secondly most recent map data when map update for updating the second link is established after the update of the first link; a determination device that determines whether the update of the first link and the update of the second link have a dependency relationship, in accordance with a result of searching a route in the tertiary supplementary map data between a first node and a second node, which are both ends of the second link, respectively, and a result of searching the route between the first node and the second node in the tertiary most recent map data; and a map difference data generation device that generates map difference data, which defines a combination of the update of the first link and the update of the second link, when the determination device determines that the update of the first link and the update of the second link have the dependency relationship.