Map data processing apparatus and method of the same

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates to a device and a method for Processing of map data for updating Map data to be used by mobile units, for example of a vehicle navigation system, a Mobile phone, a personal digital assistant, and . like

2. Description of the Prior Art

<b>Fig.</b> 42 schematically shows a conventional Map data processing device, for example, in Japanese Laid-open patent application no. 11-95657 is described. In the drawing, the numeral <b>1</b> an information center for generating Update information for map data; <b>2</b> a transmitter for transmitting the generated from the information center Update information; <b>3</b> a receiver for receiving the Update information; <b>13</b> a map data storage unit for storing the map data; <b>5</b> a map data processor laying down a portion of the map data, the modified will be, and the extent of change, in response to of the receiver <b>3</b> received Update information, and for the subsequent amendment the map data; <b>6</b> an input device; and<b>7</b> an output device.

In the <b>Fig.</b> 43A to 43C <b>Fig.</b> 43A is a view showing a Road network before you upgrade a certain range is represented by a node and a junction is represented; <b>Fig.</b> 43B a view showing the Road network after updating a particular range is represented by a node and a link is represented; and<b>Fig.</b> 43C is a view that a Node number explained that each node is assigned to With respect to the knot of <b>Fig.</b> to take 43A and 43B.

the operation is explained next.

The Information Centre <b>1</b> transfers Update information for updating the uses map data of each area on a recent version is, via the transmitter <b>2</b>, For example, if the road network from <b>Fig.</b> 43A <b>Fig.</b> 43B is updated, send the information Centre <b>1</b> Update information indicating, that links between the nodes N2 and N5 and were canceled between nodes N5 and N7 of the region, Added a link between the node N3 and N6 was, and the nodes N5 and N7 omitted.

Upon receiving the above-described Updated information on the receiver <b>3</b> takes to the map data processor <b>5</b> the map data of the road network from <b>Fig.</b> 4A, in the map data storage <b>13</b> saved are, and performs an update of the map data on the Basis of updated information by.

This means that the map data be constructed which the road network (<b>Fig.</b> 43B) represent, and the Map data of the road network (<b>Fig.</b> 43B) in the Map data storage <b>13</b> get saved.

In the above structure of the conventional Map data processing device is as Update Information Information used which the Addition or the elimination of nodes and links indicates which form the road network. However, there are the map data that represent the road network, not only from data one to one a node or corresponding link, but also from data a Adjacency relationship between a node and a specify shortcut from data traffic rules between specify links, etc. Such data different Species are closely related. Therefore, the need Map data processor <b>5</b> the type of data to calculate, too changing part, and the content of the change from the Add / absence information of the node or the Link, as update information. Therefore, the Load, which the map data processor <b>5</b> is exposed, excessively increased, which leads to the drawback that a quick upgrade is difficult, etc.

In addition, there is a case that the transmission of Update information from the transmitter <b>2</b> to the receiver <b>3</b> is interrupted, which makes it impossible for the Updated information in relation to a particular receiving area. Due to the impossibility of to update map data of the area, the Map data of a recent version and the map data an old version mixed together in the Map data storage unit <b>13</b> be saved. Both Map data representing the road network, the Nodes arranged in a predetermined order, and Reference is made to a desired node using a node number taken in the arrangement of the field. As in <b>Fig.</b> 43C shown, but results of adding or Elimination of a node to a change of the node numbers, and is assigned to a different node number, if a version is different, although the same node is used.

The relevant card data includes a node number for the reference to the nodes of an adjacent region, So the node number of an adjacent area to the Connection of the road network between the adjacent specify areas. Since the node number of a neighboring However, the node area of ​​the adjacent region in a Version indicating the identical with that of the relevant Range, it is indicative, when the version of the adjacent Region is different from that of the region, the Node number of the adjacent region a different node, causing a mismatch between the adjacent map data in different Versions leads. As mentioned above, the case occur that the map data of different versions mixed in the map data storage unit <b>13</b> available. Then occurs a mismatch between the adjacent Map data, which leads to the disadvantage that For example, the processing of card data impossible is, etc.

SUMMARY OF THE INVENTION

The present invention was made to solve the above developed difficulties and the invention underlying objectives are to provide a Apparatus and method for processing Map data quickly update the map data can.

Other objects of the invention are to provide an apparatus and a method for processing Map data, which is a mismatch between the can prevent card data in different versions.

According to one aspect of the invention is a Map data processing device provided, comprising: a memory device for storing Map data; an information obtaining device for Obtaining updating operation information indicating the Updating content of the map data indicates that in the Memory device are stored; and a Updating means for updating the map data, stored in the memory device, in accordance with updating the operation information of the Information obtaining device was obtained.

In the map data processing device according to the Invention obtains the information obtaining device Updating operation information which containing updated location information, a portion of which to be updated, the opposite by an offset a predetermined reference position in the map data represented.

In the map data processing device according to the Invention receives the information acquisition device Updating operation information which under data are included in the map data, Data definition information to set to contains updated information, as well Updating position information, the card set a indicates in which the data is stored.

In the map data processing device according to the Invention obtains the information obtaining device Updating operation information containing updated location information, at least one or more updating positions in the data set indicates.

In the map data processing device according to the Invention obtains the information obtaining device Updating operation information includes updating type information which Update types of at least one or more parts indicating to be updated in the data set.

In the map data processing device according to the Invention is a data storage apparatus provided to to store the updated operation information, the is obtained from the information obtaining device when the update time as a result of Update device a predetermined reference time exceeds, and for storing map data after Updating by the updating device when the Update time is less than the predetermined time.

In the map data processing device according to the Invention is a data storage apparatus provided to to store the updated operation information, the was obtained from the information obtaining device, when the determined update time by the Update device a predetermined reference time exceeds, and for storing map data after Updating by the updating device when the determined update time predetermined smaller than the Reference time.

According to another aspect of the invention is a Map data processing device provided, comprising: a memory device for storing Map data; an information obtaining device for Obtaining updated information in relation to the Map data stored in the storage device; and an updating means for updating the Map data stored in the memory device, corresponding to the update information from the Information obtaining device is obtained. In this Case receives the information acquisition device corresponding node information, the correspondence a between identical nodes of different versions indicating when the storage device stores map data, and a version of a certain range of that of a is another area different.

In the map data processing device according to the Invention receives the information acquisition device Information with respect to corresponding node only if different versions of adjacent areas are, with the obtained information of corresponding Node relates to identical nodes, the other in the are adjacent areas available.

In the map data processing device according to the Invention receives the information acquisition device only Information with respect to respective nodes of the same Node of each other in an overlapping portion is adjacent spaces.

According to another aspect of the information is a Map data processing method provided, comprising the following steps: obtaining Updating operation information indicating the Updating content stored map data indicates; and Updating map data corresponding to the obtained Updating operation information.

In the map data processing method according to the invention Updating operation information is obtained, which containing updated location information, a portion of which to be updated, the opposite by an offset a predetermined reference position is represented in the is the map data available.

In the map data processing method according to the invention Updating operation information is obtained, which contains data that is information for specifying to contains updated information, as well Updating position information, the record one indicates in which the data is stored in among the the map data contained data.

In the map data processing method according to the invention Updating operation information is obtained, the containing updated location information, at least one or more positions in a update indicating record.

In the map data processing method according to the invention Updating operation information is obtained, the includes updating type information which Update types of at least one or more parts indicating to be updated in the data set.

In the map data processing method according to the invention the updating operation information obtained stored when the update time of the map data exceeds a predetermined reference time, and the Map data stored after the upgrade if the Update time less than the predetermined reference time is.

In the map data processing method according to the invention the updating operation information obtained stored when the determined update time of Map data exceeds a predetermined reference time, and the map data is stored after the upgrade, when the determined update time is less than the predetermined reference time.

According to a further aspect of the invention, a Map data processing method provided, comprising the following steps: obtaining Update information for stored map data; and Updating map data corresponding to the obtained Update information. In this case, if stored map data is present, and a version a certain range from that of another Region differs, on information relating corresponding nodes receive which correspondence a indicating between identical nodes of the respective versions.

In the map data processing method according to the invention is information with respect to each corresponding node only obtained when adjacent versions of each other Areas are different, wherein the information regarding in a corresponding node, which is obtained, identical Node relates to adjacent areas in each available.

In the map data processing device according to the Invention, only information relating to corresponding Node receive, namely with respect to the same node, the in an overlapping portion of adjacent areas of is available.

The invention will be based drawings described exemplary embodiments in more detail, from which further advantages and features emerge. It shows:

<b>Fig.</b> 1 is a schematic view of a Map data processing device according to a first to fourth embodiments of the present Invention;

<b>Fig.</b> 2 is a schematic view of a Map data providing station in each of the first to fourth embodiments;

<b>Fig.</b> 3 is a view of an example of map data;

<b>Fig.</b> 4A and 4B are views each showing a road network explain a certain range;

<b>Fig.</b> 5A to 5J are views showing an example of a Data structure of route calculation data;

<b>Fig.</b> 6 is a view for explaining the contents of a Node Table of the route calculation data of in everyone who <b>Fig.</b> 5A to 5J shown Data structure with respect to the road network of <b>Fig.</b> 4A;

<b>Fig.</b> 7 is a view for explaining the contents of Connection information of the route calculation data in each of the <b>Fig.</b> 5A, 5J Data structure with respect to the road network of <b>Fig.</b> 4A;

<b>Fig.</b> 8 is a view for explaining the contents of a Costs of the route calculation data in everyone who <b>Fig.</b> 5A to 5J shown Data structure with respect to the road network of <b>Fig.</b> 4A;

<b>Fig.</b> 9 is a view for explaining the contents of a Node table, connection information and a Costs, according to the road network of <b>Fig.</b> 4B;

<b>Fig.</b> 10 is a view for explaining the contents of Node table, the connection information and the Cost table corresponding to the road network of <b>Fig.</b> 4B;

<b>Fig.</b> 11 is a view for explaining the contents of Node table, the connection information and the Cost table corresponding to the road network of <b>Fig.</b> 4B;

<b>Fig.</b> 12 is a flow chart illustrating the Operation of the Map data providing station;

<b>Fig.</b> 13A to 13D are views each showing an example of a data structure of Updating operation information show;

<b>Fig.</b> 14A to 14C are views each showing a setting of show data for updating Operation information are used;

<b>Fig.</b> 15 is a view of Updating operation information of Data structure in each of the <b>Fig.</b> 13A to 13D;

<b>Fig.</b> 16 is a flow chart of the operation of the Map data processing device;

<b>Fig.</b> 17 is a flowchart of details of the processing the step ST18;

<b>Fig.</b> 18 is a flow chart illustrating the Definition of update type information in the Updating operation information of <b>Fig.</b> 13A 13D;

<b>Fig.</b> 19A to 19C are views each showing the data structure explaining an update record if Update type information partial indicates update of a single type;

<b>Fig.</b> 20A to 20C are views for explaining the data structure an update record if Update type information partial Update composite type indicates;

<b>Fig.</b> 21 is a view showing the example for the definition of information for partial Data in a call record of Route calculation data link information, the in each of <b>Fig.</b> 5A to 5J;

<b>Fig.</b> 22A and 22B are views of an example of the record in each of the <b>Fig.</b> 19A to 19C shown Data structure;

<b>Fig.</b> 23 is a view of an example of Update record for specifying the partial update of the composite Type of connection record of Link information;

<b>Fig.</b> 24 is a flow chart of the operation of a Map data processor;

<b>Fig.</b> 25 is a flow diagram showing details of the partial Updating the single type of step ST31 of <b>Fig.</b> 24;

