PARCELIZED GEOGRAPHIC DATA MEDIUM WITH INTERNAL SPATIAL INDICES AND METHOD AND SYSTEM FOR USE AND FORMATION THEREOF

• US 20040205517A1
• Filed: 01/30/1998
• Published: 10/14/2004
• Est. Priority Date: 01/30/1998
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: MEEK, JAMES, JAUGILAS, JOHN, LAMPERT, DAVID S., FERNEKES, ROBERT, ASHBY, RICHARD A.
• Granted Patent: US 7,266,560 B2
• Time in Patent Office: Days
• US Class Current: 715/502
• CPC Class Codes: G01C 21/3863 Structures of map data
• CPC Class Codes: G01C 21/3874 Structures specially adapted for data searching and retrieval
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A navigable map database, stored on a computer-readable medium and used with a navigation application program, includes data which are spatially parcelized into a plurality of parcels. Associated with each of the plurality of parcels is a first index which associates the area represented by the data in the parcel with a plurality of sub-areas formed of the area. Also associated with each of the parcels is a second index associating each of the data in the parcel with at least one of the sub-areas. Further disclosed is a method for producing a navigable map database which is parcelized into a plurality of parcels, wherein each of the plurality of parcels includes a first index which associates the area represented by the data in the parcel with a plurality of sub-areas formed of the area and a second index associating each of the data in the parcel with at least one of the sub-areas. Also further disclosed are a program and method for finding data in one or more parcels that match a spatial search criterion using a navigable map database that is parcelized into a plurality of parcels, wherein each of the plurality of parcels includes a first index which associates the area represented by the data in the parcel with a plurality of sub-areas formed of the area and a second index associating each of the data in the parcel with at least one of the sub-areas. The program and method use the first and second indices to identify which of the data in at least one of the plurality of parcels satisfy the spatial search criterion.

Claims

1. A method for producing a database that represents a road network in a geographic region for comprising the steps of:

spatially parcelizing a plurality of data entities into a plurality of parcels wherein each parcel said plurality of parcels contains a separate subset of said plurality of data entities;

with respect to each of said parcels, determining a plurality of sub-areas each of which encompasses some of the geographic features represented by the data entities contained in said parcel; and

storing a first index identifying with respect to each of the data entities contained in said parcel each of said sub-areas intersected by the geographic feature represented thereby.

2. The method of claim 1 wherein said first index is a bitmap.

3. The method of claim 1 wherein each of the plurality of sub-areas is a sub-rectangle.

4. The method of claim 1 wherein said first index is stored internally of each of said parcels.

5. The method of claim 1 further comprising:

with respect to each of said parcels, storing a second index identifying boundaries of each of said plurality of sub-areas.

6. The method of claim 5 wherein said second index is a kd-tree index.

7. The method of claim 5 wherein said second index is stored internally of said parcel.

8. The method of claim 1 wherein with respect to each parcel, the data entities that represent geographic features encompassed by each of said plurality of sub-areas are approximately equal in number to the data entities that represent geographic features encompassed by each of the other of the plurality of sub-areas.

9. The method of claim 1 wherein the data entities represent segments of roads in the geographic region.

10. The method of claim 1 wherein the step of determining a plurality of sub-areas each of which encompasses some of the geographic features represented by the data entities contained in said parcel is further characterized as comprising:

determining eight sub-areas.

11. A method of using a navigable map database with a navigation system comprising the steps of:

identifying a search area in a geographic region;

identifying at least one parcel of data in the navigable map database, wherein the at least one parcel of data contains data entities that represent features encompassed within a first rectangular area within the geographic region, wherein the first rectangular area intersects said search area;

using a first index associated with said at least one parcel of data to identify each of a plurality of sub-rectangles of said first rectangular area that intersect said search area; and

using a second index associated with said at least one parcel of data to identify which of said data entities contained in said parcel intersect each of the plurality of sub-rectangles identified by using said first index.

