EP0838663A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
System and method for storing geographic data on a physical storage medium
Assignee: Navteq Corp
•
Filing: 1997-10-24
•
Granted: —
•
Expires: 2017-10-24
Abstract
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.
Inventors
- 👤 Vijaya S. Israni
- 👤 Richard A. Ashby
- 👤 Paul M. Bouzide
- 👤 John C. Jasper
- 👤 Robert P. Fernekes
- 👤 Gregory M. Nyczak
- 👤 Nicholas E. Smith
- 👤 David S. Lampert
- 👤 James A. Meek
- 👤 Aaron I. Crane
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-04 21:40
CPC Classifications
G; G08; G08G; G08G1/00; G08G1/09; G08G1/0962; G08G1/0968; G08G1/096805; G08G1/096827; G01; G01C; G01C21/00; G01C21/38; G01C21/3863; G01C21/3867; G06; G06F; G06F16/00; G06F16/20; G06F16/29; G08G1/0969; G09; G09B; G09B29/00; G09B29/10; G09B29/106; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 46
Claim 1
Independent Claim
168 words
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.
Claim 2
Dependent Claim
67 words
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.
Claim 3
Dependent Claim
67 words
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.
Claim 4
Dependent Claim
34 words
The method of Claim 3 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.
Claim 5
Dependent Claim
50 words
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.
Claim 6
Dependent Claim
46 words
The method of Claim 1 wherein said trial divisions are located at a
position m/2 n 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 n -1).
Claim 7
Dependent Claim
39 words
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.
Claim 8
Dependent Claim
58 words
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 step to said one grouping that had been applied to said plurality of
records.
Claim 9
Dependent Claim
61 words
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, continuing to
apply said separating said one grouping and to all groupings formed therefrom until
each of said groupings has a size that does not exceed a predetermined desired
maximum parcel size.
Claim 10
Dependent Claim
15 words
The method of Claim 1 wherein said records represent segments of
roads in geographic region.
Claim 11
Dependent Claim
27 words
The method of Claim 1 wherein said records are routing data records
that include information about speed of travel and turn restrictions along each of
said segments.
Claim 12
Dependent Claim
27 words
The method of Claim 1 wherein said records are cartographic data
records that are used to display shapes of said segments of roads on a computer
display.
Claim 13
Dependent Claim
62 words
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.
Claim 14
Dependent Claim
55 words
The method of Claim 13 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.
Claim 15
Independent Claim
251 words
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
from the preceding division; and wherein each division of a rectangle area into further rectangular areas is
made at a location of said rectangular area based upon an assessment of quantities
of data that represent features encompassed by said rectangular area and each of
said further rectangular areas, based upon a comparison of said quantities of data to
a plurality of ranges of acceptable sizes derived from a desired fill percentage of
parcels with data.
Claim 16
Independent Claim
432 words
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;
Claim 17
Independent Claim
513 words
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 said one of said rectangle 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.
Claim 18
Dependent Claim
37 words
A geographic database stored on a computer readable medium where
said database is formatted by the process of Claim 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
12, 13, 14, 15, 16, or 17.
Claim 19
Dependent Claim
100 words
An improved geographic database for use with a route searching
program in a navigation system to find routes to destinations in a geographic
region, wherein said geographic database is stored on a storage medium, and
further wherein said geographic database includes segment data entities
corresponding to portions of roads in the geographic area and nodal data entities
corresponding to points in the geographic area including intersections of roads,
wherein said improvement comprises: supernodal data entities included in said geographic database, wherein each
supernodal data entities represents a substitute for a plurality of nodal data entities
for said route searching program.
Claim 20
Dependent Claim
50 words
An improved method for storing geographic data in a computer-readable
medium for use by a route searching program wherein ends of portions of
road segments are represented by nodes, the method comprising: identifying complex intersections in said geographic data; and
representing a plurality of separate nodes as a single node
Claim 21
Dependent Claim
166 words
An improved geographic database for a geographic region for use
with a route calculation program in a navigation system, said improved geographic
database stored on a computer-readable physical storage medium, the improved
database stored on the computer readable physical storage medium comprising: a plurality of regular node data entities representing points in the geographic
region; a plurality of supernode data entities, wherein each supernode data entity
represents a plurality of regular node data entities; a plurality of segment data entities, wherein each of said plurality of
segment data entities represents a portion of a road in the geographic region; wherein each of said segment data entities is associated with at least one
node data entity that corresponds to an end of the portion of the road that said
segment entity represents; and wherein said segment data entities that have ends corresponding to regular
node data entities represented by supernode data entities are associated with
supernode data entities for purposes of use by said route calculation program.
Claim 22
Dependent Claim
41 words
The improved geographic database of Claim 21 wherein each of said
plurality of segment data entities is associated with two node data entities each
corresponding to an end of the portion of the road portion represented by said
segment data entity.
Claim 23
Dependent Claim
30 words
The improved geographic database of Claim 21 wherein each of said
plurality of supernode data entities includes attributes identifying the regular node
data entities represented by the supernode data entity.
Claim 24
Dependent Claim
53 words
The improved geographic database of Claim 21 wherein at least
some of said plurality of supernode data entities further represent segment data
entities and wherein with respect to each of those supernode data entities that also
represent segment data entities, including attributes identifying the segment data
entities represented by the supernode data entity.
Claim 25
Dependent Claim
20 words
The improved geographic database of Claim 21 wherein at least
some of said plurality of supernode data entities represent roundabouts.
Claim 26
Dependent Claim
20 words
The improved geographic database of Claim 21 wherein at least
some of said plurality of supernode data entities represent cloverleaves
Claim 27
Dependent Claim
23 words
The improved geographic database of Claim 21 wherein at least
some of said plurality of supernode data entities represent intersections of divided
highways.
Claim 28
Dependent Claim
21 words
The improved geographic database of Claim 21 wherein each of said
plurality of supernode data entities has an cost associated therewith.
Claim 29
Dependent Claim
39 words
The improved geographic database of Claim 21 wherein said
database comprises a plurality of layers, and wherein a lower layer represents more
detail than a higher layer, and wherein said plurality of supernodes are located in
said lower layer.
Claim 30
Independent Claim
76 words
A method for organizing a geographic database for storage on a
computer-readable storage medium for use in a navigation system, wherein
intersections of portions of roads are represented by node data entities, comprising
the steps of: identifying related node data entities; designating a supernode data entity that represents said related node data
entities; and providing said supernode data entity for use in a route calculation program
in place of the related node data entities represented thereby.
Claim 31
Dependent Claim
63 words
The method of Claim 30 wherein said providing step is further
characterized by: in segment data entities that represent portions of roads that have end points
at intersections corresponding to node data entities represented by a supernode data
entity, substituting a reference to the supernode data entity in place of a reference to
the node data entity represented by the supernode data entity.
Claim 32
Dependent Claim
100 words
An improved geographic database for use with a route searching
program in a navigation system to find routes to destinations in a geographic
region, wherein said geographic database is stored on a storage medium, and
further wherein said geographic database includes segment data entities
corresponding to portions of roads in the geographic area and nodal data entities
corresponding to points in the geographic area including intersections of roads,
wherein said improvement comprises: supernodal data entities included in said geographic database, wherein each
supernodal data entities represents a substitute for a plurality of nodal data entities
for said route searching program.
Claim 33
Dependent Claim
137 words
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.
Claim 34
Dependent Claim
49 words
The improved geographic database of Claim 33 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.
Claim 35
Dependent Claim
194 words
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 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 or the plurality
of local normalized attribute arrays.
Claim 36
Dependent Claim
65 words
The improved geographic database of Claim 35 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.
Claim 37
Independent Claim
74 words
A method for organizing data for storage on a physical storage
medium comprising: forming a plurality of data files wherein each of said data files has data
therein; parcelizing the data in each of said data files into a plurality of parcels, concatenating the plurality of data files while retaining said parcelization of
said data; assigning a parcel identification to each of said plurality of parcels; and storing said concatenation on a storage medium.
Claim 38
Dependent Claim
27 words
The method of Claim 37 wherein said step of forming a plurality of
data files further comprises the step of: forming a data file for route calculation.
Claim 39
Dependent Claim
12 words
The method of Claim 37 wherein said storage medium is a
CD-ROM.
Claim 40
Dependent Claim
13 words
The method of Claim 37 wherein said storage medium is a PCMCIA
card.
Claim 41
Dependent Claim
13 words
The method of Claim 37 wherein said concatenation is a single data
file.
Claim 42
Dependent Claim
18 words
The method of Claim 37 wherein said parcel identification includes
an offset from a start of the concatenation.
Claim 43
Dependent Claim
29 words
The method of Claim 37 wherein said parcel identification includes
an offset from a start of the concatenation and an indication of a size of the parcel
identified thereby.
Claim 44
Dependent Claim
48 words
The method of Claim 37 wherein said data includes cross-references
between individual records of said data, and wherein the method further comprises
the step of: after the step of assigning a parcel identification to each of said plurality of
parcels, updating said cross-references to include said parcel identifications.
Claim 45
Dependent Claim
83 words
A physical storage medium for computer-readable data wherein said
medium includes a plurality of similar-sized physical boundaries, comprising: a plurality of parcels, each of said parcels including a plurality of data
entities padding added to individual parcels of said plurality of parcels to cause said
parcels to conform to said similar-sized physical boundaries; and wherein each parcel of said plurality of parcels includes a parcel
identification, said parcel identification related to an offset from a start of said
plurality of similar-sized physical boundaries.
Claim 46
Dependent Claim
25 words
The invention of Claim 45 wherein said plurality of data entities
includes cross reference data, and wherein said cross-reference data includes
references to parcel identifications.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.