<b>Fig.</b> 26 is a flowchart of details of the partial Update the composite type of Step ST32 of <b>Fig.</b> 24;

<b>Fig.</b> 27 is a view of a data structure of a Updating operation information storage section;

<b>Fig.</b> 28 is a view of a data structure of a Map buffer;

<b>Fig.</b> 29 is a flow chart of the operation of a Map data processing device according to the third embodiment;

<b>Fig.</b> 30 is a flow chart of the operation of a Map data processor;

<b>Fig.</b> 31 is a flow chart of the operation of the Map data providing station according to the fourth embodiment;

<b>Fig.</b> 32 is a view for explaining the relationship between the fields of map data;

<b>Fig.</b> 33A to 33E views of respective examples of a Road network;

<b>Fig.</b> 34A to 34D Examples of a respective road network;

<b>Fig.</b> 35A to 35F views of examples of respective Road networks;

<b>Fig.</b> 36A and 36B are views of the respective correspondence between node record numbers;

<b>Fig.</b> 37A to 37C views of examples for a particular Data structure of corresponding node information;

<b>Fig.</b> 38A and 38B are views of respective examples of a Table corresponding node of the data structure everyone who <b>Fig.</b> 37A to 37C;

<b>Fig.</b> 39 Details of the flow chart of the step ST81 from <b>Fig.</b> 31;

<b>Fig.</b> 40 is a Flussdiagrarnm the operation of a Map data processing device according to a fifth embodiment;

<b>Fig.</b> 41 is a view of an example of a data structure a node table storage section;

<b>Fig.</b> 42 is a schematic view of a conventional Map data processing device; and

<b>Fig.</b> 43A to 43C views of a particular road network, represented by a node and a connection represented.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

An embodiment of the present invention is described below.

EMBODIMENT 1

<b>Fig.</b> 1 schematically shows a Map data processing device according to the first Embodiment of the invention. referred to in the drawings numeral <b>11</b> an input device for inputting Information and the like with respect to the operation of the map data processing means; <b>12</b> a Vehicle position detector for detecting the position of a Vehicle, in which the Map data processing device is provided with Using a GPS receiver and the like; and<b>13</b> on Map data storage device (memory device) for storing map data.

Numeral <b>14</b> denotes a transmitter / receiver (Information acquisition device), the mobile device and like used to to receive updating operation information indicating the Update contents of map data indicating, and for transmitting or receiving various information bits with a Map data providing station via a Communication network; and reference numeral<b>15</b> designated a map data processor (updater), the serves to conduct: map matching to a to identify the road on which a vehicle is traveling, and its position on the road, on the basis of Vehicle position from the vehicle position detector <b>12</b> is determined, and map data stored in the Map data storage unit <b>13</b> stored, a Route calculation, the calculation of a route to a start point to a destination using the Map data is used; Route, which serves the Vehicle to lead from the starting point to the destination; Map Display around the vehicle position; and various other Navigation operations; and finally updating the Map data in the map data storage unit <b>13</b> are stored, corresponding to the Updating operation information indicating the content Update indicating and from the transmitter / receiver <b>14</b> Will be received. In this case, contains the Updating operation information indicating the content Update indicating update position information. indicating keep and update a part, Update type information indicating the type of update indicating, for example, replace, delete, add, and like, and the information to be updated part, Replaces example, Added, and the like.

Numeral <b>16</b> called a Update data storage device for storing Map data from the map data processor <b>15</b> updated will; and reference numeral<b>17</b> denotes an output device for display or output, by voice, a map, a Vehicle position, a route, guidance information, and like by default by the card data processor <b>15</b>,

<b>Fig.</b> 2 schematically shows the Map data providing station. In the drawing reference numeral <b>21</b> a transmitter / receiver consists of a model or the like for transmitting data with the transmitter / receiver <b>14</b> about the Communication network serves; <b>22</b> denotes a Road network database for storing road network data are managed for each version; <b>23</b> denotes a Road network upgrade database for storing Road network update data indicating how the Updated road network between different versions has been; and<b>24</b> denotes a Updating operation information generator for generating of updating operation information relating to the Road network data between versions in the Map data processor <b>15</b>, By reference to the Road network database <b>22</b> and the Road network upgrade database <b>23</b>,

<b>Fig.</b> 3 shows an example of map data in the Map data storage unit <b>13</b> are stored in the Update data storage device <b>16</b>, and in the Road network database <b>22</b>,

As map information management information available, various map data, search data management, and various other data.

All map data corresponding to each area to made available when the whole country in different Areas is divided. Information which a map indicates the associated range, is in the map data contain.

Management information is data to manage the map data is provided. The Management information includes information with respect to the Place of the map data in the map information, Version information for managing stored old or new information, etc.

The map data includes road data for Map matching for displaying roads or the like, be used; Background data for displaying a will map background used, for example a River, a lake or the like; Name data for Displays the name of a place, a name or the like be used; Routing data to Route used; Route calculation data, used for calculating a route; data in Relation to local institutions, the local to Search Devices are used, etc. The map data moreover contain different attributes in terms of the map data of information and the like which the specify the field concerned, as well as a bias, the includes information for managing the places various data and the like is used.

The <b>Fig.</b> 4A and 4B are views each showing the Road network of a specific area show. In these Figures denote N0 to N15 nodes intersections specify; and L0 to L16 links that a road to specify connecting the crossing points.

<b>Fig.</b> 4A shows the road network of the above-mentioned Region during a given period; and<b>Fig.</b> 4B shows a recent road network, in which the link L12 of the road network of <b>Fig.</b> 4A is omitted, and the Road linking L16 has been refurbished.

The <b>Fig.</b> 5A to 5J are views each showing an example show the data structure of route calculation data.

<b>Fig.</b> 5A shows the structure of the route calculation data, the consist of a route calculation bias, a Timetable, connection information, and a Costs.

<b>Fig.</b> 5B shows the structure of the route calculation header, are wherein offsets and data sizes used specify the locations of a node table, Link information, and a cost table, each have a length of 4 bytes. The offset represents the Data size of data issuing from the top Route calculation data in the header of each data get saved. Each number in the drawing is a Offset against the head of the route calculation header in Reference to the relevant data.

<b>Fig.</b> 5C shows the structure of the node table in which the Node records are arranged with a fixed length, and Node records in a correspondence one to one to the Nodes are provided which of the road network form each division. In addition, a Node record to identify each node record with a node record number provided that in a number of Arrangement order of the node records represents.

<b>Fig.</b> 5F shows the structure of the node data set from a Knotenkoordinate is that the geographic location an associated node indicates a node attribute that each indicating the nodes under different attributes, For example, the presence of a traffic sign, the Presence on the border of the area concerned, and the like, the number of related compounds which the number of connections indicates that the node are connected; the number of regulated records, which the Number of regulated records of an associated connected Record indicating the offset and an associated Record of the location of the associated connected, Record indicates. The offset represents the data size of data in from the top of the route calculation data saved the head of the corresponding connected record were.

As described above, the node table is the place and the attribute of each node, which in the road network forms the relevant area, the location of the associated, associated data rate, etc.

<b>Fig.</b> 5D shows the structure of connection information, in which the associated data sets with variable lengths are arranged, and associated records in a Correspondence of one to one are provided to the node, which make up the road network of the area concerned. Therefore, each connected record each node corresponds to a relationship of one to one. In addition, a display related data, each associated data provided with a number of associated data record, as Number in the arrangement order of the connected Records.

<b>Fig.</b> 5G shows the structure of the associated data set, wherein which linked records and regulated records are arranged, the related records in a provided relationship of one to one to the compounds are connected to a corresponding node, and the regulated records are provided so that their Number equal to the number of traffic regulations is formed between are the shortcuts available. Additional is to Linked identifier associated with each data set Record number of a linked record provided, as the number in the arrangement order of the related records. To a regulated record to identify each record with a regulated provided number of regulated data set, in a number the arrangement order of the regulated records.

<b>Fig.</b> 5H shows the structure of the linked set of data of information relating to neighboring nodes and from Link cost information is.

When information relating to neighboring nodes a Node connected to a node in accordance with the Record is connected, using his Node record number represents. A node that by the information of the neighboring node is referred to, is a neighboring node of the node in accordance with the denotes associated data set, and the number of existing, adjacent nodes is equal to that of related records.

The link cost information indicates the location of the Information in terms of cost for which driving of the Node according to the Associated record to the adjacent nodes occur. A cost record according to a link which linked the corresponding record is his using Cost record number represents.

<b>Fig.</b> 5I shows the structure of the regulated set of data consists of input link information, which the Linking an input side by a number of linked record indicating from Exit link information, which link the an exit side by the number of linked Record indicates, and a regulated code between Links, the existing traffic rules to driving the linkage represented by the Input link information is given to the indicates linking by the Output link information is specified.

As described above is the connection information the relationship between the node in the road network to forms corresponding area, and the linkage to the Location of a cost data set indicative costs for the Driving between nodes occur and traffic regulations between the links in the node.

<b>Fig.</b> 5E shows the structure of the charge table, in which the Cost data sets are arranged with fixed lengths, and the Cost data sets corresponding to a relationship of one to one on the links exist, which the form road network. In addition to a cost record identify each cost record with a Cost record number provided, as in the number Arrangement order of the cost records.

<b>Fig.</b> 5J shows the structure of the cost data set a link attribute is that each of different link attributes indicating, for example, the road type of an associated link, and the like, a link length, which determines the length of a link indicating an average travel time, indicating the time that needed to drive through a shortcut, and a Width information indicative of the road width of the link indicates.

As noted above, are the costs table different Bits of to information needed for cost calculation are, with respect to the costs that the when passing Linking occur that the road network in the forms relevant field.

<b>Fig.</b> 6 is a view for explaining the contents of Node Table of the route calculation data with the Data structure in each of the <b>Fig.</b> 5A to 5J, with respect to the road network of <b>Fig.</b> 4A. The node N0 to N15 are respectively connected to the node records the Node record numbers 0 to 15 is provided.

So for example, corresponds to the node record a Node record number in <b>Fig.</b> 6 of the node N1 <b>Fig.</b> 4A, , node N1 on a Knotenkoordinate (X1, Y1), is an attribute node NA1 available, and is the Number of connected links four, so that the Links L0, L11, L1 and L8 are connected. The number Regulated records is four, so that four Traffic rules among the links L0, L11, L1 and L8 are present, and an offset corresponding to the associated Record as JOFS1.

<b>Fig.</b> 7 schematically shows the contents of the Connection information of the route calculation data the data structure according to the <b>Fig.</b> 5A to 5J show, in which Road network of <b>Fig.</b> 4A. The node N0 to N15 are respectively with the associated records of the numbers 0 to 15 of related records provided.

For example, corresponding to the associated record of Number 1 of <b>Fig.</b> 7 a related record node B1 of <b>Fig.</b> 4A, his head is offset JOFS1, and corresponds the links L0, L11, L1 and L8, which linked the Records of the numbers 0, 1, 2 or 3 linked records have, as well as the regulated records the numbers 0, 1, 2 or 3 of regulated records.

The information relating to the adjacent nodes and the Information with respect to the associated cost of the linked record number 0 of a linked Record is in each case 0, the adjacent node of the Node N1 is the node N0, and the cost of the node N1 N0 to the node by the cost record with the Number 0 specified. In other words, the cost will represented by the cost record of the link L0.

The information relating to the adjacent nodes and the Information with respect to the associated cost of the linked record number 1 of the linked Record are 12 and 11. The adjacent nodes of Node N1 is a node N2, and the cost of the node N1 N12 to the node through a cost record with the Number 11 indicated. In other words, the cost represented by the cost record of the link L11.

