System and method for use and storage of geographic data on physical media

• US 5,968,109 A
• Filed: 10/25/1996
• Issued: 10/19/1999
• Est. Priority Date: 10/25/1996
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Bouzide, Paul M., Crane, Aaron I., Fernekes, Robert P., Israni, Vijaya S., Lampert, David S., Meek, James A., Ashby, Richard A., Nyczak, Gregory M., Jasper, John C., Smith, Nicholas E.
• Primary Examiner(s): Zanelli, Michael J.
• Application Number:
  US08/740,295
• Time in Patent Office: 1,089 Days
• Field of Search: 701/208, 701/200, 340/995, 707/102, 707/104
• US Class Current: 701/208
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/0969 having a display in the form of a map
• CPC Class Codes: G09B 29/106 using electronic means
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

An improved method and system for storage of geographic data on physical storage media. The geographic data are stored in a manner that facilitates and enhances use and access of the data by various navigation application functions in navigation systems that use the data. The geographic data includes a parcelization that separates the geographic data into parcels having less than or equal to a maximum parcel size but having at least a desired fill percentage. The parcelization method also provides for a division arrangement that facilitates addressing and identification of the parcels. According to a further aspect, the geographic data includes special nodal entities that are used to collapse complex intersections, such as roundabouts, cloverleaves, and divided highways, into simpler data representations. The special nodal entities are associated with road segment data entities and used in a route calculation program in place of regular node entities. Further, the geographic data include a normalized attribute array that includes reoccurring combinations of certain selected attributes of the geographic data. Indices to the array are included in place of data corresponding to the selected attributes. When a navigation application program requests data, an entry in the normalized attribute table pointed to by an index in the data is used to return the requested data in the particular combination of attributes from the normalized attribute array. The geographic data is compiled by a method that facilitates access to the data on a physical medium. According to the compilation method, data files to be stored on the medium are organized into parcels. The data records within the data files are identified by the parcel in which they are located. An arrangement of all the data files on the medium is determined and a parcel identification related to the medium is assigned to each parcel. Cross references between data records are updated to include the assigned parcel identifications and the parcels are stored on the medium.

Claims

1. A method of storing a plurality of records of geographic data on a storage medium, wherein each record represents a physical feature having a physical location in a geographic region, the method comprising the steps of:

separating said plurality of records into first and second groupings of records wherein the records in said first of said groupings represent physical features having geographic locations encompassed within a first sub-rectangular area and the records in said second of said groupings represent physical features having geographic locations encompassed within a second sub-rectangular area,

wherein said first and said second sub-rectangular areas are formed by a division at a position of a rectangular area that encompasses the locations of the physical features represented by the plurality of records in said first and second groupings, wherein said position of said division is determined by

evaluating a plurality of trial divisions of said rectangular area; and

selecting one of said plurality of trial divisions based upon resultant sizes of said first and second groupings.

2. The method of claim 1 wherein ends of portions of road segments located in said geographic region are represented by node data records which are included among the plurality of records of geographic data, the method further comprising:

prior to the step of separating, identifying complex intersections in said geographic data; and

representing said complex intersections as a single node data record.

3. The method of claim 1 further comprising the step of:

comparing resultant sizes of said first and second groupings derived from said evaluation of said plurality of trial divisions to a first range of sizes;

and wherein said step of separating comprises separating said plurality of records into first and second groupings based upon at least one of said groupings corresponding to said first range of sizes.

4. The method of claim 1 further comprising the step of:

comparing resultant sizes of said first and second groupings derived from said evaluation of said plurality of trial divisions to a first range of sizes;

and wherein said step of separating comprises separating said plurality of records into first and second groupings based upon both said first and second groupings corresponding to said first range of sizes.

5. The method of claim 4 wherein said first range of sizes is based upon a fill percentage of between 80 and 100 percent for a parcel formed of one of said groupings of records.

6. The method of claim 1 further comprising:

