Memory management for navigation system

• US 6,073,076 A
• Filed: 03/27/1998
• Issued: 06/06/2000
• Est. Priority Date: 03/27/1998
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Jaugilas, John, Nash, Alex, Natesan, Senthil, Lampert, David S., Crowley, Paul
• Primary Examiner(s): HO, RUAY L
• Application Number:
  US09/049,747
• Time in Patent Office: 802 Days
• Field of Search: 707/1, 707/5, 707/10, 707/100-104, 707/200-206, 701/208
• US Class Current: 701/208
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. The invention of claim 1 wherein the portion of said memory occupied by said cache is allocated at initialization of said navigation system.

6. 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.

7. The invention of claim 1 wherein said cache comprises at least one buffer that forms a contiguous address range in said memory.

8. The invention of claim 1 wherein said memory is formed of a plurality of pages, all having the same size.

9. The invention of claim 8 wherein said page size is 2 K.

10. The invention of claim 1 wherein said geographic database is stored on a physical medium.

11. The invention of claim 10 wherein said physical medium is a CD-ROM disc.

12. The invention of claim 1 wherein said navigation system comprises multiple parcel caches.

13. The invention of claim 1 wherein said portions of the geographic data are generally formed in sizes of 2ⁿ Kilobytes, wherein n is an integer value greater than 1.

14. 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.

15. The invention of claim 14 wherein said page size is 2 K.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. The method of claim 23 wherein said index is a hash table.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.