The information relating to the adjacent nodes and the Information with respect to the associated cost of the Link record number 2 of the linked Record be 2 or 1. The adjacent nodes of Node N1 is a node N2, and the cost of the node N1 N2 to the node through a cost record number 1 indicated. In other words, the cost of the Cost record of the link L1 represents.

The information relating to the adjacent nodes and the Information with respect to the associated cost of the linked record of the linked record with the Number 3 are each 5 or 8. The adjacent nodes of the node N1 is a node N5, and the cost of the Node N1 to the node N5 are a cost record reproduced at the point 8 below. In other words, the Cost by the cost record of the link L8 represents.

The regulated record of a regulated record with the number 0 has input link information <b>5</b> on, Output link information <b>3</b>And a regulated Record r10 between links. The traffic rules at Driving from the link L0 according to the number of 0 linked record to the link L8 corresponding the related record with the number 3 will therefore with r10 indicated.

The regulated record of a regulated record with the number 1 has input link information <b>1</b> on, Output link information 0, and a regulated Record r11 between links. Traffic rules at Driving from the link L11 according to the number of 0 linked record to link L1 in accordance with the Number 2 of the linked record therefore be r11 indicated.

The regulated record of a regulated record with the number 2 has input link information <b>2</b> on, Output link information <b>1</b>And a regulated Code r12 between links. Traffic rules while driving the link L1 corresponding to the number 2 of the linked Dataset to link L11 according to the number of 1 linked record are therefore indicated by r12.

The regulated record of a regulated record with the number 3 has input link information <b>3</b> on, Output link information <b>2</b>And a regulated Code r13 between links. Traffic rules while driving the link L8 corresponding to the number 3 of the linked Dataset to link L1 corresponding to the number of 2 linked record are therefore indicated by r13.

<b>Fig.</b> 8 schematically shows the contents of the cost table of the Route calculation data with that data structure in everyone who <b>Fig.</b> 5A is given to 5J, which in terms of Road network of <b>Fig.</b> 4A. The cost data sets with the Cost data numbers 0 to 15 are the respective Links L0 assigned to L15.

The <b>Fig.</b> 9 to 11 show schematically the content of a Node table, connection information, and Cost table corresponding to the road network of <b>Fig.</b> 4B.

By unlinking L12 is the number Links that connected to the node N2 and N3 are equal to 3 and is the number of rules between Links equal to 2. As shown in the table of node <b>Fig.</b> 9 shown, therefore, the number of connected links and the number of data sets of the regulated Node records node IDs 2 and 13 to 3 or 2 updated.

By adding the link L16 is the number Links equal to 4, applied to the node N3 and N14 are connected. Regarding rules between these Links are an input regulation r32, of the Link L16 to the link L2, and a Output regulation r33 of the link L3 to Link L6, the node N3 added, whereas the previous regulation on node N14 is maintained. As in the node table of <b>Fig.</b> shown 9, therefore, the number in related links and the number of regulated Records of the node data record with the Node record number 3 respectively updated to 4, and is the number of connected links of the node record a node record number 14 on 4 updated.

In addition, as described above, since the has changed data size of the associated data set, the place the connected records of the connected record numbers 3, 14 and 15 amended, and the offsets of the associated Records the node codes with the node record numbers 3, 14 and 15 respectively updated on JOFS2 'JOFS14', or JOFS15 '.

In the link information from <b>Fig.</b> 10 by deleting the link L12, in the related record with the Number 2 of a related set of data associated Record number 1 of a linked record according to the link L12 of the number 2 of the connected Data set from <b>Fig.</b> 7 deleted and the linked Records linked Datensatznunmern 0, 2 and 3 arranged. The regulated records with the numbers 1 and 2 regulated records which rules in relation to Link L12 in the connected record number 2 an associated data set of <b>Fig.</b> 7 specify deleted and there are the regulated records with the numbers 1 and 2 regulated records arranged. As below is explained as the link cost record number is amended by deleting the link L12, the Link cost information of the linked record with the number 1 to 12 updates.

As in the case of the associated data record with the number 13 are the associated data set, due to the change of Link cost record number of bits Link cost information of the linked record of 0 Number of connected record numbers of 8 to 10 records each connected at 12, 13 and 14 updated; and bits of the link cost information in Terms of the related record with the number 1 linked records of the numbers 12 and 14 connected Records each refreshed at 12 and 14 respectively.

By adding the link L16 in the connected Record number 3 of the associated record is the linked record number 3 of the linked Record corresponding to the link L16 added, and are the numbers 1 and 2 of regulated records which Rules regarding the link L16 specify before regulated record number 1 of the regulated Record of the connected record number 3 of related record inserted, the in <b>Fig.</b> is shown. 7 In the connected record number 14 of associated data record, the record associated with the Number 3 of the linked record in accordance with the Link L16 added.

As a result of the deletion of the link L12 and the addition the link L16, as described above occur, also linked the addition or deletion Records and regulated records on what changes in the data sizes of the associated data records with numbers 2, 3, 13 and 14 connected records leads. Therefore, the offsets of the associated records of the numbers 3, 14 and 15 related records each on JOFS3 'JOFS14' or JOFS15 'changed, and also the data size of the Connection information changed. In adapting to the change the data size of the connection information is also the Offset the cost table changed, the behind the Link information is arranged.

In the node N12 is the content of the traffic rules with respect the access from the link L11 to the link L5 of r63 to r63 'updated.

In the cost table of <b>Fig.</b> 11, by deleting the Link L12, the cost record a Cost record number 12 of <b>Fig.</b> 8 according to the Link L12 deleted, and the Cost record numbers of the following cost records changed. Further, by adding the link L16 the cost record of a cost record number 12 added.

is as described above with respect to the Update, ie the deletion of the link L12 and the Deletion of the link L16, the following performed: Updating the record in the node record numbers 2, 3, 13, 14 and 15, the node table; updating the associated records with the numbers 2, 3, 8, 9, 10, 12, 13 and 14 related records the connection information; Deletion of the cost records of the cost record number 12 the cost table; and adding the cost of record on End.

Therefore, updated map data by collecting Updating the operation information with respect to the Records various data are represented. At the Map data providing station, with a processor having high processing capability, the updated map data in Updating operation information of the records various data converted. In the Map data processing device can by updating the map data corresponding to the Updating operation information of the records Stress that when updating the A card processing device is exposed, significantly updating can be reduced, and fast be performed.

An operation will next be described.

<b>Fig.</b> 12 is a flow diagram of the operation Map data providing station shows. If the Map data providing station updated in step ST1 is, the process waits for the arrival of a Updating operation information request from the Transmitter-receiver <b>14</b> the map data processing device to the transmitter / receiver <b>21</b> is sent, and goes to the Arrival to step ST2.

In step ST2, the Updating operation information request from the Transmitter-receiver <b>21</b> receive. These includes updating operation information request Map data identification information indicating the Map data of a region indicative of, and Version information of the navigation processing Map information processing apparatus are required.

generated in step ST3, according to the Map data identification information map data ID M indicates and the version information indicating a version V indicating and was obtained in the step ST2, the Updating operation information generator <b>24</b> Update operation information, with reference to the map data which the map data M having ID that in the road network upgrade database <b>23</b> stored, and on the road network update data from the version V a most recent version VX, of with reference to the map data Map data ID M, which in the Road network upgrade database <b>23</b> stored.

In step ST4, the updating operation information, which was generated in step ST3, to the transmitter / receiver <b>3</b> the map data processing device through the Transmitter-receiver <b>21</b> transfer.

Then, the process proceeds to step ST1, and is a similar processing described as above repeated.

Now, with the example of the route calculation data of the <b>Fig.</b> 5A to 5C, the updating operation information described, which is generated in the step ST3. It will For example, assume that when the map data ID M specify the map data of a region of in each <b>Fig.</b> 4A and 4B, the version of the road network of V <b>Fig.</b> 4A corresponds, and the road network of the most recent version VX is a street of <b>Fig.</b> 4B.

In this case, road network update data included from V version to the latest version, with respect to the Map data of the map data ID M, which in the Road network upgrade database <b>23</b> stored, Bits of information, which the deletion of the link L12 show, the addition of the link L16, and different information bits with respect to the link L16 in each of the <b>Fig.</b> 4A and 4B.

The updating operation information generator <b>24</b> generated Information in regards to how the records updated to be, which contains various data for Upgrading the route calculation data of <b>Fig.</b> 6 to 8 to the route calculation data of <b>Fig.</b> 9 to 11 necessary, by deleting the link L12 and Adding the link L16, which in the <b>Fig.</b> 4A and 4B are shown, in accordance with the above-mentioned Road network update data. In addition, since the Data sizes of various data will also be changed, which form the route calculation data, information created regarding how the route calculation biasing the <b>Fig.</b> 5A is to be changed to 5J.

The <b>Fig.</b> 13A to 13D are views each showing an example for the data structure of Show updating operation information on the above-described manner by the Updating operation information generator <b>24</b> generated becomes. As in<b>Fig.</b> 13A, there is Update operation information from a Updating operation information header and one or multiple update segments. The Updating operation information includes Updating operation information data size which the Data size of the update operation information indicates Map data identification information indicating the Map data ID of the map data indicating Update version information which a Updated version indicates that the Updating operation information is given, ie Which version to which version update takes place, and an update segment number, which the Number or number of update segments of Updating operation information indicates.

If the most recent map data already on the Map data processing device were delivered by wherein the updating operation information request ran out, so if the version information in the Updating operation information request with the matches most recent version, the Updating operation information as an information set, which the update from the recent Version relates to the latest version, is the number or number of update segments set to 0, and is the update information only from the Updating operation information header.

As in <b>Fig.</b> 13B, there is a segment update of an update segment header, and one or multiple update records. Of the Update segment header contains data type information, Update type information, a Updating position division, and the number of Update records. The data type information is so such as those defined in the <b>Fig.</b> 14A, and outputs the To kind of data obtained by the update segment are to be updated, so a type of data from the route calculation header, the node table, the Connection information, the cost table, etc. selected becomes. The update type information is like those defined in the <b>Fig.</b> 14B, and is a to be performed on update operation, so a Operation, which is selected from deleting, adding and Overwrite. The updated Position Department is such as those defined in the <b>Fig.</b> 14C is shown, and indicates whether the definition of an updated position Offset Type is that uses the data size of data from the head data, which is indicated by the data type information, are stored in the update position, or from the Record type, in which the record number of data is used, the set of the data type information becomes. The number or numbers of update records is the number or numbers of update records the update segment to.

In the case of the record type of Updating position division is a record type fixed length or variable length shown, depending on whether the set of the data type information data a fixed have length or a variable length.

<b>Fig.</b> 13C shows the data structure of Update record, when the Update Position Department of Offset type. On Head offset is the head position of conduct Update operation on, determined by the Update type information over by an offset the head of the data, before the data type information to the Update is specified. The update data size is the scope of implementation of the Update operation to that of the Update type information is set. The number or part number of update data that are present, is equal to an amount by updating data is indicated, and outputs data to replace and add to.

When the update type information indicates deletion, No update part data available.

In the case of the update record of the offset type be when the update type information deletion indicating specified only by the update data size Erase everything from the position of the head by the offset Data indicated that the data type information is specified. When the update type information a indicates replacement, only the Updating data size specified data replaced by Updating partial data of the position by the Head offset of the data indicates that of the Data type information is specified. If the Update type information indicates an addition, be Update part data is inserted in the position indicated by head offset of the data indicates that of the Data type information is specified.

