Spatial indexing method and apparatus for navigation system for indexing and retrieval of XML map data

• US 20100287207A1
• Filed: 05/08/2009
• Published: 11/11/2010
• Est. Priority Date: 05/08/2009
• Status: Active Grant

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Motoyama, Masaki
• Granted Patent: US 8,532,925 B2
• Time in Patent Office: Days
• US Class Current: 707/803
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A method and apparatus efficiently assigns the spatial index numbers to map cells that divide an area which is a unit of administrative region into a plurality of small units. The method includes the steps of: establishing a plurality of map cells that divide an administrative region expressed by XML map data which is configured in a multiple-layered structure; determining a layer in the XML map data on which the map cells are established; selecting a type of tracing curve for sequentially indexing the plurality of map cells; assigning index numbers consecutively to the map cells with the sequence of the tracing curve; and repeating foregoing steps for all of the map cells in all of the layers of the XML map data, thereby creating a map database in the XML format with the spatial indexes for all of the map cells.

Claims

1. A method of spatial indexing a plurality of map cells and retrieving map data from the map cells for a navigation system utilizing XML map data, comprising the following steps of:

establishing a plurality of map cells for spatial indexing where the map cells divide an administrative region expressed by XML map data into small units where the XML map data is configured in a multiple-layered structure;

determining a layer in the multiple-layered structure of the XML map data on which the map cells are established for the spatial indexing;

selecting a type of tracing curve for sequentially indexing the plurality of map cells that divide the administrative regions;

assigning index numbers consecutively to the plurality of map cells with the sequence determined by the selected tracing curve; and

repeating foregoing steps for all of the map cells in all of the layers of the XML map data, thereby creating a map database in the XML format with the spatial indexes for all of the map cells.

2. A method of spatial indexing and retrieving the map data as defined in claim 1, further comprising a step of selecting the map cells by generating address data that correspond to the index numbers assigned to the map cells for retrieving the XML map data from the map database.

3. A method of spatial indexing and retrieving the map data as defined in claim 1, wherein said sequence of the tracing curve for indexing the map cells is created by combining X-address data and Y-address data of the map cells into one dimensional data.

4. A method of spatial indexing and retrieving the map data as defined in claim 3, wherein said sequence of the tracing curve for indexing the map cells is created by combining X-address data Xi and Y-address data Yi into one dimensional data (Xi, Yi):

Xi Ω

Yi→

Value (X3 Y3 X2 Y2 X1 Y1 X0 Y0)_n binary bit integer.

5. A method of spatial indexing and retrieving the map data as defined in claim 3, wherein said tracing curve is an N-shape curve or a U-shape curve, where the U-shape curve or U-shape curve is adaptable to three dimensional curve representation for a given spatial sequence whose coordinates x_n, y_n and z_n (n=0,1,2 . . . N, where N is the length of the spatial sequence) are uniquely determined by the N/U transformation of spatial sequence.

6. A method of spatial indexing and retrieving the map data as defined in claim 3, further comprising a step of providing cost information on virtual links that connect boundary nodes on the administrative regions on layers higher than a base layer in the layered structure of the XML map data, and a step of providing cost information on physical links on the base layer of the layered structure of the XML map data.

7. A method of spatial indexing and retrieving the map data as defined in claim 6, further comprising a step of searching routes between a start point and a destination when the destination is specified by a user by selecting candidate virtual links that connect the boundary nodes of different administrative regions on a particular layer of the map data by evaluating the cost information on the virtual links.

8. A method of spatial indexing and retrieving the map data as defined in claim 7, wherein the cost information is computed based on a distance, a travel time, and predetermined cost space factors for each virtual link and physical link where the cost information on the virtual links on a particular layer is established on a layer of the map data that is immediately higher than the particular layer and stored in a form of cost tables.

9. A method of spatial indexing and retrieving the map data as defined in claim 1, wherein said administrative regions include cities, counties, states, and countries in the order of lower layer to higher layer in the layered structure of the XML map data.

