Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2000-05-23
2004-12-07
Bataille, Pierre (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C701S025000
Reexamination Certificate
active
06829690
ABSTRACT:
REFERENCE TO COPYRIGHTED MATERIAL
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
The present invention relates to geographic data used in navigation systems and more particularly the present invention relates to a way to use geographic data in a navigation system that provides improved performance.
Navigation systems (including navigation applications provided on other types of computing platforms such as general purpose computing platforms) use geographic data. Because navigation systems and navigation applications use geographic data in known ways, the geographic data can be organized and arranged so as to improve the performance of the navigation system or navigation application. Ways that geographic data can be organized and arranged to improve navigation system performance are described in U.S. Pat. Nos. 5,974,419, 5,968,109, and 5,953,722, the entire disclosures of which are incorporated by reference herein.
As described in the aforementioned patents, spatial data are divided into parcels. Each parcel contains data that represent geographic features (e.g., roads, intersections, points of interest, rivers, lakes, etc.) located within a geographic rectangular area. The amount of data in each parcel is constrained not to exceed a specified maximum parcel size. The process of dividing spatial data into parcels is referred to as “parcelization” and data that have been organized into parcels are referred to as being “parcelized.”
FIGS. 1-3
show the same geographic data parcelized using different maximum parcel sizes.
Spatially parcelized data are stored on various physical media, such as CD-ROM disks, DVD disks, hard drives, etc. Parcelized geographic data are accessed from such media and used by navigation systems and navigation applications.
Determining the best size to parcelize geographic data involves balancing several different factors. When a navigation system reads data from a medium into the memory of the navigation system (or other computing platform), there is overhead associated with each I/O operation. For example, it takes longer to read two 8K parcels separately from a CD-ROM disk than it does to read one 16K parcel. I/O performance is therefore degraded when average parcel size is too low.
On the other hand, during normal use of a navigation system, it is preferable to maintain several parcels of data in a buffer memory of the system at the same time. Some systems have limited memory resources. This imposes an upper limit on parcel size. If parcels are relatively large compared to the available buffer memory, relatively few parcels can be stored in the buffer memory at one time and therefore parcels may have to be discarded more frequently because the buffer space is needed for a different parcel. However, a discarded parcel may be needed a short time later and therefore the discarded parcel has to be re-read, thereby degrading performance.
Testing or analysis could suggest at what parcel size these two constraints are in balance and I/O performance is optimal. However, the best parcel size may vary from one hardware platform to another. A parcel size that is optimal for one platform could be sub-optimal for a different platform.
Accordingly, there is a need for a way to use geographic data in navigation systems to improve performance.
SUMMARY OF THE INVENTION
To address these and other objectives, the present invention comprises a method whereby a computing platform that uses geographic data that are spatially organized into parcels of a given size can specify a parcel block size larger than the given size. Thereafter, during runtime, the geographic data are accessed by the computing platform in groups of one or more parcels not larger than the parcel block size.
According to one embodiment, at or after initialization of the computing platform, groupings of parcels corresponding to parcel blocks are determined. Each parcel block has a size larger than the maximum parcel size but not larger than a maximum parcel block size. Data identifying the groupings and the parcels corresponding thereto are stored on the computing platform and the data identifying the groupings and the parcels corresponding thereto are used to access all the parcels corresponding to a parcel block whenever geographic data in any one of the parcels are needed.
REFERENCES:
patent: 4888698 (1989-12-01), Driessen et al.
patent: 5600817 (1997-02-01), Macom, Jr. et al.
patent: 5953722 (1999-09-01), Lampert et al.
patent: 5968109 (1999-10-01), Israni et al.
patent: 5974419 (1999-10-01), Ashby
patent: 6047280 (2000-04-01), Ashby et al.
patent: 6073076 (2000-06-01), Crowley et al.
patent: 6308177 (2001-10-01), Israni et al.
patent: 6460046 (2002-10-01), Meek
patent: 6484090 (2002-11-01), Lahaije et al.
“ECE 360 Principles of Design”, Team Knight Rider, www.rose-hulman.edu/~sandsjk/ece360/ documents/patent%20search.doc.*
Matsuyama et al., “A File Organization for Geographic Information Systems Based on Spatial Proximity” Computer Vision, Graphics and Image Processing 26:303-318 (1984).
Bataille Pierre
Kaplan Lawrence M.
Kozak Frank J.
Navteq North America, LLC
Shutter Jon D.
LandOfFree
Method and system for accessing spatially organized... 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 and system for accessing spatially organized..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for accessing spatially organized... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3317415