Spatial Index for Locating Geographic Data Parcels Stored on Physical Storage Media

• US 20100082564A1
• Filed: 10/01/2008
• Published: 04/01/2010
• Est. Priority Date: 10/01/2008
• Status: Abandoned Application

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: Fernekes, Robert P.
• Application Number:
  US12/243,186
• Publication Number:
  US 20100082564A1
• Time in Patent Office: Days
• US Class Current: 707/705
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A spatial index for locating geographic data parcels stored on physical storage media is disclosed. A geographic database for advanced driver assistance systems is subdivided based on a grid of fixed size tiles that span the entire globe. Each tile is assigned a tile identification. The geographic database is organized as a collection of parcels, each of which contains the data for one or more tiles. To locate a parcel on the physical storage media, a spatial index uses the tile identification. Because the tiles are not uniformly filled with data, the spatial index is organized as a sparse array.

Claims

1. A system for locating geographic data stored in parcels on physical storage media, wherein the geographic data is located in a geographic database that is organized by parcels of one or more tiles bounded by lines of constant latitude or longitude in a world tile grid, comprising:

an application that receives a request for geographic data, wherein the request includes information that the application uses to identify a tile that contains the requested geographic data; and

a spatial index organized as a sparse array, wherein the application provides the tile identification to the spatial index and the spatial index uses the tile identification to identify a row and a column associated with the tile, and wherein the spatial index uses the row and the column to identify a parcel location on the physical storage media that contains the requested geographic data.

2. The system of claim 1, wherein the information that the application uses to identify the tile includes data associated with a current position of a vehicle.

3. The system of claim 2, wherein the data associated with the current position of the vehicle includes geographic coordinates of the vehicle'"'"'s position.

4. The system of claim 2, wherein the data associated with the current position of the vehicle includes at least one of a segment identification and a node identification.

5. The system of claim 1, wherein the information that the application uses to identify the tile includes at least one of a segment identification and a node identification.

6. The system of claim 1, wherein the spatial index includes a single row parcel and at least one column parcel.

7. The system of claim 6, wherein the row parcel and the at least one column parcel includes a header, a first array, and a second array, wherein the first array indicates presence of entries in the second array.

8. A method for locating geographic data stored in parcels on physical storage media, wherein the geographic data is located in a geographic database that is organized by parcels of one or more tiles bounded by lines of constant latitude or longitude in a world tile grid, comprising:

receiving a request for geographic data;

identifying a tile that contains the requested geographic data, wherein the tile identification is associated with a row and a column in the world tile grid; and

retrieving a media address for a parcel using a spatial index organized as a sparse two dimensional array indexed by the tile'"'"'s row and column in the world tile grid.

9. The method of claim 8, wherein the request includes data associated with a current position of a vehicle.

10. The method of claim 9, wherein the data associated with the current position of the vehicle includes geographic coordinates of the vehicle'"'"'s position.

11. The method of claim 10, wherein identifying the tile includes translating the geographic coordinates of the vehicle'"'"'s position to obtain the tile identification.

12. The method of claim 9, wherein the data associated with the current position of the vehicle includes at least one of a segment identification and a node identification.

13. The method of claim 12, wherein identifying the tile includes extracting the tile identification from a geographic database identification using at least one of the segment identification and the node identification.

14. The method of claim 8, wherein the request includes at least one of a segment identification and a node identification.

15. The method of claim 8, further comprising reading the parcel from the physical storage media.

16. A spatial index used to for locating geographic data stored in parcels on physical storage media, wherein the geographic data is located in a geographic database that is organized by spatial parcels of one or more tiles bounded by lines of constant latitude or longitude in a world tile grid, comprising:

a row index parcel including a first array of bit flags and a first array of media addresses, wherein the first array of bit flags indicates presence of entries in the first array of media addresses; and

a column index parcel including a second array of bit flags and a second array of media addresses, wherein the second array of bit flags indicates presence of entries in the second array of media addresses, wherein an entry in the first array of media addresses identifies a media address of the column index parcel, and wherein the second array of media addresses identifies a media address of a spatial parcel.

17. The spatial index of claim 16, wherein the row index parcel and the column index parcel further include a parcel header.

18. The spatial index of claim 17, wherein the parcel header includes information regarding type of parcel, the array of bit flags, and the array of media addresses.

19. The spatial index of claim 16, wherein the geographic database includes a database header that identifies a media address of the row index parcel.

20. The spatial index of claim 16, wherein one of the row index parcel and the column index parcel is stored in more than one parcels.

21. The spatial index of claim 16, wherein one of the row index parcel and the column index parcel includes more than one indexes.