<b>Fig.</b> 13D shows the data structure of Update record, when the Updating position division, a record type with fixed Length or variable length. is a head record number the head position to carry out a Update operation on, determined by the Update type information by the record number of Data generated by the data type information before Update can be specified. The number of Update part records indicates the range for Implementation at the update operation, by the Update type information from the head record number is set. The number or number of Update part records that exist is, equal to that represented by the Update part record number is specified, and there Data to replace and add to. If the Update type information indicates deletion, are no update part data available.

In case of an update record of the record type is when the update type information deletion indicates the number of records of the number Update records is specified, from a position deleted by the head record number of data is specified, indicated by the data type information becomes. When the update type information replacement indicates the number of records that the number specified by updating records through replacing update data subsets from the position is given by the head record number of data is indicated by the data type information. If the Update type information an addition indicating is an updating partial data set before the data is inserted, which is indicated by the head record number of data, which is indicated by the data type information. When a Record is added to the end of data obtained by the Data type information are set, then a value of by adding 1 to the record number of Enddatensatzes the data obtained is set as the head record number.

The update segments of <b>Fig.</b> extend 13B continuously when data type information is identical. is the data type information is identical, then the Update Position Department of offset type before Record type arranged. If the data type information and the Updating position division are identical, are bits of update type information in the order of Substitution, deletion and addition arranged.

<b>Fig.</b> 15 shows the updating operation information of Data structure in each of the <b>Fig.</b> 13A to 13D, and of the updating operation information generator <b>24</b> is produced. An update operation of the Route calculation data of <b>Fig.</b> 6-8 to those of the <b>Fig.</b> 9 to 10 is specified, and an update segment # 0 indicates that an offset relative to the head of Route calculation header data 12-8 bytes, so in other words that the command is issued, the Data size of the connection information and the offset of the Costs by updating data SSSS and OOOO to replace.

An update segment # 1 indicates that a replacement in accordance with the update records # 0 and # 1 of the Node records of the node table is performed. For example, at the update record # 0 that two node records of the node record number 2, so the node records the node record numbers 2 and 3, by the node records of the node record numbers 2 and 3 from <b>Fig.</b> are to be replaced. 9

An update segment # 2 indicates that a replacement in accordance with the update records # 0 and # 1 of the connected records the connection information is carried out. For example, the Update record # 0 indicates that two connected Records with the number 2 of the associated records, so the associated data records with numbers 2 and 3 related records by the associated records of Sections 2 and 3 of the associated records of <b>Fig.</b> 10 are to be replaced.

An update segment # 4 indicates that an addition or addition to the connection information in accordance with the Update records # 0 and # 1 is performed. Thus, For example, the update record at # 0 that two related records with the numbers 2 and 3 related records by <b>Fig.</b> 10 before the number of 4 associated dataset are inserted.

An update segment # 3 indicates that a deletion from the connection information corresponding to the Updating records is performed # 0 and # 1. So for example, has the update record # 0 that two linked records from the number 2 connected Records, so the associated records with the numbers 2 and 3 related records are deleted.

An update segment # 5 is the deletion of a Returns record at from the cost table. Of the Update record # 0 instructs that a Cost record of the cost record number 12, so the Cost record with the cost record number 12 deleted becomes.

An update segment # 6 is the addition of a Cost record for cost table. Of the Update record # 0 instructs that a Node record the cost record number 15 of <b>Fig.</b> 11 before the cost record number 16 is added, so after Cost record number 15th

<b>Fig.</b> 16 is a flowchart of the operation Map data processing device displays. If the Device is put into operation, is first in step ST11 operation information from the input device <b>11</b> inputted, for operating the Map data processing device, information with respect to the reduced scale of the map display, rollers the displayed map, select a destination, Route calculation, and the like.

is the current position of a vehicle in the step ST12 by the vehicle position detector <b>12</b> receive.

In step ST13 map data is a range for the navigation processing is required from the Operation information determined, the condition in step ST11 was, the current position of the vehicle which in step ST12 was obtained, etc. Then, a Updating operation information request, which Map data identification information and includes version information which map data represent, by the transmitter / receiver <b>14</b> to the transmitted map data providing station, and is a leave request, updating operation information for updating the map data to latest map data send.

In step ST14, the Updated operation information of the Map data providing station is sent by the Transmitter-receiver <b>14</b> received, in accordance with the Updating operation information request of Step ST13.

In step ST15, the Updating operation information obtained in step ST14 was received, bit by bit from the transmitter / receiver <b>14</b> each time taken from when the process at this step passes, and then the process proceeds to step ST16 proceeds. However, were all bits of removed updating operation information, and are no additional bits of information update operation yet, the process proceeds to step ST20.

In step ST16 is referring to the Updating operation information header in step ST15 obtained updating operation information made, and if the number or numbers of Update segments is 0, it is determined that updating the map data is unnecessary. The process then proceeds to step ST17.

In step ST17, reference to the Updating operation information header in step ST15 obtained updating operation information taken, and the map data obtained by the Map data identification information are input from the map data storage unit <b>13</b> removed.

In step ST18 an update for, in step <b>5</b>T17 obtained map data performed in accordance with the Updating operation information obtained in step ST15 was obtained.

In step ST19, the updated in step ST18 Map data in the update data storage device <b>16</b> stored, and also management information updated, the update data in the storage device <b>16</b> is stored. If the storage capacity of Update data storage device <b>16</b> by storing the map data is exceeded, the map data, in the update data storage device <b>16</b> saved are deleted, starting with those with the longest Storage time until a required, empty area can be assured, and then the map data is stored.

Reference is in step ST20 to the management information of the Update data storage device <b>16</b> taken, and required map data from the Update storage device <b>16</b> receive. If the required map data is not in the Update data storage device <b>16</b> are present, required map data from the map data storage unit <b>13</b> obtained by referring to the management information in the map data storage unit <b>13</b>, And then a predetermined navigation processing is performed.

Then, the process returns to step ST11, and is then the above-described processing performed.

<b>Fig.</b> 17 is a flow chart showing details of step ST18 shows. In step ST21, a segment set value establishing a to be processed Updating the segment is set to 0, so a Head update segment. To segment definition is a the update segments in the obtained in step ST15 set update operation information on the Based on its number in the arrangement order.

In step ST22, the number of update segments under the update segments in the Updating operation information header in step ST15 obtained updating operation information with the Segment set value compared. If a match is detected, then the processing of step ST18 ends, as all segments of the update Updating operation information have been processed. Becomes no match is found, the process goes to Step ST23 over to an updated segment process, which is indicated by the segment definition.

In step ST23, a Update record setting value establishing a to be processed the update record to 0 set, so a head update record. For the Update record setting is one of the updated records in the segment by establishing specified refresh segment based on its Number specified in the arrangement order.

In step ST24, the number of updated records in the update segment header of the Segment definition specified refresh segment with update record setting value compared. Becomes a match is found, the process goes to Step ST30 through since all updated records of Updating the segment have been processed, represented by the Segment definition is specified. If no match detected, the process proceeds to step ST25 to the to process updated record by Determining the updated record is specified.

In step ST25, a check with respect to the Update type information of Update segment header of the Segment definition specified refresh segment performed. Specifies the information to a cancellation, is the Process to step ST26 above. In addition comes the Process to step ST27. When replacing the process goes to step ST28 above.

In steps ST26, ST27 and ST28 is with respect to the Update segment header of the update segment taken, which is indicated by the segment setting, is a deletion, addition or substitution of data performed that of the data type information Update segment header in the step ST17 obtained map data are given, according to the Update Position Department of Update segment header, and in accordance with the updated record of the determination updated record is specified. Then comes the Process to step ST29 above.

In step ST29 of determining value for the will updated record only increased by 1 to the next arranged to define updated record. Then goes the process proceeds to step ST24.

Thereafter, the process from step ST24 to step ST30 is repeated, and when the processing of all updated Records of the specified by the segment definition Update segment is completed, is as described above described the process from step ST24 to step ST30 about.

In step ST30 of the segment setting value is only 1 increased to the next segment disposed update define. Then, the process proceeds to step ST21.

Thereafter, the above-described processing repeated and updated, all segments in the Step ST15 obtained updating operation information processed. Then the processing of step ST18 terminated.

As described above, the map data updated by performing a simple Processing, for example, replace, delete and add of data, according to the command of Updating operation information. In this way, a quick update performed.

EMBODIMENT 2

is in the second embodiment Update type information in the Update operation information shown in each of the <b>Fig.</b> 13A to 13D, such as those defined in the <b>Fig.</b> 18 shown is. The data structure of the updated data set into the Updating operation information of each of <b>Fig.</b> 13A to 13D is adjusted such as in each of the <b>Fig.</b> 19A to 19C is shown when the update type information a partial update single type indicating or as those in each of the <b>Fig.</b> 20A to 20C is shown when the Update type information, a partial update composite type indicates. For the processing of step ST25 of <b>Fig.</b> 17, as in <b>Fig.</b> 24 demonstrated a Check if the update type information a partial update of the single type indicating and Verification added when the Update type information, a partial update composite type indicates. In the case of partial Updating the single type is the processing of Step ST31 performed. In the case of partial Update composite type is the processing of Step ST32 performed. In this manner, a performed partial update in the record will.

<b>Fig.</b> 19A shows the data structure of the updated Record, the updated record of a bias exists, and one or more partially updated Records. The updated record header contains a Record number that a record to update indicating of data indicated by the data type information are information of the type with partial update, updating position division, a number partially updated records which partially the number updated records indicates. The information of the type partial updating and Updating position division are each as in <b>Fig.</b> 14B or 14C defined.

<b>Fig.</b> 19B shows the data structure of a partially updated record when the Update Position Department of Offset type. On Head offset is the head position to carry out a Update operation on, indicated by the information type partial updating of the updated Record leader, by an offset relative to the head a record which of the record number updated record header is specified. A Update data size is the area of ​​the implementation of Update operation on, determined by the information type partial updating of the head offsets. The Number or number of existing update part data is equal to an amount determined by the Update data size is specified, and data Replace and add indicative. When the information of the type partial update indicating a deletion, are not Updating partial data available.

<b>Fig.</b> 19C shows the data structure of a partially updated record when the Update Position Department of record type is. Information of the type of partial data indicates the type of data at that updates in the record to be updated to be in the updated records. A Head record number indicates the head position for the implementation of an update operation on, determined by the Information of the type partial updating, by the Record number of data by the information of the type Partial data are given before the upgrade. The Number or number of update part records are the Area to carry on the update operation, determined by the information of the type of partial Update, from a head record number. The number or number of existing update part records equal to the number or amount of Update data subsets, and outputs data for replacing and Add. No update part data yet, when the information of the type of partial Update indicates a deletion.

By foregoing, updated Records can an update operation of the same type for multiple locations are ordered in the data or a.

The <b>Fig.</b> 20A to 20C are views each showing a case show, in which the information of the type of partial Update and the update position in department the updated record header in each of the <b>Fig.</b> 19A held to 19C for each partially updated record be, and the update operations of different Modes can be ordered in a record.

As described above, can, by adjusting the updated records in such a manner as shown in each of the <b>Fig.</b> 19A to 19C and each of the <b>Fig.</b> 20A to 20C shown is several update operations for a record defined by a partially updated record will. Therefore, the data size of the Updating operation information can be reduced.

<b>Fig.</b> 21 shows a definition example of information of Type of partial data in the associated record of Connection information of the route calculation data of <b>Fig.</b> 5A to 5J. 0 and 1 are respectively the field of the linked Records or the field of regulated records assigned to forming the associated record.

