Patent US6073076A successfully refreshed from Google Patents.
US6073076A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Memory management for navigation system
Assignee: Here Global BV
•
Filing: 1998-03-27
•
Granted: 2000-06-06
•
Expires: 2018-03-27
Abstract
Abstract A method and system for managing memory resources in a system used in conjunction with a navigation application program that accesses geographic data. The geographic data are comprised of a plurality of data records. The plurality of data records are organized into parcels, each of which contains a portion of the plurality of data records, such that the data records in each portion of the plurality of data records that forms each parcel are accessed together. One or more buffers each that forms a contiguous portion of the memory of the navigation system is provided as a cache to store a plurality of parcels. One or more data structures located outside the contiguous portion of memory identify the parcels of data stored in the cache and the locations in the cache at which the parcels are stored. The one or more data structures located outside the contiguous portion of memory in which the parcels are cached are used to manage the parcel cache to use it efficiently. These one or more data structures located outside the contiguous memory in which the parcels are cached are also used to defragment the parcel cache.
Inventors
- 👤 Paul Crowley
- 👤 John Jaugilas
- 👤 Alex Nash
- 👤 Senthil Natesan
- 👤 David S. Lampert
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 16:43
CPC Classifications
G; G01; G01C; G01C21/00; G01C21/26; G06; G06F; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
73 words
A system for managing memory for a navigation system that uses geographic data, the system comprising a cache occupying a portion of said memory and used for holding portions of the geographic data; and at least one data structure that identifies each of the portions of the geographic data contained in said cache and associates each of the portions so identified with a position in said cache at which the portion is located.
Claim 2
Independent Claim
73 words
A system for managing memory for a navigation system that uses geographic data, the system comprising a cache occupying a portion of said memory and used for holding portions of the geographic data; and at least one data structure that identifies each of the portions of the geographic data contained in said cache and associates each of the portions so identified with a position in said cache at which the portion is located.
Claim 3
Dependent Claim
81 words
The invention of claim 1 wherein said at least one data structure comprises: a plurality of first data structures, each of said first data structures identifying a position in said cache at which a respective one of said portions of geographic data is stored; and a second data structure that includes an identification of each of said portions of geographic data contained in said cache, wherein each of said identifications is associated with one of said plurality of first data structures.
Claim 4
Dependent Claim
35 words
The invention of claim 1 wherein said geographic data are comprised of a plurality of data records and wherein each of said portions of geographic data comprises a portion of said plurality of data records.
Claim 5
Dependent Claim
67 words
The invention of claim 1 wherein said geographic data are comprised of a plurality of data records and wherein each of said portions of geographic data comprises a spatially organized portion of said plurality of data records wherein the data records in each portion represent geographic features that are encompassed within a separate one of a plurality of rectangular areas which together encompass the entire geographic region.
Claim 6
Dependent Claim
23 words
The invention of claim 1 wherein the portion of said memory occupied by said cache is allocated at initialization of said navigation system.
Claim 7
Dependent Claim
26 words
The invention of claim 1 wherein said portion of memory occupied by said cache can be augmented during runtime by addition of at least one buffer.
Claim 8
Dependent Claim
22 words
The invention of claim 1 wherein said cache comprises at least one buffer that forms a contiguous address range in said memory.
Claim 9
Dependent Claim
20 words
The invention of claim 1 wherein said memory is formed of a plurality of pages, all having the same size.
Claim 10
Dependent Claim
12 words
The invention of claim 8 wherein said page size is 2 K.
Claim 11
Dependent Claim
15 words
The invention of claim 1 wherein said geographic database is stored on a physical medium.
Claim 12
Dependent Claim
13 words
The invention of claim 10 wherein said physical medium is a CD-ROM disc.
Claim 13
Dependent Claim
13 words
The invention of claim 1 wherein said navigation system comprises multiple parcel caches.
Claim 14
Dependent Claim
30 words
The invention of claim 1 wherein said portions of the geographic data are generally formed in sizes of 2 n Kilobytes, wherein n is an integer value greater than 1.
Claim 15
Dependent Claim
38 words
The invention of claim 13 wherein said memory is formed of a plurality of pages, all having the same size, and all having a size of 2 m Kilobytes, wherein m is an integer value greater than 1.
Claim 16
Dependent Claim
12 words
The invention of claim 14 wherein said page size is 2 K.
Claim 17
Dependent Claim
29 words
The invention of claim 1 wherein said at least one data structure occupies a portion of said memory other than the portion of said memory occupied by said cache.
Claim 18
Dependent Claim
143 words
The invention of claim 1 wherein said cache comprises a plurality of buffers, wherein each of said plurality of buffers comprises a contiguous address range of said memory and is used for holding at least one of said portions of geographic data, and wherein said at least one data structure comprises: a plurality of pools of first data structures, each of said plurality of pools associated with a separate one of said plurality of buffers, and each of said first data structures in each of said pools identifying one of said portions of geographic data contained in said buffer with which its respective pool is associated; and a second data structure that includes an identification of each of said portions of geographic data contained in said cache, wherein each of said identifications is associated with one of said plurality of first data structures.
Claim 19
Dependent Claim
32 words
The invention of claim 2 wherein each of said first data structures includes information that identifies a position in said cache at which storage of the respective portion of geographic data starts.
Claim 20
Dependent Claim
31 words
The invention of claim 2 wherein each of said first data structures includes information that identifies a size in said cache used for storage of the respective portion of geographic data.
Claim 21
Dependent Claim
37 words
The invention of claim 1 wherein each of said portions of geographic data represents a minimum amount of said geographic data that can be accessed at a time by said navigation system in a single read operation.
Claim 22
Dependent Claim
153 words
A cache management system for a navigation system that uses a geographic database and that has a memory, said cache management system comprising: a cache for parcels of geographic data, wherein each of said parcels comprises a portion of a plurality of data records that form said geographic database, and wherein said cache is formed of at least one contiguous buffer of said memory, wherein said at least one buffer is substantially larger than the sizes of said parcels so that a plurality of parcels can occupy said buffer; a header pool located outside said contiguous buffer of memory and containing header information for each of the parcels that occupy said buffer; and a hash table located outside said contiguous buffer of memory and containing a searchable index of parcel identifiers, each of which refers to said header information in said header pool, whereby a parcel contained in said cache can be located.
Claim 23
Dependent Claim
153 words
A cache management system for a navigation system that uses a geographic database and that has a memory, said cache management system comprising: a cache for parcels of geographic data, wherein each of said parcels comprises a portion of a plurality of data records that form said geographic database, and wherein said cache is formed of at least one contiguous buffer of said memory, wherein said at least one buffer is substantially larger than the sizes of said parcels so that a plurality of parcels can occupy said buffer; a header pool located outside said contiguous buffer of memory and containing header information for each of the parcels that occupy said buffer; and a hash table located outside said contiguous buffer of memory and containing a searchable index of parcel identifiers, each of which refers to said header information in said header pool, whereby a parcel contained in said cache can be located.
Claim 24
Independent Claim
136 words
A method for operating a navigation system including a memory, wherein the navigation system executes a navigation application program to provide navigation functions and uses a geographic database having data records that represent geographic features in a geographic region and wherein said geographic database is organized into a plurality of parcels on a medium, each of said parcels including a plurality of the data records, the method comprising the steps of: providing a contiguous portion of said memory for use as a parcel cache; during execution of the navigation application program to provide said navigation functions, storing parcels of data read from said medium into said parcel cache; storing data relating to each of said parcels stored in said parcel cache in a header structure maintained in a portion of the memory separate from said parcels.
Claim 25
Independent Claim
136 words
A method for operating a navigation system including a memory, wherein the navigation system executes a navigation application program to provide navigation functions and uses a geographic database having data records that represent geographic features in a geographic region and wherein said geographic database is organized into a plurality of parcels on a medium, each of said parcels including a plurality of the data records, the method comprising the steps of: providing a contiguous portion of said memory for use as a parcel cache; during execution of the navigation application program to provide said navigation functions, storing parcels of data read from said medium into said parcel cache; storing data relating to each of said parcels stored in said parcel cache in a header structure maintained in a portion of the memory separate from said parcels.
Claim 26
Dependent Claim
29 words
The method of claim 22 further comprising: storing an index identifying each of said parcels, wherein said index refers to the respective header structure maintained separate from said parcels.
Claim 27
Dependent Claim
12 words
The method of claim 23 wherein said index is a hash table.
Claim 28
Independent Claim
107 words
A method of operating a navigation system that includes a memory, wherein the navigation system executes a navigation application program to provide navigation functions and uses a geographic database having data records that represent geographic features in a geographic region, wherein said geographic database is organized into a plurality of parcels each of which includes a plurality of the data records, the method comprising the steps of: requesting parcels that contain data required to provide said navigation functions; and organizing identifications of said requested parcels into a queue of parcel identifications, wherein multiple requests for the same parcel are linked to single parcel identification in said queue.
Claim 29
Independent Claim
107 words
A method of operating a navigation system that includes a memory, wherein the navigation system executes a navigation application program to provide navigation functions and uses a geographic database having data records that represent geographic features in a geographic region, wherein said geographic database is organized into a plurality of parcels each of which includes a plurality of the data records, the method comprising the steps of: requesting parcels that contain data required to provide said navigation functions; and organizing identifications of said requested parcels into a queue of parcel identifications, wherein multiple requests for the same parcel are linked to single parcel identification in said queue.
Claim 30
Dependent Claim
28 words
The method of claim 25 further comprising the step of forwarding said queue of parcel-identifiers to a media device layer to read said parcels from the geographic database.
Claim 31
Dependent Claim
100 words
The method of claim 25 where a request for a parcel that represents data not yet needed for performing a navigation function is not linked to one of said single parcel identifications in said queue if adding said parcel that represents data not yet needed for performing a navigation function to a parcel cache in said memory which is used to store all parcels read from said geographic database causes a limit imposed on the portion of said parcel cache that can be used for parcels that represent data not yet needed for performing a navigation function to be exceeded.
Claim 32
Dependent Claim
30 words
The method of claim 25 further comprising: storing a hash table in said memory, said hash table indexed on identification data of each of said parcels in said parcel cache.
Claim 33
Independent Claim
234 words
A method for operating a navigation system including a memory, wherein the navigation system executes a navigation application program to provide navigation functions and uses a geographic database having data records that represent geographic features in a geographic region and wherein said geographic database is organized into a plurality of parcels on a medium, each of said parcels including a plurality of the data records, and further wherein a contiguous portion of said memory is used as a parcel cache for storing parcels read from said medium in blocks thereof, and further wherein data relating to each of said parcels in said parcel cache is stored in a header structure maintained in a portion of the memory separate from said contiguous portion used as said parcel cache, the method comprising the step of: defragmenting said parcel cache in order to store a parcel therein when said parcel cache already contains a plurality of parcels, wherein said defragmenting comprises: skipping any block contains a parcel indicated by the header structure to be locked; and if an in-use block is completely able to fill an adjacent free block of said contiguous portion of said memory, or if a single in-use block is between two free blocks of said contiguous portion of said memory, moving the block indicated by the header structure to be in-use to the adjacent block indicated in the header structure to be free.
Claim 34
Independent Claim
234 words
A method for operating a navigation system including a memory, wherein the navigation system executes a navigation application program to provide navigation functions and uses a geographic database having data records that represent geographic features in a geographic region and wherein said geographic database is organized into a plurality of parcels on a medium, each of said parcels including a plurality of the data records, and further wherein a contiguous portion of said memory is used as a parcel cache for storing parcels read from said medium in blocks thereof, and further wherein data relating to each of said parcels in said parcel cache is stored in a header structure maintained in a portion of the memory separate from said contiguous portion used as said parcel cache, the method comprising the step of: defragmenting said parcel cache in order to store a parcel therein when said parcel cache already contains a plurality of parcels, wherein said defragmenting comprises: skipping any block contains a parcel indicated by the header structure to be locked; and if an in-use block is completely able to fill an adjacent free block of said contiguous portion of said memory, or if a single in-use block is between two free blocks of said contiguous portion of said memory, moving the block indicated by the header structure to be in-use to the adjacent block indicated in the header structure to be free.
References Cited (Backward Citations)
US4876651A
Cited
US5101357A
Cited
US5848373A
Cited
US5867110A
Cited
US5893901A
Cited
US5781195A
Cited
US5953722A
Cited
US5968109A
Cited
US5966135A
Cited
US5978730A
Cited
US6016485A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-06-06 | 2003-12-06 | 2004-06-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-06-06 | 2007-12-06 | 2008-06-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-06-06 | 2011-12-06 | 2012-06-06 | $7700.00 | Window Closed / Lapsed |