ascertaining an aspect ratio of at least one trial rectangle formed by each of said trial divisions; and

wherein said selecting step is based upon evaluating both said aspect ratio and said resultant sizes of groupings formed by each of said trial divisions.

7. The method of claim 1 wherein said trial divisions are located at a position m/2ⁿ along a side of said rectangle where n is an integer between and including 1 and 5 and m is an integer between and including 1 and (2ⁿ -1).

8. The method of claim 1 further comprising;

upon determining that a size of one of said first and second groupings formed by said separating step exceeds a predetermined threshold, separating said one grouping into further first and second groupings by applying the same separating, evaluating, and selecting steps to said one grouping that had been applied to said plurality of records.

9. The method of claim 8 further comprising the step of:

forming any of said first and second groupings of records, and the further first and second groupings of records formed therefrom, into a parcel upon evaluation of a size of said grouping not exceeding a predetermined desired maximum parcel size.

10. The method of claim 1 further comprising;

if a size of one of said first and second groupings formed by said separating step exceeds a predetermined desired maximum parcel size, continuing to apply said separating, evaluating, and selecting steps to the plurality of data records in said one grouping and to all groupings formed therefrom until each of said groupings formed therefrom has a size that does not exceed the predetermined desired maximum parcel size.

11. The method of claim 1 wherein said plurality of records represent segments of roads in said geographic region.

12. The method of claim 11 wherein said plurality of records are routing data records that include information about speed of travel and turn restrictions along each of said segments of roads.

13. The method of claim 1 wherein said plurality of records are cartographic data records that represent shapes of segments of roads and that are used to display said segments of roads on a computer display.

14. The method of claim 1 further comprising the step of:

forming one of said first and second groupings of records into a parcel upon evaluation of a size of said grouping not exceeding a predetermined desired maximum parcel size, wherein said parcel size represents a minimum quantity of data that can be accessed by a navigation system in a single access operation.

15. The method of claim 14 wherein said forming step further comprises the step of:

when forming said one of first and second groupings of records into a parcel, adding an amount of padding to said grouping of records so that said grouping and said padding together are equal to the predetermined desired maximum parcel size.

16. The method of claim 1 wherein the geographic data includes data entities that represent segments of roads in said geographic region, wherein each segment of a road is associated with two nodes located at respective endpoints thereof, the method further comprising the steps of:

prior to the step of separating,

evaluating each of the nodes of represented segments of roads with a plurality of criteria, wherein the plurality of criteria include

a first criterion that any number of segments, other than exactly 2 segments, can meet at a node, and

at least one other criterion;

determining that a node is an aggregated-significant node based upon said step of evaluating;

forming an aggregated segment data entity that represents in aggregation a plurality of road segments that connect between aggregated-significant nodes; and

storing the aggregated segment data entity as one of the plurality of records.

17. The method of claim 1 further comprising:

prior to the step of separating, identifying common attributes in a portion of the plurality of records,

forming an array containing said common attributes; and

in said portion of the plurality of records, substituting said common attributes with a reference to said array.

18. The method of claim 17 further comprising:

storing said array with said geographic data on said storage medium.

19. A database formed according to the method of claim 1, wherein said database is stored on a computer-readable medium.

20. A method of forming a geographic database that includes data entities that represent segments of roads in a geographic area, wherein each segment of a road is associated with two nodes located at respective endpoints thereof, the method comprising the steps of:

evaluating each of the nodes of represented segments of roads with a plurality of criteria, wherein the plurality of criteria include

a first criterion that any number of segments, other than exactly 2 segments, can meet at a node, and

at least one other criterion;

determining that a node is an aggregated-significant node based upon said step of evaluating;

forming an aggregated segment data entity that represents in aggregation a plurality of road segments that connect between aggregated-significant nodes;

storing the aggregated segment data entity in the geographic database,

for each aggregated segment data entity formed by the forming step, forming abbreviated segment data entities that represent the plurality of segments of roads that are represented by the aggregated segment data entity; and

