A road estimation device receives data including a core point being assigned along a road and assigned with attributes for identifying the road. An input unit inputs map data including links having attributes corresponding to the attributes of the core point. An extraction unit first narrows down links into candidate links each having an attribute corresponding to a non-shape-relevant attribute of the core point. The extraction unit subsequently narrows down the candidate links into a candidate link having an attribute corresponding to a shape-relevant attribute of the core point, thereby to extract the candidate link pertinent to the road represented by the core point from the map data for estimating the road on a map.