Interface layer for navigation system

• US 6,173,277 B1
• Filed: 09/07/1999
• Issued: 01/09/2001
• Est. Priority Date: 10/25/1996
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Bouzide, Paul M., Fernekes, Robert P., Israni, Vijaya S., Lampert, David S., Ashby, Richard A., Jasper, John C., Natesan, Senthil K., Killey, Grant S., Feigen, Jerry S.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US09/390,737
• Time in Patent Office: 490 Days
• Field of Search: 701/201, 701/202, 701/207, 701/208, 701/209, 707/1, 707/2, 707/202, 345/440, 340/995
• US Class Current: 1/1
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G08G 1/0969 having a display in the form of a map
• CPC Class Codes: G09B 29/106 using electronic means
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

An improved method and system that provides for a data access interface layer in a navigation system. The navigation system is of the type that includes a navigation application software program that provides navigating features to a user of the system and a geographic database stored on a computer-readable storage medium wherein the geographical database includes information relating to the geographical region about which the navigation system provides the navigation features to the user. The data access interface layer is preferably stored in the navigation system as a library of software functions. The data access interface layer operates in conjunction with the navigation system application software. The data access interface layer isolates the navigation application software from the geographic data which are stored on the storage medium. The data access interface layer intercepts requests by the navigation application software for geographic data. The data access interface layer retrieves geographic data from the storage medium and converts the data into a format usable by the navigation application software. The data access interface layer also provides for memory management that facilitates accessing and using geographic data from the particular storage medium quickly and efficiently. By recognizing that different media types have different physical formats, the data access interface layer accommodates and isolates the differences so that the portions of the data access interface layer that interact with the navigation application software can be generic.

Claims

1. In a navigation system that includes application programs that provide navigation-related functions, wherein the navigation system uses geographic data stored on a computer-readable medium, interface layer programming comprising:

a query subsystem that accepts requests for geographic data from the application programs and provides responses thereto;

an indexes management subsystem that identifies a location of data on the medium at which is located data required to respond to said requests received by said query subsystem;

a physical-to-logical subsystem that transforms data read from the medium into a format used in said responses; and

a resources management subsystem that provides access to memory resources and I/O of the navigation system for use by said query subsystem, said indexes management subsystem, and said physical-to-logical subsystem.

2. The invention of claim 1 wherein said resources management subsystem comprises:

a memory manager that manages the memory resources of said navigation system that are allocated to said interface layer programming.

3. The invention of claim 2 further comprising a memory pool formed of the memory resources of said navigation system by said memory manager.

4. The invention of claim 3 wherein said memory pool is divided into multiple memory blocks, wherein each of said multiple memory blocks is a contiguous area of memory of a predetermined fixed size.

5. The invention of claim 4 wherein said memory manager receives requests for buffers of given sizes from tasks, allocates memory blocks of said given sizes to satisfy said requests for buffers, and assigns buffer ID'"'"'s to said allocated memory blocks.

6. The invention of claim 2 wherein the memory resources managed by said memory manager include a cache for parcels of data read from said medium and a general purpose heap used for said query subsystem, said indexes management subsystem, and said physical-to-logical subsystem.

7. The invention of claim 6 wherein each of said parcels is identified by a parcel ID, wherein said parcel ID comprises a first part and a second part, and wherein said first part comprises an offset from a start of a file containing the parcel and wherein said second part comprises a size of said parcel.

8. The invention of claim 7 wherein said parcel ID comprises a third part, wherein said third part comprises an indication whether a redundant copy of the data in said parcel is located in another parcel located on said medium.

9. The invention of claim 8 further comprising:

a table located in a memory of said navigation system containing locations at which redundant copies of parcels are located on said medium.

10. The invention of claim 6 wherein said resources management subsystem comprises:

an I/O manager that receives requests for parcels of data to be read from said medium when said parcels are not found in said cache.

11. The invention of claim 10 wherein said I/O manager includes an I/O message queue that contains I/O transactions that include said requests for parcels.

12. The invention of claim 11 wherein said I/O transactions include a priority associated therewith.

13. The invention of claim 10 further comprising:

a physical storage format address mapper that provides to the I/O manager a physical address for a parcel relative to a beginning of a file in which said parcel is located.

14. The invention of claim 13 further comprising:

a file directory mapper that provides to the I/O manager a starting location of said file on said medium.

15. The invention of claim 10 further comprising:

a physical storage format address mapper that translates a parcel ID by which a parcel is identified to a physical sector address and sector count on the medium and returns said physical sector address and sector count to said I/O manager.

16. The invention of claim 15 further comprising:

a file address mapper used by said physical storage format address mapper to locate a file containing the parcel on the medium.

17. The invention of claim 15 wherein said physical storage format address mapper returns multiple addresses for redundantly placed parcels.

18. The invention of claim 15 wherein said I/O manager chooses which of said redundantly placed parcels to read from the medium based upon a current read head location.

19. The invention of claim 10 further comprising:

a file directory mapper that provides to the I/O manager starting locations of each file on said medium.

20. The invention of claim 19 wherein said starting locations are provided as physical media addresses.

21. The invention of claim 20 wherein said physical media addresses conform to ISO-9660.

22. The invention of claim 10 further comprising:

a media device isolation layer that receives a media address, a parcel extent, and an address of a cache buffer from the I/O manager.

23. The invention of claim 22 wherein said media device isolation layer provides a scattered read device capability.

24. The invention of claim 22 wherein said I/O manager provides said media device isolation layer with an array representing a sequence of physical media addresses, extents, and memory buffer pointers.

25. The invention of claim 24 wherein said array has a size which is configurable.

26. In a navigation system having navigation application programs and that uses geographic data stored on a physical storage medium, an improvement comprising:

an interface layer that defines a first set of calls that can be used by said navigation application programs to access a set of geographic data entities on the physical storage medium,

wherein said set of geographic data entities includes one of;

a single entity, a list of multiple entities, and no data entities,

and further wherein said geographic data entities in said set of geographic data entities accessed by said navigation application programs using said interface layer conform to a logical data model which has a decompressed format,

and wherein the interface layer accepts calls that allow the navigation application programs to formulate queries for data, and wherein said calls may be qualified by spatial and non-spatial attributes of desired entities,

and wherein the attributes used to qualify a query for data can be used singly or in combination and can specify a range or a single value,

and further wherein the geographic data on the physical storage medium include spatially organized data, non-spatially organized data, and index data,

and wherein the spatially organized data comprises data that represent segments of roads,

and wherein said spatially organized data are organized into parcels which contain the geographic data entities representing geographic features encompassed within physical geographical localities within a represented geographic region,

and wherein said non-spatially organized data comprise data representing names of navigable features,

and wherein said index data include indexes that relate the spatially organized data and non-spatially organized data to each other,

and wherein the interface layer occupies a portion of memory of the navigation system which is separate from a portion of the memory of the navigation system used for the navigation application programs and wherein a part of the portion of memory occupied by the interface layer is used for a resizable cache for said parcels.

27. The invention of claim 26 wherein said indexes include at least one of a kd-tree index and a B-tree index.

28. The invention of claim 26 wherein the geographic data on said physical storage medium are organized into parcels each of which includes a plurality of data entities and wherein each of said parcels is identified by a unique parcel ID.

29. The invention of claim 28 wherein a size of each of said parcels is related to a physical sector size on the physical storage medium.

30. The invention of claim 28 wherein the interface layer accesses data from the physical storage medium in whole parcels and loads whole parcels into memory in a single physical read in order to resolve said queries.

31. A method of operating a navigation system that includes navigation application programs that are loaded into a memory of said navigation system and executed, and further wherein said navigation system uses geographic data stored on a physical storage medium, the method comprising the steps of:

allocating a resizable portion of said memory for an interface layer program that accepts requests for geographic data from said navigation application programs, determines locations on said physical storage medium at which are located geographic data for responding to said requests, accesses said geographic data from said locations, stores said geographic data accessed from said physical storage medium in a cache formed of said resizable amount of memory, transforms geographic data stored in said cache into a decompressed format and returns geographic data in said decompressed format to said navigation application programs; and

resizing said resizable portion of memory in response to a request from said one of said navigation application programs.