storing the abbreviated segment data entities in the geographic database.

21. The method of claim 20 wherein said at least one other criterion comprises:

a second criterion that a restricted driving maneuver extends across the node.

22. The method of claim 20 wherein the geographic database is formed of a plurality of layers wherein each layer includes a separate collection of data entities and inclusion of a data entity in a given layer is based upon a functional rank of at least one road segment represented thereby, and wherein the abbreviated segment data entities formed to represent the plurality of segments of roads that are represented by an aggregated segment data entity are stored in a same layer as the aggregated segment data entity.

23. A database formed according to the method of claim 20, wherein said database is stored on a computer-readable medium.

24. A method of forming a geographic database that includes data entities that represent segments of roads in a geographic area, wherein each segment of a road is associated with two nodes located at respective endpoints thereof, the method comprising the steps of:

evaluating each of the nodes of represented segments of roads with a plurality of criteria, wherein the plurality of criteria include

a first criterion that any number of segments, other than exactly 2 segments, can meet at a node, and

at least one other criterion;

determining that a node is an aggregated-significant node based upon said step of evaluating;

forming an aggregated segment data entity that represents in aggregation a plurality of road segments that connect between aggregated-significant nodes;

storing the aggregated segment data entity in the geographic database;

for each node which is not an aggregated-significant node, forming an abbreviated node data entity and including a reference thereto in the aggregated segment data entity that represents the segments of roads connected thereto; and

storing the abbreviated node data entity in the geographic database.

25. The method of claim 24 wherein the geographic database is formed of a plurality of layers wherein each layer includes a separate collection of data entities and inclusion of a data entity in a given layer is based upon a functional rank of the at least one road segment represented thereby, and wherein each abbreviated node data entity is located in a same layer as the aggregated segment data entity that refers thereto.

26. A database formed according to the method of claim 24, wherein said database is stored on a computer-readable medium.

27. A method of manufacturing a geographic database for a geographic region for use by a navigation application program, wherein said geographic database is stored on a computer-readable medium and wherein said geographic database includes a plurality of records wherein each record corresponds to a physical feature having a physical location in the geographic region, the method comprising the steps of:

arranging said records of geographic data into a plurality of parcels according to a method that stores in each parcel records of geographic data that represent features having physical locations in proximity to each other and wherein the records stored in any one parcel represent features having locations encompassed within a corresponding rectangular area associated therewith and located in said geographic region;

wherein a size and location of each rectangular area associated with a parcel are determined by a series of divisions of a rectangular area encompassing all of said features represented by said plurality of records, wherein each division of said series of divisions subsequent to an initial division is made on a rectangular area formed from a preceding division; and

wherein each division of a rectangular area into further rectangular areas is made at a location of said rectangular area based upon a comparison of quantities of data that represent features encompassed by each of said rectangular areas formed by said division to a plurality of ranges of acceptable sizes derived from a desired fill percentage of parcels with data.

28. The method of claim 27 wherein said plurality of ranges of acceptable sizes is based upon a fill percentage of between 80 and 100 percent for a parcel formed therefrom.

29. The method of claim 27 wherein said division of a rectangular area into further rectangular areas is also based upon an evaluation of aspect ratios of the rectangular areas formed by said division.

30. The method of claim 27 wherein a division of a rectangular area into further rectangular areas is located at a position m/2ⁿ along a side of said rectangular area where n is an integer between and including 1 and 5 and m is an integer between and including 1 and (2ⁿ -1).

31. The method of claim 27 wherein said records represent segments of roads in said geographic region.

32. The method of claim 31 wherein said records comprise routing data records that include information about speed of travel and turn restrictions along each of said segments of roads.

33. The method of claim 31 wherein said records comprise cartographic data records that represent shapes of said segments of roads and that are used to display said segments of roads on a computer display.

34. The method of claim 27 wherein said desired fill percentage is based upon a parcel size not exceeding a minimum quantity of data that can be accessed by a navigation system in a single access operation.

