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

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.

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.

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.

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.

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.

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.

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.sup.-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.sup.N -M) times 2.sup.-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.sup.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.

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.

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.

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.