12. A method of using a navigable map database with a navigation system, wherein the navigable map database is comprised of a plurality of parcels, wherein each of said parcel contains data entities that represent features encompassed within a separate rectangular area within a geographic region, wherein the rectangular area associated with each parcel is distinct from the rectangular area associated with each other parcel of the plurality of parcels, comprising the steps of:

identifying a search area in a geographic region;

identifying each of said parcels whose data entities are encompassed by a rectangular area that intersects said search area;

using a first index associated with each of said parcels to identify each sub-rectangle of a plural of sub-rectangles that intersects said search area, wherein said plurality of sub-rectangles are of the rectangular area that encompasses the features represented by the data entities of the parcel; and

using a second index associated with each of said parcels to identify which of said data entities contained in each of said parcels intersects each sub-rectangle of the plurality of sub-rectangles identified by using the first index associated with the parcel.

13. The method of claim 12 wherein said data entities represent segments of roads.

14. The method of claim 12 wherein the first index is a kd-tree index.

15. The method of claim 12 wherein the second index is a bitmap.

16. In a map database for use in a navigation system, wherein the map database is comprised of a plurality of data records each of which represents a physical geographic feature in a geographic region,

wherein the data records are spatially parcelized into a plurality of parcels,

wherein each parcel plurality of said parcels comprises a separate portion of said plurality of data records, wherein the portion of said plurality of data records in each parcel represents geographic features encompassed together in an area of said geographic region and wherein the area that encompasses the geographic features represented by one parcel is separate from the areas that encompass the geographic features represented by the rest of the parcels of a given level and of a given type,

wherein the improvement comprises:

a plurality of index tables of a first type, each of which is associated with a separate one of said plurality of parcels,

wherein each of said index tables of the first type comprises;

a separate reference to each data record in the parcel to which said index table is associated; and

a reference to at least one of a plurality of groupings of the plurality of data records in the parcel,

wherein the plurality of groupings organize the plurality of data records in the parcel spatially.

17. The invention of claim 16 further comprising:

a plurality of index tables of a second type, each of which is associated with a separate one of said plurality of parcels,

wherein each of said index tables of the second type comprises;

a spatial reference to each of a plurality of separate sub-areas formed of the area that encompasses the geographic features represented by the data records in a respective one of the plurality of parcels.

18. A geographic database stored on a computer readable storage medium, said geographic database for use with a navigation application program and representing a geographic region, said geographic database comprising:

a plurality of data entities each of which represents a physical feature in the geographic region, wherein said plurality of data entities are separated into a plurality of parcels each of which contains a subset of said plurality of data entities wherein the subset of data entities in each parcel represent geographic features in said geographic region encompassed within a separate one of a plurality of rectangles which together encompass all the plurality of data entities in all the parcels in the entire geographic region;

wherein each of said plurality of parcels is associated with an index, wherein the index associated with each parcel relates each of the data entities in the subset of said plurality of data entities associated with said parcel with at least one grouping of a plurality of groupings of said subset of data entities associated with said parcel.

19. The invention of claim 18 wherein each of said groupings in each of said subsets is spatially organized.

20. The invention of claim 18 wherein each of said groupings of the data entities within each parcel include approximately a similar number of data entities as each of the other groupings within the parcel.

21. The invention of claim 18 wherein each of said groupings of the data entities in each of said parcels includes data records encompassed within a separate sub-rectangular area.

22. A computer usable medium having computer readable program data structure means embodied therein for use in a map database, wherein the map database includes a plurality of data records representing segments of roads in a geographic region, said computer readable program data structure means adapted to provide for identifying which of said plurality of data records included in each of a plurality of parcels of spatially parcelized data meets a spatial search criterion, said computer readable program data structure comprising:

a plurality of first indices, each of which is associated with a respective one of each of said plurality of parcels, wherein each of said plurality of first indices determines a plurality of sub-areas formed of an area that encompasses the geographic features represent by the data records in the respective parcel; and

a plurality of second indices, each of which is associated with a respective one of each of said plurality of parcels, wherein each of said plurality of second indices associates each of the plurality of data records in its respective parcel to at least one of the plurality of sub-areas determined by the one of the plurality of first indices associated with the respective parcel.