The <b>Fig.</b> 22A and 22B are views showing examples of Show updated records that the data structures <b>Fig.</b> 19A to 19C show, when the node record of Node record number <b>15</b> the node table from that in <b>Fig.</b> 6 to those of <b>Fig.</b> 9 is updated, and if the connected record number 12 related records the link information from that in <b>Fig.</b> 7 to those in <b>Fig.</b> 10 is updated. A partial data type as that defines the in each <b>Fig.</b> 19A to 19C shown is.

In the <b>Fig.</b> 22A and 22B shows <b>Fig.</b> 22A an example of an updated record of the partial update the single type of node record of the node table indicates. In detail, from a position at which an offset of 10 against the head of the node record the node record number of 15 <b>Fig.</b> 6 is provided, instructed that 2 bytes by updating partial data be replaced JOFS15 '.

It is believed that the offset of the associated Record of the node record is 10, and its Data length is 2 bytes.

<b>Fig.</b> 22B shows the example of an updated Record that the partial update of the single type the associated data record the connection information indicates. With respect to the associated data set with the number 12 related records in <b>Fig.</b> 7, the partially updated record # 0 indicates that the record of a Number 1 records linked through the Update part record # 0 is to be replaced, so the Contents of a linked record on which the number linked records of related records of the number 12 related records in <b>Fig.</b> 10 is equal to 1. Of the partially updated record # 1 instructs that the Record number 3 of regulated records by the Update part record # 0 is to be replaced, so a regulated record, on which the number of Regulated record the associated record with Number 12 related records in <b>Fig.</b> 10 is equal to 3.

<b>Fig.</b> 23 shows an example of an updated Record that the partial update of the composite type the associated data record the connection information indicates. With respect to the associated data set with the number 14 related records in <b>Fig.</b> 7, the partially updated record # 0 indicates that the record of a Number 1 records linked by the updated Partial data set # 0 is to be replaced, so the contents of a linked record on which the number of linked record of the linked record with the Number 14 related records by <b>Fig.</b> 10 is equal to 1. The partially updated record # 1 has, on that of the updated part record # 0 at the end of the field linked records of the connected record with the Number 14 related records in <b>Fig.</b> are added 7 should, therefore a related record, in which the number linked records of the connected record with the Number 14 related records by <b>Fig.</b> 10 is equal to 3.

<b>Fig.</b> 25 is a flowchart showing in detail the partial Updating the single type of step ST31 of <b>Fig.</b> 24 shows.

In <b>Fig.</b> 25, in step ST41 target record definition, the indicating a record to be updated, equal to the value the record number of the updated record header in everyone who <b>Fig.</b> 19A set to 19C.

In step ST42 are updating operation down and updating position division down to Determining an update operation and a Update Position Department set equal values the partial by the information of the type update and the updating position division of the updated Record leader of <b>Fig.</b> 19A are set to 19C.

In step ST43, for a to be processed, partially updated record, a set value for a partially updated record on the basis Arrangement order of the updated records is set, set to 0, so a head of a partially updated record.

In step ST44, the number is partially updated Records in the update record with the bias Set value compared to the partial update.

If a match is found, the processing terminated in step ST31, since then the processing of all partially updated records of the updated Data set is completed. If no match detected, the process proceeds to step ST45 to the to process partially updated record by the establishment of a partially updated record is specified.

In step ST45, partially in accordance with the updated record of the by establishing for partially updated record is specified, a Data, which is indicated by target record definition, updated based on the updating operation and the updating position division, which in step ST42 were established.

In step ST46 of determining value for the will updated record only increased by 1, so that a next lying updated record is set, and then the process goes to step ST44.

Thereafter, the process from step ST44 to step ST46 is repeated. When the processing of all partially updated records is completed, the processing in step ST31 finished.

<b>Fig.</b> 26 is a flowchart showing in detail the partial Update composite type of step ST32 in <b>Fig.</b> 24 shows.

In <b>Fig.</b> 26, in step ST51 target record definition, the indicating a record to be updated, equal to the value the record number of the updated record header of <b>Fig.</b> 20A set to 20C.

In step ST52 is the partially updated Record to be processed, the determination value for the partially updated record on the Based on the arrangement order of the updated Records is set, set to 0, so the Head of a partially updated record.

In step ST53, the number is partially updated compared records in the updated record header with the setting value for the partially updated Record. If match is found, the Processing of step ST32 ends, since then the Processing of all partially updated records the updated record was ended. If no Match is found, the process goes to Step ST54 over to the partially updated record to process which is partially due to the establishment of the updated record is specified.

In step ST54 are updating operation down and updating position division down to Determining an update operation and a Update Position Department set equal values the partial in the information of the type and update the updated position of the updated Department Record the leader <b>Fig.</b> 20A are set to 20C, of partially updated data set by the stated determination of the partially updated record becomes.

In step ST55, the record, which is by the Target record definition is specified, updated, according to the partially updated record by establishing for the record partially updated is specified.

In step ST56 of determining value for the will updated record only increased by 1, so that the next arranged, updated record is set. Then the process goes to step ST422.

Thereafter, the process from step ST53 to step ST56 is repeated. When the processing of all partially updated records is completed, the processing step ST32 finished.

As described above, the updating of a number identical types of update in the record as a partially updated record achieved, and the Updating of a number of different Update types in the record as a partially scored updated record. Therefore, the time be reduced, which is required to Update operation information from the to obtain map data providing station, the Map data updating are carried out quickly, and can communication cost is reduced.

EMBODIMENT 3

<b>Fig.</b> 27 shows the data structure of a Updating operation information storage section, the in the update data storage device <b>16</b> according to the third is provided embodiment.

Updating operation information is correspondingly Updating operation information management information stored. The Updating operation information management information specifies the location of the update operation information in the update data storage device <b>16</b> is stored.

<b>Fig.</b> 28 shows the data structure of a card buffer in the map data processor <b>15</b> according to the third embodiment is provided. The card buffer stores map data corresponding card management information. The Card management information consists of a Map data number indicating the number of map data, which is necessary for navigation processing, and from Card management records that according to the Map data is provided that the Navigation processing are required. Of the includes map management record Map data identification information indicating the Map data ID of the corresponding map data indicating Map data presence information, the presence of the the corresponding map data in the map buffer indicates and map data position information of the place corresponding map data in the map buffer specifies.

<b>Fig.</b> 29 is a flowchart of the operation Map data processing device according to the third Embodiment, wherein steps ST61 to ST65 the process of <b>Fig.</b> are added 16th In step ST18 measured the time it is consumed for updating.

In step ST61 with the card management information of Map buffer of the map data processor <b>15</b> a Initialization performed. In the number or number of Card data is the number or amount of map data set which of the navigation processing Step ST20 is required. The map data ID at any Map data of the navigation processing Step ST20 are needed is in any Map data identification information set. Each Map data presence information is to nonexistence set.

In step ST62, the updated in step ST18 Map data in the map buffer of the map data processor <b>15</b> stored. The map data presence information of a Card management data set according to the stored Map data is set to Available. The location of Map data in the map data position information set.

In step ST63 is determined whether it is necessary that obtained in step ST15 store update operation information. Is the time required is greater for updating in step ST18 or equal to a predetermined value, the process goes to Step ST63 through, and specifies that a storage is required. If not, 63193 00070 552 00004 63074 0002010200375 001000280000000200012000285916308200040 the process proceeds to Step ST19 above, and determined that the storage is unnecessary.

In step ST64, according to the Updating operation information management information of the memory device <b>16</b> for updated data in step ST15 obtained updating operation information in the storage device <b>16</b> stored for updated data, and will the Updating operation information management information updated. In this case, the Updating operation information in the storage device <b>16</b> stored for updated data, as already obtained updating operation information designated. When the storage capacity of the storage device<b>16</b> for updated data by storing the Updating operation information is exceeded, the updating operation information that the in storage device <b>16</b> stored for updated data, deleted, starting with those with the longest storage time, to a required, free area is determined and then the update operation information stored.

Furthermore, the map data which are in the Update data storage device <b>16</b> in step ST19 were stored, as already updated map data designated.

In step ST65 of the flowchart of <b>Fig.</b> 30 illustrated process performed. For the map data, the not in the cards buffer the map data processor <b>15</b> under the map data has been stored, for the Navigation processing of step ST20 are needed has already obtained Updating operation information or the already updated map data in the storage device <b>16</b> For updated data stored by the previously made updating operation request. In this Step, the map data for your by Updated obtained updating operation information were, or the already updated map data in which Map buffer of the map data processor <b>15</b> stored. These Processing is updated as again Get Map data refers.

In step ST20, the predetermined navigation processing carried out, by referring to the map data in the map buffer of the map data processor <b>15</b> saved are.

In <b>Fig.</b> 30, in step ST71 of Card management record of the card management information the map buffer of the map data processor <b>15</b> removed. The Card management information is sequentially bit by bit each time taken in their arrangement order when the process at this step comes, then comes the Process to step ST27. If no further Card Management data records exist for removing, is the processing of step ST20 ends.

If the map data presence information in step ST72 the extracted in step ST71 map management record indicates a non-presence, then the process goes to Step ST73 through, where it is determined that the Map data, the previously obtained Updating operation information, or already updated map data in the storage device <b>16</b> For updated data through the already made stored updating operation information request were. If a presence is displayed, the process goes to step ST71 above, will be determined on which that Map data to a recent version in the map buffer of Map data processor <b>15</b> were saved.

In step ST73 an inquiry is made as to whether the already obtained updating operation information of Map data by the Map data identification information of the step ST71 removed card management data file is specified, already in the storage device <b>16</b> for updated data have been stored or not on the basis of the Updating operation information management information of the memory device <b>16</b> for updated information. Is the already obtained not updating operation information available, then the process proceeds to step ST74. is it is present, the process proceeds to step ST75.

In step ST74, the already updated Map data by the Map data identification information of the step ST71 removed card management data set are specified, from the memory device <b>16</b> receive updated data.

In step ST75, the already obtained Update operation information of the map data, the by the map data of the identification information in the Step ST71 removed card management record is specified, from the memory device <b>16</b> for updated receive data. The map data generated by the Map data identification information of the step ST71 removed card management data set are specified, are prepared from the map data storage unit <b>13</b> removed. Like in Case of step ST18 is an update for the Map data on the basis of the previously obtained Updating operation information carried out, and then the process goes to step ST76.

In step ST76, the obtained in step ST74, already updated map data, or in step ST75 updated map data in the map buffer of Map data processor <b>15</b> stored. The Card management information as in the case of step ST62 updated, and then the process goes to step ST71 about.

Thereafter, the procedure of step ST71 and the following Steps for all card management records of Card management information is performed and then the Processing of step ST20 ends.

As described above, the Update operation information indicating that the required for the update processing time longer than the predetermined time, as the already updated Map data in the update data storage device <b>16</b> stored, and are already updated Map data extracted according to need. Therefore, the to re-obtaining the updated map data is less than or equal to a predetermined time.

EMBODIMENT 4

<b>Fig.</b> 31 is a flow chart showing the operation of a Map data processing device according to the fourth Embodiment, wherein the process of <b>Fig.</b> 12 Steps ST82 and ST82 are added. In step ST81 generates the updating operation information generator <b>24</b> the required information for respective nodes through Referring to Updating operation information request in Step ST2 was obtained. In step ST82, the Information regarding appropriate nodes in step ST81 was generated at the transmitter / receiver <b>14</b> by the Transmitter-receiver <b>21</b> transfer.

The updating operation information request in Step ST2 is included, contains the number of bits neighboring information, and bits of adjacent information according to the number or number. The adjacent Information is composed of an adjacent number, each Map data adjacent to map data indicating, by the Map data identification information in the Updating operation information request specified be, and the relevant version.

As described above occurs when only the map data are updated in a certain area, a Mismatch with respect to the correspondence of nodes, due to a version difference between the area and its adjacent area.