35. The method of claim 27 further comprising the step of:

when forming a parcel of records of geographic data, if a size of said records is less than a maximum size for a parcel, adding an amount of padding equal to the difference between the size of the records of geographic data and the maximum parcel size.

36. A database formed according to the method of claim 27, wherein said database is stored on a computer-readable medium.

37. A geographic database for use with a navigation application program that uses said geographic database, wherein the geographic database comprises:

segment data entities that represent segments of roads;

aggregated segment data entities that represent aggregations of segments of roads; and

abbreviated segment data entities that are abbreviated representations of the segments of roads represented by the aggregated segment data entities,

and wherein each of the aggregated segment data entities refers to those abbreviated segment data entities that represent the same segments of roads that are represented in aggregation thereby,

and further wherein the geographic database is comprised of a plurality of separate layers of segment data entities, aggregated segment data entities and abbreviated segment data entities, wherein each of said plurality of separate layers includes a separate collection of said data entities based upon functional ranks of the represented segments of roads,

and wherein the abbreviated segment data entities that are referred to by an aggregated segment data entity and the aggregated segment data entity that refers to those abbreviated segment data entities are located in a same layer.

38. A database according to claim 37, wherein said database is stored on a computer-readable medium.

39. A geographic database for use with a navigation application program that uses said geographic database, wherein the geographic database comprises:

segment data entities that represent segments of roads;

aggregated segment data entities that represent aggregations of segments of roads; and

abbreviated segment data entities that are abbreviated representations of the segments of roads represented by the aggregated segment data entities,

abbreviated node data entities that are abbreviated representations of nodes which are endpoints of segments of roads represented in aggregations by aggregated segment data entities and wherein the nodes which are represented by abbreviated node data entities are internal of endpoints of the aggregations of road segments represented by the aggregated segment data entities,

wherein each of the aggregated segment data entities refers to those abbreviated segment data entities that represent the same segments of roads that are represented in aggregation thereby,

and wherein each of the aggregated segment data entities refers to those abbreviated node data entities that represent the nodes at the endpoints of the segments of roads represented in aggregation by the aggregated segment data entity and that are located internal of the endpoints of the aggregated segment data entity.

40. The invention of claim 39 wherein each of said aggregated segment data entities includes attributes that include at least one of:

a length of the segments of roads represented in aggregation;

an average speed along the segments of roads represented in aggregation; and

a transit time along the segments of roads represented in aggregation.

41. A database according to claim 39, wherein said database is stored on a computer-readable medium.

42. A method of formatting geographic data for storage on a computer-readable storage medium, said geographic data relating to a geographic region and said geographic data being nonuniform in density over the geographic region, the method comprising the steps of:

dividing said geographic data into a first plurality of portions, wherein each one of said first plurality of portions includes geographic data that correspond to geographic positions encompassed within a rectangular area of the geographic region, and wherein a rectangular area encompassing geographic positions corresponding to any one of said plurality of portions is separate from rectangular areas encompassing the remaining of said plurality of portions;

with respect to each portion of said first plurality of portions that exceeds a predetermined multiple of a predetermined maximum parcel amount,

forming smaller portions of said portion by repeating a regular separation process upon said portion, and the portions formed therefrom, until all resultant portions do not exceed the predetermined multiple of the maximum parcel amount;

wherein the regular separation process applied to a portion forms a pair of resultant portions, wherein each of said pair of resultant portions includes geographic data that correspond to geographic positions encompassed within a separate equal-sized rectangular area, wherein said separate equal-sized rectangular areas together correspond in size to a rectangular area encompassing the portion that had been divided to form the pair of resultant portions;

with respect to each portion of said first plurality of portions and each of the resultant portion that exceeds the maximum parcel amount but is not greater than a predetermined multiple of the maximum parcel amount,

forming smaller portions of said portion by repeating a special separation process upon said portion, and the portions formed therefrom, until all resultant portions do not exceed the maximum parcel amount;