10. A method of spatial indexing and retrieving the map data as defined in claim 9, wherein the layered structure of the XML map data is configured by an international layer for connecting the boundary nodes between two or more countries, a country layer for connecting the boundary nodes between two or more states within the country, a state layer for connecting the boundary nodes between two or more counties within the state, a county layer for connecting the boundary nodes between two or more cities within the county, and a city layer which is the base layer with the physical links.

11. An apparatus for spatial indexing a plurality of map cells and retrieving map data from the map cells for a navigation system utilizing XML map data, comprising:

means for establishing a plurality of map cells for spatial indexing where the map cells divide an administrative region expressed by XML map data into small units where the XML map data is configured in a multiple-layered structure;

means for determining a layer in the multiple-layered structure of the XML map data on which the map cells are established for the spatial indexing;

means for selecting a type of tracing curve for sequentially indexing the plurality of map cells that divide the administrative regions;

means for assigning index numbers consecutively to the plurality of map cells with the sequence determined by the selected tracing curve; and

means for repeating foregoing steps for all of the map cells in all of the layers of the XML map data, thereby creating a map database in the XML format with the spatial indexes for all of the map cells.

12. An apparatus for spatial indexing and retrieving the map data as defined in claim 11, further comprising means for selecting the map cells by generating address data that correspond to the index numbers assigned to the map cells for retrieving the XML map data from the map database.

13. An apparatus for spatial indexing and retrieving the map data as defined in claim 11, wherein said sequence of the tracing curve for indexing the map cells is created by combining X-address data and Y-address data of the map cells into one dimensional data.

14. An apparatus for spatial indexing and retrieving the map data as defined in claim 13, wherein said sequence of the tracing curve for indexing the map cells is created by combining X-address data Xi and Y-address data Yi into one dimensional data (Xi, Yi):

Xi Ω

Yi→

Value (X3 Y3 X2 Y2 X1 Y1 X0 Y0)_n binary bit integer.

15. An apparatus for indexing and retrieving the map data as defined in claim 13, wherein said tracing curve is an N-shape curve or a U-shape curve, where the U-shape curve or U-shape curve is adaptable to three dimensional curve representation for a given spatial sequence whose coordinates x_n, y_n and z_n (n=0,1,2, . . . N, where N is the length of the spatial sequence) are uniquely determined by the N/U transformation of spatial sequence.

16. An apparatus for spatial indexing and retrieving the map data as defined in claim 13, further comprising means for providing cost information on virtual links that connect boundary nodes on the administrative regions on layers higher than a base layer in the layered structure of the XML map data, and means for providing cost information on physical links on the base layer of the layered structure of the XML map data.

17. An apparatus for indexing and retrieving the map data as defined in claim 16, further comprising means for searching routes between a start point and a destination when the destination is specified by a user by selecting candidate virtual links that connect the boundary nodes of different administrative regions on a particular layer of the map data by evaluating the cost information on the virtual links.

18. An apparatus for spatial indexing and retrieving the map data as defined in claim 17, wherein the cost information is computed based on a distance, a travel time, and predetermined cost space factors for each virtual link and physical link where the cost information on the virtual links on a particular layer is established on a layer of the map data that is immediately higher than the particular layer and stored in a form of cost tables.

19. An apparatus for spatial indexing and retrieving the map data as defined in claim 11, wherein said administrative regions include cities, counties, states, and countries in the order of lower layer to higher layer in the layered structure of the XML map data.

20. An apparatus for spatial indexing and retrieving the map data as defined in claim 19, wherein the layered structure of the XML map data is configured by an international layer for connecting the boundary nodes between two or more countries, a country layer for connecting the boundary nodes between two or more states within the country, a state layer for connecting the boundary nodes between two or more counties within the state, a county layer for connecting the boundary nodes between two or more cities within the county, and a city layer which is the base layer with the physical links.