<b>Fig.</b> 32 shows a relationship between the regions of the Map data. A rectangular area 0 is a report the map data to the map data M ID, defined by the Map data identification information in the step ST2 obtained updating operation information request is specified. designate Rectangular Zones 1 to 8 Areas adjacent map data. The map data of the adjacent region are considered neighboring map data designated. Furthermore, in<b>Fig.</b> 31 specified numbers or figures used, the adjacent regions, and the define adjacent map data, and each of these Numbers than neighboring numeral.

In the <b>Fig.</b> 33A to 33E shows <b>Fig.</b> 33A is an example of the Road network of map data of a version V of map data ID; and shows<b>Fig.</b> 33B is an example of the road network of A map data version of the map data and V-ID of a Mb adjacent number 3 in addition to the above-mentioned Map data.

<b>Fig.</b> 33C shows a relation between the node and the Node record number of route calculation data in each of the <b>Fig.</b> 5A to 5J with respect to the road network of <b>Fig.</b> 33A; and <b>Fig.</b> 33D shows the node record number of the node of the Route calculation data in each of the <b>Fig.</b> 5A to 5J regarding on the road network of <b>Fig.</b> 33B.

Nodes N04, N05 and N06, and node N31, N32 and N33 located on the border of the regions of the respective Map data. The nodes N04 and N31 are the same node; the nodes N05 and N32 are the same node; and the node N06 and N33 are the same node.

To a node relationship between such neighboring display map data, for example, the node N31 the map data of the adjacent number 3 as adjacent Of the node N04 represents. Therefore, adjacent numbers Joined records of <b>Fig.</b> 5H assigned. Is an adjacent number equal to 0, then a Node, the adjacent through information related to a Node indicates a node of the map data. Is a adjacent number other than 0, then a through information for neighboring nodes specified nodes of a node Map data, which is indicated by the adjacent number. As an example of the related record of the node N04 is in <b>Fig.</b> 33E shown.

In the <b>Fig.</b> 34A to 34D shows <b>Fig.</b> 34A, a road network of Version VX wherein the node N03 of the road network of <b>Fig.</b> 34A is deleted; <b>Fig.</b> 34B shows a road network of Version VX at which the node N30 of the road network of <b>Fig.</b> 33B is deleted; and the<b>Fig.</b> Show 34C and 34D Node record numbers of the nodes of the road networks of <b>Fig.</b> 34A and 34B, respectively, being specifically shown, that the Node record numbers of the nodes N04, N05 and N06 on 3, 4 and 5 were amended by deleting the node N03, and the Node record numbers of the nodes N31 to N36 to 0 to 5 were amended, by deleting a node N30.

Each of the <b>Fig.</b> 35A to 35F shows the state only the Road network of <b>Fig.</b> 33A, the version of the VX has been updated on the basis of Updating operation information obtained from the step ST3 <b>Fig.</b> is generated 31st In detail<b>Fig.</b> 35A a Road network to that of identical <b>Fig.</b> 34A; <b>Fig.</b> 35B shows a road network, the identical to that of <b>Fig.</b> 33B; the<b>Fig.</b> 35C and 35D show node record numbers the road networks <b>Fig.</b> 34A and 34B; and the<b>Fig.</b> 35E, 35F show node record numbers of the nodes of the road networks of the <b>Fig.</b> 34A and 34B. For the information relating to the adjacent nodes of the associated record with the Number 1 related records by <b>Fig.</b> 35E is the Node record number of the version of V <b>Fig.</b> 34D used. For the information relating to the adjacent nodes of the connected record of the number 1 of the connected records of <b>Fig.</b> 35F, the node record number of Version V of <b>Fig.</b> 33C used. Therefore, in the<b>Fig.</b> 35E and 35F, the relationship between the road networks of <b>Fig.</b> 35A and 35B are not correctly represented. Thus, For example, in <b>Fig.</b> 35E, an adjacent node of the Node N04 to a node record number of 0, namely a Node N30. In<b>Fig.</b> 35F has an adjacent node of the Node N31 is a node record number 4, so a node N05. Thus occurs a mismatch between today adjacent to map data in different Versions are available.

In the <b>Fig.</b> 36A and 36B shows <b>Fig.</b> 36A correspondence between the node record numbers of node versions VX and V in the range of <b>Fig.</b> 35A; and shows<b>Fig.</b> 36B, the Correspondence between the node record numbers of Node versions VX and V in the range of <b>Fig.</b> 35B. From the Match each of the <b>Fig.</b> 36A and 36B, a Node record number in a desired version can be determined, and a mismatch between the adjacent map data in different versions, such as described above can be prevented.

Each of the <b>Fig.</b> 37A to 37C shows an example of the Data structure of information corresponding nodes in Step ST81 of <b>Fig.</b> is generated 31st As from<b>Fig.</b> 37A emerges, there is information with respect to corresponding node of a bias of the information in With respect to corresponding node, and from one or more Tables corresponding node. The biasing of information for appropriate node contains information data size for respective nodes of the data size Information concerning corresponding node indicating and Table number or table number corresponding node, which the number or numbers of tables corresponding Nodes of information regarding appropriate node indicates.

<b>Fig.</b> 37B shows the data structure of the table corresponding Node, the corresponding of a header of the table Node exists, and one or more corresponding Records. The leader of the table corresponding node map data contains identification information specifies map data ID, information relating to corresponding versions which have versions 0 and 1, and a correspondence between versions 0 and 1 indicates information with respect to adjacent map data represents an adjacent number, the card data adjacent to those map data indicating, by the Map data identification information are given, and a number of corresponding records, what the number or Number of corresponding records in the table corresponding Node indicates. If the Map data identification information map data M indicates the table corresponding node as appropriate Table of map data M indicates.

<b>Fig.</b> 37C shows the data structure of the Correspondence record. For the nodes in the map data, the identification information by the map data is given which is a node in the Map data is included, the adjacent through the Map data indicated, the Correspondence data set the node record number of the version 0 on, stored in the node record number 0, and the Node record number of the version 1, stored in the Node record # 1.

Everyone who <b>Fig.</b> 38A and 38B show an example of the Table corresponding node of the data structure in each of the <b>Fig.</b> 37A to 37C is shown. In detail<b>Fig.</b> 38A a correlation table, in which the neighboring Map data information of the map data of <b>Fig.</b> 35A the Map data <b>Fig.</b> 35B indicates; and shows<b>Fig.</b> 38B a Correlation Table, in which the neighboring Map data information of the map data of <b>Fig.</b> 35B, the Map data <b>Fig.</b> 35B indicates.

<b>Fig.</b> 39 is a flowchart showing, in detail, Processing of step ST81 of <b>Fig.</b> 31 shows.

In step ST91 are an adjacent number Ai and Version Vi as bits of adjacent information in the Step ST2 of <b>Fig.</b> 31 obtained removed updating operation information request, and then the process proceeds to step ST94 proceeds.

In step ST92 are a recent version VX and in the Step ST91 obtained version Vi compared. If a match is found, the process goes to Step ST91 through. In case of conflict is the Process to step ST93 above.

In step ST93, with reference to the Road network database <b>22</b> and the Road network upgrade database <b>23</b> a correspondence between the node record numbers of version of VX Map data by map data identification information in the updating operation information request to specify and obtain the node in the version Vi, and creates a table of corresponding nodes in everyone who <b>Fig.</b> 37A to 37C is shown. Furthermore, a Correspondence between the node record numbers of version VX of the map data adjacent to map data by the map data identification information in the Updating operation information request specified be, than the adjacent number Ai, and the nodes of obtain version Vi, and is a table of corresponding generated nodes in each of the <b>Fig.</b> 37A to 37C shown is. Then, the process proceeds to step ST91.

Thereafter, for all the bits of adjacent information in the Updating operation information request process the steps ST91, ST92 and ST93 performed.

is information on respective nodes in step ST94, in each of the <b>Fig.</b> 37A to 37C shown, produced under Using the table generated corresponding node, and so that the processing of step ST81 is completed.

<b>Fig.</b> 40 is a flowchart of an operation sequence Map data processing device according to a fifth Embodiment, wherein steps ST101 and ST102 the process of <b>Fig.</b> are added 16th In step ST13 the number of adjacent information in relation to the Map data of a region that is adjacent to a region in is the navigation processing is required, and adjacent information of Updating operation information request added, and from the transmitter / receiver <b>14</b> to the transfer map data providing station.

In step ST101, according to the Updating operation information request of Step ST13, information on appropriate nodes was sent from the map data providing station, of the transmitter / receiver <b>14</b> receive. Then, according to the management information for the table for corresponding Node of a storage section for the table a corresponding node in the storage device <b>14</b> For updated data is provided as shown in <b>Fig.</b> 41 shown a table corresponding node in the received Information concerning corresponding node in the storage device <b>16</b> stored for updated data. The Management information for the corresponding node table is used to manage the resort each table corresponding Node. When the storage capacity of the storage device<b>16</b> For updated data by storing the table corresponding node is exceeded, the tables corresponding nodes in the storage device <b>16</b> For updated data is stored, deleted, starting with those which are stored the longest, until a required free area can be ensured, and Then, the above-described table of Correspondences stored.

In step ST102, the tables corresponding nodes all map data Ma, in which the version of the Map data in the map data storage unit <b>13</b> is stored, the relative information by the adjacent map data of the corresponding node table updated in steps ST15 to ST19 map data Ma is specified, the version of the map data Ma matches, from the memory device <b>16</b> for updated Data deleted. Furthermore, under the tables corresponding node, in which the information for neighboring map data indicative of the map data Ma, those in wherein the version of the map data by the corresponding map data identification information is specified, that coincides with the map data Ma, from the memory device <b>16</b> deleted for updated data.

Through the above-described process, the table corresponding node, which thereby becomes unnecessary that both adjacent map data to latest versions be updated, deleted, so that the memory area of the memory device <b>16</b> efficient for updated data is being used.

If in step ST20 on the adjacent map data My a version Vy reference is made during a Reference to specific map data Mx one version Vx, and the version Mx and My version of one another differ, then on the basis of a table corresponding node, which shows a correlation with the Information regarding appropriate versions of My map data stored in the map data storage unit <b>13</b> stored, is located between the versions Mx and My, Referring to the map data My, using a Node record number that is obtained by the Node record number of the version Mx in those of Version My is converted.

For example, in the <b>Fig.</b> 35A to 35F and in the <b>Fig.</b> 37A to 37C with the values ​​Mx = Ma, My = Mb, Vx = VX and Vy = V, a reference to the adjacent node of the node N06 the node record number 5 the map data Ma of version Vx occurs, the node record number of the neighboring Node is equal to 2 from the map data Mb of the version VX <b>Fig.</b> 35E. From the correlation table (<b>Fig.</b> 38B) of the Map data Mb is therefore a corresponding data set determined, in which the node record number 0 is equal to 2 is, therefore, a corresponding data set # 2. Then a node in map data Mb version V, in which a Node record number represented by the node record number 1 the correspondence data set # 2 is specified, equal to 3, So a node N33, as an adjacent node set.

Using the table corresponding node is therefore a navigation processing is performed in which a Adaptation of map data in different versions was made.

In each of the above first to fourth Embodiments, the Updating operation information and the information for corresponding node of the transmitter / receiver <b>14</b> receive. However, such information also from a removable storage medium can be obtained, for example, a memory card.

In each of the first to fourth embodiments are the Map data storage unit <b>13</b> and the storage device <b>16</b> For updated data separately provided. However, these devices be united in a storage device, wherein, when the updated map data stored are, the map data of an old version in the area the map data can be deleted.