wherein the special separation process applied to a portion forms a pair of resultant portions, wherein each of said pair of resultant portions includes geographic data that correspond to geographic positions encompassed within a separate rectangular area, wherein said separate rectangular areas together correspond in size to a rectangular area encompassing the portion that had been divided to form the pair of resultant portions, and wherein one of said portions includes an amount within ranges defined between an integer multiple of a desired fill percentage times the maximum parcel amount and the integer multiple of the maximum parcel amount; and

with respect to each portion of said first plurality of portions and said portions formed by said regular and special separation processes that is not greater than a maximum parcel amount, forming a parcel of said portion.

43. A method of storing geographic data in a computer-readable storage medium, said geographic data relating to a geographic region and said geographic data being nonuniform in density over the geographic region, the method comprising the steps of:

formatting the geographic data according to the method of claim 42;

storing said geographic data in their corresponding portions; and

storing said portions onto the computer-readable storage medium.

44. A method of storing geographic data in a computer-readable storage medium, said geographic data relating to a geographic region and said geographic data being nonuniform in density over the geographic region, the method comprising the steps of:

separating said geographic data into a first plurality of portions, wherein each of said first plurality of portions includes geographic data that corresponds to geographic positions encompassed within a separate rectangular tile, wherein a grid composed of a plurality of said separate rectangular tiles encompasses the geographic region;

with respect to each portion of said first plurality of portions that is not greater than a maximum parcel amount, forming a parcel of said portion,

with respect to each portion of said first plurality of portions that exceeds a predetermined multiple of said maximum parcel amount, separating said portion to form a pair of resultant portions, wherein each of said pair of resultant portions includes geographic data that correspond to geographic positions encompassed within a separate equal sized rectangular tile, wherein said separate equal sized rectangular tiles together correspond in area to the rectangular tile encompassing the geographic data that had been divided to form the pair of resultant portions;

with respect to each resultant portion that exceeds said predetermined multiple of said maximum parcel amount, continuing to divide said resultant portion and portions resultant therefrom to form a pair of further resultant portions, wherein each of said pair of further resultant portions includes geographic data that correspond to geographic positions encompassed within a separate equal sized rectangular tile;

with respect to each portion of said first plurality of portions that exceeds said predetermined maximum parcel amount but does not exceed said predetermined multiple of said maximum parcel amount and each resultant portion that exceeds said predetermined maximum parcel amount but does not exceed said predetermined multiple of said maximum parcel amount, separating said portion to form a pair of resultant portions, wherein each of said pair of resultant portions includes geographic data that correspond to geographic positions encompassed within a separate rectangle, wherein said separate rectangles together correspond in area to the rectangular tile encompassing the geographic data that had been divided to form the pair of resultant portions, and

wherein both said resultant rectangles have a first dimension equal to a first dimension of the tile from which said rectangles were formed;

wherein one of said rectangles has a second dimension equal to M times 2^-N times a second dimension of the tile from which said rectangles were formed, and

wherein the other of said rectangles has a second dimension of (2^N -M) times 2^-N times the second dimension of the tile from which said rectangles were formed,

wherein N is a positive integer greater than 1 and M is a positive integer less than 2^N, and

wherein M is chosen so that said first and said second portions can be divided into as few further rectangles as possible each of said further rectangles encompassing a quantity of data exceeding a minimum fill percentage of said maximum parcel amount.

45. A method of formating a geographic data base for storage on a computer-readable medium wherein said geographic data base includes geographic data corresponding to a geographic region, the method comprising the steps of:

separating said geographic data into two portions so that the two portions each include geographic data encompassed by equal sized rectangles of said geographic region;

continuing to perform said separating step upon the portions of geographic data until a portion of said geographic data formed by said separating is less than a predetermined multiple of a maximum parcel size, said portion of geographic data that is less than the predetermined multiple of the maximum parcel size corresponding to geographic data encompassed by a first rectangle of said geographic region having a first side of a first dimension and a second side of a second dimension;

