Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2002-11-26
2004-08-24
Zanelli, Michael J. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C707S793000
Reexamination Certificate
active
06782319
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.
Many 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, and U.S. patent application Ser. No. 09/629,224 entitled “Method for Organizing Map Data,” filed Jul. 28, 2000, now U.S. Pat. No. 6,591,270 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 displaying 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 of organizing map data on a physical storage medium. The map data represents geographic features located in a geographic region. The method identifies at least one dense area in the geographic region. The map data representing the geographic features within the dense area have a data size exceeding a predetermined maximum size for a predetermined sized geographic area of the region. The method subdivides the map data representing the geographic features within the dense area into parcels so that the portion of map data contained in the parcel is close to a predetermined parcel size. The method subdivides the map data less the map data representing the dense area into parcels so that the portion of map data contained in the parcel is close to the predetermined parcel size. Additionally, the method locates the map data in each parcel together on the physical storage medium.
REFERENCES:
patent: 4888698 (1989-12-01), Driessen et al.
patent: 4937572 (1990-06-01), Yamada 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: 5974419 (1999-10-01), Ashby
patent: 6035299 (2000-03-01), White et al.
patent: 6112153 (2000-08-01), Schaaf et al.
patent: 6112200 (2000-08-01), Livshutz et al.
patent: 6122594 (2000-09-01), Tamaki et al.
patent: 6141454 (2000-10-01), Seymour et al.
patent: 6233521 (2001-05-01), Nomura
patent: 6324470 (2001-11-01), White
patent: 6430497 (2002-08-01), Gaertner et al.
patent: 6473691 (2002-10-01), Winter et al.
patent: 6484090 (2002-11-01), Lahaije et al.
patent: 6546334 (2003-04-01), Fukuchi et al.
patent: 6591270 (2003-07-01), White
patent: 2001/0051851 (2001-12-01), Suzuki et al.
patent: 2002/0147545 (2002-10-01), Norimoto
patent: 2003/0028315 (2003-02-01), Miyahara
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.
Kaplan Lawrence M.
Kozak Frank J.
Navteq North America, LLC
Shutter Jon D.
Zanelli Michael J.
LandOfFree
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.
Profile ID: LFUS-PAI-O-3276098