Method for organizing map data

Details Method for organizing map data Method for organizing map data

2000-07-28

2003-07-08

Rones, Charles (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C701S209000, C382S243000

Reexamination Certificate

active

06591270

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a method and system for the organization and storage of map data that facilitate use of the map data by navigation application programs such as those in navigation systems. The present invention also relates to a physical storage medium having map data stored thereon having the aforementioned method of organization.
Most navigation systems use map data that are stored on read-only disks (e.g., CD-ROM disks, DVD-ROM disks, etc.) or hard disks. An important factor that affects the performance of some navigation system features, such as map display, is the time required to fetch the map data from the disk. A large portion of the time required to fetch map data is attributable to the seek time of the device (i.e., the time for the read head of the navigation system to move from a current track to the track where the data are located). This factor is important for CD-ROM and DVD-ROM disks but also applies to some extent to hard disks.
Because seek time accounts for a large portion of the time required to fetch data from a disk, techniques for organizing map data have been developed that reduce the number of seeks (and thus the total seek time) for a given request thereby helping to improve navigation system performance. One way to reduce the number of seeks when accessing map data for certain navigation system functions is to organize the map data spatially. In general, when map data are organized spatially, geographic features that are close together physically in the geographic region are represented by data records that are physically (or logically) close together in the map database (and possibly also close together on the medium upon which the map data are stored).
There are various methods by which data that represent geographic features can be organized spatially. One of the ways that data that represent geographic features can be organized spatially is to first identify groups of data entities that represent geographic features that are located close together and then arrange the groups spatially. The groups of data may be referred to as “parcels,” “buckets,” or “map regions,” although other terminology may also be used. The data entities within each group may also be organized spatially or the data entities within a group may be organized according to another arrangement. Methods for organizing map data spatially are described in U.S. Pat. Nos. 5,968,109 and 5,974,419, the entire disclosures of which are incorporated by reference herein.
Some map data parcelization techniques attempt to achieve uniform data size parcels (e.g., 32 or 64 kilobytes per parcel) or fixed geographic size parcels (e.g., 0.02 degree delta latitude by 0.03 degree delta longitude or some other latitude/longitude “rectangle”). A disadvantage of uniform data size parcels is that when a map display rectangle spans several parcels that are not adjacent on the disk, several seeks are required to fetch the requested data, thereby possibly adversely affecting navigation system performance. On the other hand, a disadvantage of uniform geographic size parcels is that the data sizes of parcels vary widely from densely populated areas to sparsely populated areas. If the area corresponding to each uniform geographic size parcel is too small, the overhead necessary to store information about each parcel becomes excessive. However, if the area corresponding to uniform geographic size parcel is too large, the amount of data contained in densely populated regions may exceed the data size limitations of a parcel. For example, if two-byte offsets are used to locate byte positions of a parcel, then the inherent limit of 64 kilobytes constrains the amount of data that can be stored in a parcel.
Accordingly, there is a need for an improved way to organize map data that reduces the number of fetches needed to obtain the data required to represent an area while accommodating wide variations in data density across a region.
SUMMARY OF THE INVENTION
To address these and other objectives, the present invention comprises a method and system for organizing and storing map data that facilitates use of the map data by navigation application programs such as those in navigation systems. The map data represent geographic features located in a region. The map data are organized into parcels such that each parcel contains a portion of the map data. The map data contained in each parcel represent those geographic features contained in a corresponding separate one of a plurality of rectangular areas located in the region. Each rectangular area has a uniform dimension in a first coordinate direction but has a dimension in the other coordinate direction such that the map data that represent the geographic features contained in the rectangular area are close to, but do not exceed, a maximum data size for a parcel.


REFERENCES:
patent: 4888698 (1989-12-01), Driessen et al.
patent: 5170353 (1992-12-01), Verstraete
patent: 5513110 (1996-04-01), Fujita et al.
patent: 5953722 (1999-09-01), Lampert et al.
patent: 5963956 (1999-10-01), Smartt
patent: 5968109 (1999-10-01), Israni et al.
patent: 6035299 (2000-03-01), White et al.
patent: 6112153 (2000-08-01), Schaaf et al.
patent: 6141454 (2000-10-01), Seymour et al.
patent: 6324470 (2001-11-01), White
patent: 6430497 (2002-08-01), Gaertner et al.
patent: WO 99/58934 (1999-11-01), None
Samet, Hanan: “The Strategies for Optimizing the Use of Redundancy in Spatial Databases”,The Design and Analysis of Spatial Data Structures,ISBN 0-201-50255-0, Chapter 2.4 (No date).
Matsuyama, et al.: “A file Organization for Geographic Information Systems Based on Spatial Proximity”,Computer Vision, Graphics, and Image Processing26, 303-318. 1984.

Affiliated with

Also associated with

Rating

Method for organizing map data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for organizing map data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for organizing map data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3091515