# US 8,543,618 B2 · Apparatus, program, and method for map data update > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,543,618 B2 - Document ID: US8543618B2 - Status: Granted - Kind: B2 - Application number: 12/458,379 - Filed: 2009-07-09 - Published: 2010-01-28 - Granted: 2013-09-24 - Earliest claimed: 2008-07-25 - Assignees: Denso Corporation; Kousokuya, Inc. - Applicants: Hidetoshi Fujimoto; Toshio Nomura; Yasutaka Atarashi; Toshio Shinjo; Akio Samizu - Inventors: Hidetoshi Fujimoto; Toshio Nomura; Yasutaka Atarashi; Toshio Shinjo; Akio Samizu - Web page: https://patentgrep.com/patent/US8543618B2 ## CPC - G01C 21/3878: {Hierarchical structures, e.g. layering} - G01C 21/3815: {Road data} - G06F 16/29: Geographical information databases - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract In map data having link information, each of the links has reference information regarding a start point node of the link, a next link in a series of links, and an upper link. Further, links are memorized in a form of link list, and the position of the link in the link list is not changed in the course of adding/deleting a link, thereby enabling a direct reference to each of the links in the link list by the position of the link. The link information organized in the above-described manner enables the ease of the update of the map data as well as the speed-up of the calculation of, for example, a navigation route. ## Claims ### Claim 1 A map data update apparatus having a link list for link management in map data by using update data that updates the link list, the update data specifies position information of a subject link to be updated in the link list, the apparatus comprising: a memory configured to store a link list; and a processor, the processor configured with a link addition enhancer for enhancing the link list stored in the memory so that the link list includes the position information specified by the update data, when the position information is currently non-existent in the link list; an information update unit for updating information on the link in the memory that is in association with the position information specified by the update data based on the update data, wherein each of the links represents a road in the map data, successive links respectively having same road attributes are defined as a link series in the map data, each of the links in a specific link series has reference information to point to an immediate subsequent link of said each of the links in the specific link series, a last link in the link series has a nonexistent pseudo-link that serves as the immediate subsequent link of the last link in the link series, the processor is further configured to divide an existing link into two links, the existing link of the link series, before the existing link is divided into the two links, has reference information to point a link N as the immediate subsequent link of the existing link, the existing link, after being divided into the two links, remains the existing link as indicated by having a same link identifier, and the link series then further includes a new link divided from the existing link, the new link has reference information to point to the link N as the immediate subsequent link of the new link in the link series, and the existing link after being divided has reference information changed to point the new link as the immediate subsequent link of the existing link in the link series. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein the map data has a hierarchy of multiple levels, and each of the links in lower levels has the reference information to point to a link in higher levels. ### Claim 3 (depends on 1) The apparatus of claim 1, wherein each of the links in the link series is managed in a list form, and the position of each of the links that exists in the list series is kept unchanged in the list form in the update of the link list. ### Claim 4 A program product stored in a non-transitory computer-readable storage medium having instructions, when executing causing a computer to perform steps of a method, the method of updating map data having a link list for link management in map data based on update data that, for updating of the link list, specifies position information of a subject link to be updated in the link list, the method comprising: enhancing the link list so that the link list includes the position information specified by the update data, when the position information is currently non-existent in the link list; updating information on the link that is in association with the position information specified by the update data based on the update data; and dividing an existing link into two links, wherein each of the links represents a road in the map data, successive links respectively having same road attributes are defined as a link series in the map data, each of the links in a specific link series has reference information to point to an immediate subsequent link of said each of the links in the specific link series, a last link in the link series has a nonexistent pseudo-link that serves as the immediate subsequent link of the last link in the link series, the existing link of the link series, before the existing link is divided into the two links, has reference information to point a link N as the immediate subsequent link of the existing link, the existing link, after being divided into the two links, remains the existing link as indicated by a same link identifier, and the link series then further includes a new link divided from the existing link, the new link has reference information to point to the link N as the immediate subsequent link of the new link in the link series, and the existing link after being divided has reference information changed to point the new link as the immediate subsequent link of the existing link in the link series. ### Claim 5 (depends on 4) The program product of claim 4, wherein the map data has a hierarchy of multiple levels, and each of the links in lower levels has the reference information to point to a link in higher levels. ### Claim 6 (depends on 4) The program product of claim 4, wherein each of the links in the link series is managed in a list form, and the position of each of the links that exists in the list series is kept unchanged in the list form in the update of the link list. ### Claim 7 A method of updating map data having a link list for link management in map data based on update data that, for updating of the link list, specifies position information of a subject link to be updated in the link list, the method comprising: enhancing the link list so that the link list includes the position information specified by the update data, when the position information is currently non-existent in the link list; updating information on the link that is in association with the position information specified by the update data based on the update data; and dividing an existing link into two links, wherein each of the links represents a road in the map data, successive links respectively having same road attributes are defined as a link series in the map data, each of the links in a specific link series has reference information to point to an immediate subsequent link of said each of the links in the specific link series, a last link in the link series has a nonexistent pseudo-link that serves as the immediate subsequent link of the last link in the link series, the existing link of the link series, before the existing link is divided into the two links, has reference information to point a link N as the immediate subsequent link of the existing link, the existing link, after being divided into the two links, remains the existing link as indicated by a same link identifier, and the link series then further includes a new link divided from the existing link, the new link has reference information to point to the link N as the immediate subsequent link of the new link in the link series, and the existing link after being divided has reference information changed to point the new link as the immediate subsequent link of the existing link in the link series. ### Claim 8 (depends on 7) The method of claim 7, wherein the map data has a hierarchy of multiple levels, and each of the links in lower levels has the reference information to point to a link in higher levels. ### Claim 9 (depends on 7) The method of claim 7, wherein each of the links in the link series is managed in a list form, and the position of each of the links in the link series is kept unchanged in the list form in the update of the link list. ### Claim 10 (depends on 1) The apparatus of claim 1, further comprising a link deletion processor for updating the link list by deleting the position information specified by the update data, when the update data indicates that the position information is to be deleted from the link list. ### Claim 11 (depends on 1) The apparatus of claim 1, wherein a first link of the link series, the first link having information that includes (i) position information of the first link and (ii) reference information to point to a second link, the second link is a link that is the immediate subsequent link from the first link. ### Claim 12 (depends on 1) The apparatus of claim 1, wherein when a new link is added, the new link is added to an end of the link list, the new link having information that includes (i) position information of the new link and (ii) reference information to point to the immediate subsequent link from the new link. ### Claim 13 (depends on 1) The apparatus of claim 1, wherein when the subject link in the link list is deleted, information in the link list corresponding to the subject link is filled with a void value. ### Claim 14 (depends on 1) The apparatus of claim 1, wherein the existing link and the new link of the link series each includes reference information regarding an upper link, the upper link of the existing link and the new link is the same. ### Claim 15 (depends on 4) The program product of claim 4, further comprising updating the link list by deleting the position information specified by the update data, when the update data indicates that the position information is to be deleted from the link list. ### Claim 16 (depends on 4) The program product of claim 4, wherein a first link of the link series, the first link having information that includes (i) position information of the first link and (ii) reference information to point to a second link, the second link is a link that is the immediate subsequent link from the first link. ### Claim 17 (depends on 4) The program product of claim 4, wherein when a new link is added, the new link is added to an end of the link list, the new link having information that includes (i) position information of the new link and (ii) reference information to point to the immediate subsequent link from the new link. ### Claim 18 (depends on 4) The program product of claim 4, wherein when the subject link in the link list is deleted, information in the link list corresponding to the subject link is filled with a void value. ### Claim 19 (depends on 4) The program product of claim 4, wherein the existing link and the new link of the link series each includes reference information regarding an upper link, the upper link of the existing link and the new link is the same. ### Claim 20 (depends on 7) The method of claim 7, further comprising updating the link list by deleting the position information specified by the update data, when the update data indicates that the position information is to be deleted from the link list. ### Claim 21 (depends on 7) The method of claim 7, wherein a first link of the link series, the first link having information that includes (i) position information of the first link and (ii) reference information to point to a second link, the second link is a link that is the immediate subsequent link from the first link. ### Claim 22 (depends on 7) The method of claim 7, wherein when a new link is added, the new link is added to an end of the link list, the new link having information that includes (i) position information of the new link and (ii) reference information to point to the immediate subsequent link from the new link. ### Claim 23 (depends on 7) The method of claim 7, wherein when the subject link in the link list is deleted, information in the link list corresponding to the subject link is filled with a void value. ### Claim 24 (depends on 7) The method of claim 7, wherein the existing link and the new link of the link series each includes reference information regarding an upper link, the upper link of the existing link and the new link is the same.