In each of the first to fourth embodiments, when the map data Updating operation information and the table corresponding node in the storage device <b>16</b> For updated data is stored, if the Storage capacity of the memory device <b>16</b> for updated is exceeded data, the map data, the Update Opera tion information and the table corresponding nodes in the storage device <b>16</b> For updated data is stored, deleted, starting with the oldest stored data. However, the Cancellation also at the order of the low frequency of Reference be made in the past took place. The deletion may also be in the order of data take place outside of a region is determined by the, that he needed for the next navigation processing is, or in the order of greatest distance from this Area. It can also be a cancellation under this combination Conditions occur.

In each of the above first to third the example was embodiments of Route calculation data shown. However, these Embodiments are used for all data, constituting map data.

In each of the first to third embodiments, the Version managed by a map data unit. though can a version independently of any data can be administered, which form the map data, and Update for all data to be carried out, constituting the map data.

In each of the first to third embodiments, for Updating the offsets and the record numbers in contained various records, without this as to obtain updated operation information Calculation from the map data and the Updating operation information before updating be made, and then updated it will.

In the foregoing third embodiment was in the Step ST63, the determination of whether a store required is performed on the basis of the processing time, which is required for updating. The requirement a storage can, however, also determined on the basis be whether the data size of the map data to the Update greater than or equal to a predetermined value is. The need for storage can found , when the data size of the free area of memory device <b>16</b> for updated data is less than or equal to a predetermined value.

Furthermore, it was in the foregoing fourth Embodiment, the example of route calculation data shown. However, the embodiment in all Data are used in reference to the road network, wherein the data constituting map data.

Further, in the fourth embodiment was the example considered that the common region of the adjacent Areas was a line. The common area of However, adjacent areas may also be a plane.

As is clear from the above explanations, is the present invention particularly with regard advantageous. includes the map data processing device the information obtaining device for obtaining Updating operation information indicating the Updating content of the map data indicates that in the Memory device are stored, as well as the Updating means for updating the map data, stored in the memory device, in accordance with updating the operation information of the Information obtaining device is obtained. Therefore, it is possible to update the map data quickly.

The information acquisition device obtains the Updating operation information containing updated location information, where too be updated in part by an offset against a representing predetermined reference position in the map data becomes. Therefore, it is possible to quickly determine the part, to be updated.

receives the information acquisition device Updating operation information among data in map data is included, setting information data contains to set the data to be updated, and Updating position information, the record one indicates in which the data is stored. Therefore, it is possible to quickly update the map data, without is the structure complicated.

receives the information acquisition device Updating operation information containing updated location information, at least one or more updating positions in the data set indicates. It is therefore possible, partial data in the update record.

receives the information acquisition device Updating operation information which includes updating type information that the Update type at least one or more parts indicating to be updated in the data set. On Thus, it is possible to provide several Update operations of different types at once perform in the same record.

The data storage device is provided for the to store updated operation information of the information obtaining device is obtained when the Update time updating device the exceeds predetermined reference time, and to store the Map data after updating by the Update device when the update time is shorter than the predetermined reference time. Therefore, it is possible quickly Neuerlangungsverarbeitung the conduct updated map data.

The data storage device is provided for the to store updated operation information of the information obtaining device is obtained when the determined processing time for updating the Update device the predetermined reference time exceeds, and the map data after updating storing by the updating device when the determined processing time for updating shorter than the predetermined reference time. This is enables fast a Neuerlangungsverarbeitung the conduct updated map data.

When the memory device stores the map data, then, if the version of a specific area different from that of another region, information from corresponding nodes obtained a Correspondence between identical nodes of respective versions indicates. Even if the map data has been stored, but the version of a particular region to one of those the other area is different, it is possible to perform customized navigation processing.

The information acquisition device obtains information with respect to the corresponding node only if the versions the areas which are adjacent to each other are different, wherein the information obtained from corresponding Node relates to identical nodes, the adjacent are areas available. This allows an efficient Use of the storage device.

The information obtaining device obtains, in each neighboring areas, only the information relating corresponding node for the same node in the is overlapping part of the two spaces. This allows efficient use of the storage device.

It will receive the update operation information, indicating the update content of the map data, and the map data corresponding to the Updating operation information updated. This enables rapid updating of map data.

It will receive the update operation information, containing the update position information in which the site to be updated by an offset from the predetermined reference position in the map data represented. This makes it possible to quickly to understand updating part.

Among the data included in the map data, receive data defining information indicating the to updated data sets, as well as the Update operation information indicating the includes updating position information indicating the indicates data in which the data is stored. This makes it possible to quickly find the map data to Update without the structure becomes complicated.

It will receive the update operation information, containing the update position information at least one or more positions in the update indicating record. Therefore, partial data in the Record to be updated.

It will receive the update operation information, containing the update type information that the Update types of at least one or more parts indicating to be updated in the data set. Therefore, at a time several update operations of different types can be performed.

If the refresh rate of the map data, the predetermined exceeds reference time, the obtained Updating operation information stored. Is the Update time less than the predetermined reference time, the map data is stored after updating. This makes it possible to quickly create a Neuerlangungsverarbeitung perform the updated map data.

When the determined update time of the map data exceeds the predetermined reference time, the obtained Updating operation information stored. If the determined update time is less than the predetermined reference time, the map data to be the Update stored. This enables quickly Neuerlangungsverarbeitung the updated perform map data.

If map data are stored, it will, when the Version a certain range from that of the other Region differs, information concerning appropriate Nodes receive which correspondence between identical nodes of the respective versions indicates. thats why it even when the map data has been stored, when the version of a particular region of that of a other region is different, possible an adapted execute navigation processing.

The information regarding the appropriate node will only be obtained when the versions of adjacent one another Areas different from each other, wherein the obtained Information concerning corresponding node the identical Node relates to that in the adjacent areas available. This enables efficient use of the Memory device.

It is only the information relating to a corresponding node obtained for the same node in the overlapping portion is the adjacent spaces. This allows efficient use of the storage device.

FIGURE LABEL

Fig.

1

<b>11</b>

input device

<b>12</b>

Vehicle position detector

<b>13</b>

Map data storage unit

<b>14</b>

Transmitter-receiver

<b>15</b>

Map data processor

<b>16</b>

Storage device for updated data

<b>17</b>

output device

Fig.

2

<b>21</b>

Transmitter-receiver

<b>22</b>

Road network database

<b>23</b>

Road network upgrade database

<b>24</b>

Updating operation information generator

Fig.

3

Map Information: Ticket InformationManagement Information: Management InformationMap Data: map dataHeader: headerRoad Data: road dataBackground Data: Background dataName Data: Name DataRoute Guiding Data: routing dataRout Calculation Data: route calculation dataLocal Facility Data: data on local facilitiesGuiding SearchDataCenter: Web guide data

Fig.

5A

Route Calculation Data: route calculation dataRoute Calculation Header: route calculation biasNode Table: Node TableConnection information: Connection informationCost Table: Costs

Fig.

5B

Route Calculation Header: route calculation biasOffset of Node Table: Offset the node tableData Size of Node Table: data size of the node tableOffset of Connection Information: Offset of connection informationData Size of Connection Information: data size of connection informationOffset of Cost Table: Offset the CostsData Size of Cost Table: data size of Costs

Fig.

5C

Node Table: Node TableNode Record: node recordNode Record Number: node record number

Fig.

5D

Connection information: Connection informationConnected Record: Bandaged recordConnected Record Number: number of the connected record

Fig.

5E

Cost Table: CostsCost Record: cost recordCost Record Number: Issue costs dataset.

Fig.

5F

Node Record: node recordNode Coordinate: KnotenkoordinateNode attributes: attribute nodeNumber of Connected Links: number (number) connected compoundsNumber of Regulated Records: number (number) Regulated recordsOffset of Connected Record: offset of the associated record

Fig.

5G

Connected Record: Bandaged recordLinked Record: Linked recordRegulated Record: Regulated recordRegulated Record Number: number of regulated data set

Fig.

5H

Linked Record: Linked recordAdjacent Node Information: Information on neighboring nodeLinked cost information: information about associated costs

Fig.

5I

Regulated Record: Regulated recordEntry Link Information: Access link informationExit Link Information: output link informationInter-Link Regulated Code: provision on rules between shortcuts

Fig.

5J

Cost Record: cost recordLink attributes: link attributeLink Length: link lengthAverage Traveling Time: Average travel timeWidth Information: Information related to the width

Fig.

6

Node Table: Node TableNode Record Number: number of the node recordNode Coordinate: KnotenkoordinateNode attributes: attribute nodeNumber of Connected links: number of connected linksNumber of Regulated Records: number of regulated recordsOffset of Connected Record: offset of the associated record

Fig.

7

Connection information: Connection informationLinked Record: Linked recordRegulated Record: Regulated recordConnected Record Number: number of the connected recordLinked Record Number: number of the linked recordAdjacent Node Information: Information on neighboring nodeEntry Link Information: Access link informationInter-Link Regulated Code: provision on rules between shortcutsHatched Part Indicated Non-Presence of Target Linked Record,Regulated Record: Hatched part is absence the destination link dataset, regulated data record toOffset of Connected Record: offset of the associated recordRegulated Record Number: number of regulated data setLinked cost information: information about associated costsExit Link Information: output link information

Fig.

8th

Cost Table: CostsCost Record Number: cost record numberLink Length: link lengthAverage Traveling Time: Average travel timeWidth Information: width information

Fig.

9

Node Table: Node TableNode Record Number: KnotendatensatznunmerNode Coordinate: KnotenkoordinateNode attributes: attribute nodeNumber of Connected links: number of connected linksNumber of Regulated Records: number of regulated recordsOffset of Connected Record: offset of the associated record

Fig.

10

Connection information: Connection informationLinked Record: Linked recordRegulated Record: Regulated recordConnected Record Number: number of the connected recordLinked Record Number: number of the linked recordAdjacent Node Information: Information on neighboring nodeEntry Link Information: Access link informationInter-Link Regulated Code: provision on rules between shortcutsHatched Part Indicated Non-Presence of Target Linked Record,Regulated Record: Hatched part is absence the destination link dataset, regulated data record toOffset of Connected Record: offset of the associated recordRegulated Record Number: number of regulated data setLinked cost information: information about associated costsExit Link Information: output link information

Fig.

11

Cost Table: CostsCost Record Number: cost record numberLink Length: link lengthAverage Traveling Time: Average travel timeWidth Information: width information

Fig.

12

No: NoYes YesST1: Is a Updating operation information request yet?ST2: updating operation information request receiveST3: generate updated operational informationST4: Send updating operation information

Fig.

13A

Updating operational information: Updating operation informationUpdating operation information header: Updating operation information headerData Size of updating operation information: data size of Updating operation informationMap Data Identification Information: Map data identification informationUpdate Version Information: Update Version InformationNumber of update segment: number of update segmentsUpdate Segment: Segment Update

Fig.

13B

Update Segment: Segment UpdateUpdate segment header: update segment headerDateType Information: Data Type InformationUpdate Type Information: update type informationUpdating position Division: updating position divisionNumber of Updated Records: number of updated recordsUpdated Record: Updated data

Fig.

13C

Updated Record (Offset Type): Updated data (Offset Type)Head Offset: Offset headUpdated Data Size: Size of updated dataUpdate PartsData: update part data

Fig.

13D

Updated Record (Record Type): Updated data (Record type)Head Record Number: head record numberNumber of Update Part Records: number of Update part recordsUpdate Part Record: update part record

Fig.

14A

Data Type Information: Data Type InformationValue: ValueData Type: Data typeRoute Calculation header of Route Calculation Data: Route calculation bias of route calculation dataNode Table of Route Calculation Data: Table of node Route calculation dataConnection information of Route Calculation Data: Link information from route calculation dataCost Table of Route Calcualtion Data: Costs of Route calculation data