separating said portion of geographic data that is less than the predetermined multiple of the maximum parcel size into two smaller portions having first and second amounts of geographic data,

wherein said first amount of geographic data exceeds an integer multiple of a minimum parcel fill percentage times the maximum parcel size but does not exceed the integer multiple times the maximum parcel size, and

wherein said first amount of geographic data is encompassed by a second rectangle of said geographic region said second rectangle having a first side corresponding in length to the first side of said first rectangle and said second rectangle having a second side having a length that is one of 1/4, 1/2, and 3/4 of said second side of said first rectangle.

46. The method of claim 45 wherein geographic data for route calculation is stored separately on said medium from geographic data for map display, and wherein said geographic data for map display is separated into parcels along the same geographic boundaries as the geographic data for route calculation.

47. An improved geographic database for a geographic region for use with a navigation system, said improved geographic database stored on a computer-readable physical storage medium, the improved database comprising:

a plurality of data entities stored on said physical storage medium, said plurality of data entities representing physical features in the geographic region;

a normalized attribute array stored on said physical storage medium, said normalized attribute array having a plurality of entries each of said entries having an index reference and a specific combination of a plurality of attributes that describe a physical feature;

wherein each of said data entities includes an index reference; and

whereby attributes describing a feature represented by a data entity having a first index reference are determined by reference to an entry in the normalized attribute array corresponding to said first index reference.

48. The improved geographic database of claim 47 wherein a first plurality of data entities have the first index reference and wherein attributes describing each of said first plurality of data entities are determined by reference to the entry in the normalized attribute array corresponding to said first index reference.

49. The improved geographic database of claim 48 wherein a second plurality of data entities have a second index reference and wherein attributes describing each of said second plurality of data entities are determined by reference to the entry in the normalized attribute array corresponding to said second index reference.

50. The invention of claim 47 wherein said normalized attribute array contains combinations of pluralities of attributes that occur most commonly in the plurality of data entities.

51. The invention of claim 47 wherein said normalized attribute array contains 256 entries.

52. The invention of claim 47 wherein the physical features represented by said plurality of data entities comprise road segments.

53. The invention of claim 47 wherein the plurality of data entities comprise cartographic data records.

54. The invention of claim 47 wherein the plurality of data entities comprise route calculation data records.

55. The invention of claim 47 wherein attributes describing a feature represented by a data entity having a second index reference are determined by reference to an entry in the normalized attribute array corresponding to said second index reference.

56. The improved geographic database of claim 47 wherein said normalized attribute array comprises a global array and a local array.

57. The improved geographic database of claim 47 wherein said normalized attribute array comprises a global array and a plurality of local arrays, and wherein said geographic database is stored in a plurality of parcels each of which includes a plurality of data entities and a corresponding one of said plurality of said local arrays.

58. An improved geographic database for a geographic region for use with a navigation system, said improved geographic database stored on a computer-readable physical storage medium, the improved database comprising:

a plurality of data entities stored on said physical storage medium, said plurality of data entities representing physical features in the geographic region;

a global normalized attribute array stored on said physical storage medium, said global normalized attribute array having a plurality of entries each of said entries having an index reference and a specific combination of a plurality of attributes that describe a physical feature;

a plurality of local normalized attribute arrays stored on said physical storage medium, said local normalized attribute arrays having a plurality of entries each of said entries having an index reference and a specific combination of a plurality of attributes that describe a physical feature; and

wherein each of said data entities includes an index reference;

whereby attributes describing a feature represented by a data entity having a first index reference are determined by reference to an entry corresponding to said first index reference in one of the global normalized attribute array and the plurality of local normalized attribute arrays.

59. The improved geographic database of claim 58 wherein said geographic database is parcelized on said storage medium and further wherein each of said local normalized attribute arrays is associated with a parcel, and wherein each of said local normalized attribute arrays includes specific combinations of a plurality of attributes that describe a physical feature represented by a data entity stored within the parcel associated therewith.