Patent ID: 8532925
Filing Date: 2013-09-10
Classification: G06F

Abstract:
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, each being in an XML format and having a square shape, 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, the tracing curve being created by combining X-address data and Y-address data of the map cells into one dimensional data; assigning index numbers consecutively to all of the map cells in all of the layers of the XML map data with the sequence determined by the selected tracing curve, thereby creating a map database in the XML format with the spatial indexes for all of the map cells; providing cost information on virtual links on layers higher than a base layer in the layered structure of the XML map data, where the virtual links are non-physical links formed by connecting boundary nodes located on boundaries of the administrative regions; and providing cost information on physical links on the base layer of the layered structure of the XML map data, where the physical links are links formed by connecting actual roads on the base layer; wherein said tracing curve is adaptable to three dimensional curve representation for a given spatial sequence, and wherein said plurality of map cells divide a unit of administrative regions in all layers of the XML map data including a lowest layer thereof for indexing the map cells smaller than the administrative region in the lowest layer.