Fig.

14B

Update Type Information: update type informationValue: ValueUpdating operation: update operationDeletion: DeletionSubstitution: ReplacementAddition: Addition

Fig.

14C

Updating position Division: updating position divisionValue: ValueDivision: DivisionOffset Type: Offset TypeFixed Length Record Type: Record Type Fixed LengthVariable Length Record Type: Record Type variable length

Fig.

15

Update Segment: Segment UpdateUpdate segment header: update segment headerData Type Information: Data Type InformationUpdate Type Information: update type informationUpdating position Division: updating position divisionNumber of Updated Records: number (number) updated recordsUpdated Record: Updated dataHead Offset: Offset headUpdated Data Size: Size of updated dataUpdate PartsData: update part dataHead Record Number: head record numberNumber of Updated Records: number (number) updated recordsUpdate Part Record: update part record4-Byte Data Indicating Data Size of Connection Information After Updating: data with 4 bytes, the data size of the specify connection information after update4-Byte Data Indicating offset of Cost Table Head After Updating: data with 4-byte, the offset of specify cost table header after updateNode Record Where Node Number of

<b>Fig.</b>

9 Is n: Node record when node number of

<b>Fig.</b>

9 is equal to nConnected Record Where Connected Record Number of

<b>Fig.</b>

10 Is j: Bandaged record when number of connected Data set from

<b>Fig.</b>

10 is equal to jCost Record Where Cost Record Number of

<b>Fig.</b>

11 Is c: Cost record when cost record number of

<b>Fig.</b>

11 is equal to c

Fig.

16

ST11: InputST12: get vehicle positionST13: Request updated operation informationST14: obtained updating operation informationST15: see update operation informationNo: NoYes YesST16: Is upgrade required?ST17: take map dataST18: update map dataST19: save map dataST20: execute navigation processing

Fig.

17

ST21: Initialize segment definitionST22: Is an update segment yet?No: NoYes YesEnd: endST23: determining the updated record initializeST24: Is an updated record yet?ST25: Check type of update informationDelete: DeleteSubstitute: ReplaceAdd: AddST26: perform deletionST27: Run AdditionST28: perform replacementST29: Update determining the updated recordST30: Update segment definition

Fig.

18

Update Type Information: update type informationValue: ValueUpdating operation: update operationDeletion: DeletionSubstitution: ReplacementAddition: AdditionSingle Type Partial Updating: Partial update of single typeComposite Type Partial Updating: Partial update of composite type

Fig.

19A

Updated Record: Updated dataUpdated Record Header: biasing the updated recordRecord Number: Record NumberPartial Update Type Information: Information regarding type partial updateUpdating position Division: updating position divisionNumber of Partially Updated Records: number (number) partially updated recordsPartially Updated Record: Partially updated data

Fig.

19B

Partially Updated Record (Offset Type): Partially updated record (offset type)Head Offset: Offset headUpdated Data Size: Size of updated dataUpdate PartsData: update part data

Fig.

19C

Partially Updated Record (Record Type): Partially updated record (record type)Partial Data Type Information: Information regarding type partial dataHead Record Number: head record numberNumber of Update Part Records: number (number) of Update part recordsUpdate Part Record: update part record

Fig.

20A

Updated Record: Updated dataUpdated Record Header: biasing the updated recordRecord Number: Record NumberNumber of Partially Updated Records: number (number) partially updated recordsPartially Updated Record: Partially updated data

Fig.

20B

Partially Updated Record (Offset Type): Partially updated record (offset type)Partially UpdateType information: information regarding type partial updateUpdating position Division: updating position divisionHead Offset: Offset headUpdated Data Size: Size of updated dataUpdate PartsData: update part data

Fig.

20C

Partially Updated Record (Record Type): Partially updated record (record type)Partial Update Type Information: Information regarding type partial updateUpdating Positon Division: updating position divisionPartial Data Type Information: Information regarding type partial dataHead Record Number: head record numberNumber of Update Part Records: number (number) of Update part recordsUpdate Part Record: update part record

Fig.

21

Value: ValueData Type: Data typeLinked Record Array: Field of linked recordsRegulated Record array: field of regulated records

Fig.

22A

Single Type Partial Updating of Node Record: Partial Update (single-type) of a node recordUpdated Record Header: biasing the updated recordRecord Number: Record NumberUpdate Type Information: update type informationUpdating position Division: updating position divisionNumber of Partially Updated Records: number (number) partially updated recordsHead Offset: Offset headUpdated Data Size: Size of updated dataUpdate PartsData: update part data

Fig.

22B

Single Type Partial Updating of Connected Record: Partial Update (single-type) of an associated recordUpdated Record Header: biasing the updated recordRecord Number: Record NumberUpdate Type Information: update type informationUpdating position Division: updating position divisionNumber of Partially Updated Records: number (number) partially updated recordsPartially Updated Record: Partially updated dataPartial Data Type: type of partial dataHead Record Number: head record numberNumber of Update Part Records: number (number) of Update part recordsUpdate Part Record: update part recordContent of Link Record Where Linked Record Number of Connected Connected Record of Record Number of j

<b>Fig.</b>

10 Isp: content of the linked record when Issue linked record the associated record with the Number j of the associated record of

<b>Fig.</b>

10 is equal to p Content of Regulated Record Where Regulated Record Number of Connected Connected Record of Record Number of j

<b>Fig.</b>

10 isp: content of the regulated record if Issue Regulated record the associated record with the Number j of the associated record of

<b>Fig.</b>

10 is equal to p

Fig.

23

Composite Type Partial Updating of Connected Record: Partial update (composite type) connected a recordUpdated Record Header: biasing the updated recordRecord Number: Record NumberNumber of Partially Updated Records: number (number) partially updated recordsPartially Updated Record: Partially updated dataUpdate Type Information: update type informationUpdating position Division: updating position divisionPartial Data Type: type of partial dataHead Record Number: head record numberNumber of Update Part Records: number (number) of Update part recordsUpdate Part Record: update part recordContent of Linked Record Where Linked Record Number of Connected Connected Record of Record Number of j

<b>Fig.</b>

10 Isp: content of the linked record when Issue linked record of the linked record with the Number j of an associated record of

<b>Fig.</b>

10 equal to p is

Fig.

24

ST25: Check type of update informationDeletion: DeletionAddition: AdditionSubstitution: ReplacementSingle Type Partial Updating: Partial Update (Single type)Composite Type Partial Updating: Partial Update (Composite type)To: AfterST31: Update single type partST32: Update composite type part

Fig.

25

ST41: Set target record definitionST42: Set update operation down and Updating position division downST43: determining the partial updated record initializeST44: Is a partially updated data available?No: NoYes YesEnd: endST45: Perform Partial UpdateST46: determining the partial updated record update

Fig.

26

ST51: Set target record definitionST52: determining the partial updated record initializeST53: Is a partially updated data available?No: NoYes YesEnd: endST54: update operation down andSet updating position division downST55: Perform Partial UpdateST56: determining the partial updated record update

Fig.

27

Updating Operation Information Storage Section: Updating operation information storage sectionUpdating operation information management information: Updating operation information management informationUpdating operational information: Updating operation information

Fig.

28

Map Buffer: Buffer CardsMap Management Information: Card Management InformationThe Number of Map Data: The number (s) of card dataMap Management Record: Card management recordMap Data: map data

Fig.

29

ST11: InputST12 :. get vehicle positionST13: Request updated operation informationST14: obtained updating operation informationST61: initialize card management informationST15: Is extracted updating operation information available?No: NoYes YesST16: Is upgrade required?ST17: take map dataST65: receive updated map data againST18: update map dataST62: store card data in the card bufferST63: Is storage required?ST19. Save card detailsST64: Save Refresh OperationInfo NationST20: execute navigation processing

Fig.

30

ST71: Is of removed cards administrative record available?No: NoYes YesEnd: endST72: Are map data available?ST73: Is updating operation information available?ST74: get map dataST75: run updateST76: store card data in the card buffer

Fig.

31

ST1: Is updating operation information request available?No: NoYes YesST2: updating operation information request receiveST3: generate updated operational informationST81: Generate information on corresponding nodeST4: Send updating operation informationST82: Send information via corresponding node

Fig.

33C,

Fig.

33D

Node: NodeNode Record Number: node record number

Fig.

33E

Linked Record Number: number of the linked recordAdjacent Node information: information regarding neighboring nodeLink Cost Information: link cost informationAdjacent Number: Adjacent numberInvalid Value: Invalid valueCost Record Number of Link Between N00 And N04:Cost record number of link between N00 and N04

Fig.

34C,

Fig.

34D

Node: NodeNode Record Number: node record number

Fig.

35C,

Fig.

35D

Node: NodeNode Record Number: node record number

Fig.

35E,

Fig.

35F

Node: NodeLinked Record Number: number of the linked recordAdjacent Node Information: Information on neighboring nodeLinked cost information: information about associated costsAdjacent Number: Adjacent numberInvalid Value: Invalid value

Fig.

36A

Fig.

36B

Node: NodeNode Record Number of version: node record number of version

Fig.

37A

Corresponding Node Information: Information about corresponding nodeCorresponding Node Information Header: biasing the Information on appropriate nodeCorresponding Node Information Data Size: Data size Information on appropriate nodeNumber of Corresponding Node Tables: number (number) of Tables corresponding nodeCorresponding Node Table: Table corresponding node

Fig.

37B

Corresponding Node Table: Table corresponding nodeCorresponding Node TableHeader: biasing the table corresponding nodeMap Data Identification Information: Map data identification informationCorresponding version information: Information about appropriate versionVersion: VersionAdjacent Map Data Information: Information about neighboring card informationNumber of Corresponding Records: number (number) appropriate recordsCorresponding Record: Correspondent record

Fig.

37C

Corresponding Record: Correspondent recordNode Record Number: node record number

Fig.

38A

Fig.

38B

Corresponding Node Table: Table corresponding nodeMap Data Identification Information: Map data identification informationCorresponding version information: Version of Information about appropriate versionAdjacent Map Data Information: Information about neighboring card informationNumber of Corresponding Records: number (number) appropriate recordsCorresponding Node Header: bias corresponding nodeCorresponding Record: Correspondent recordNode Record Number: node record number

Fig.

39

ST91: Is taken Nachbarkeitsinformation yet?No: NoYes YesCoincident: matchNon-Coincident: No MatchST92: compare versionsST93: Create table corresponding nodeST94: Generate information on corresponding nodeEnd: end

Fig.

40

ST11: InputST12: get vehicle positionST13: Request updated operation informationST14: obtained updating operation informationST15: Is extracted updating operation information available?No: NoYes YesST16: Is upgrade required?ST17: take map dataST18: update map dataST19: save map dataST101: receive information about appropriate nodeST102: Delete table corresponding nodeST20: execute navigation processing

Fig.

41

Corresponding Node Table Storage Section: storage section for table corresponding nodeCorresponding Node Table Management Information: Management information table corresponding nodeCorresponding Node Table: Table corresponding node

Fig.

42

Prior Art: art

<b>1</b>

information Centre

<b>2</b>

transmitter

<b>3</b>

receiver

<b>5</b>

Map data processor

<b>6</b>

input device

<b>7</b>

output device

<b>13</b>

Map data storage unit (Below the arrow in

<b>Fig.</b>

42): Delete the link between N2 and N5Delete the link between N5 and N7Add shortcut to between N3 and N6Delete N5 and N7

Fig.

43C

Node: NodeNode Number of: number of nodesNone: None