Interface layer for navigation system

• US 6,047,280 A
• Filed: 10/25/1996
• Issued: 04/04/2000
• Est. Priority Date: 10/25/1996
• Status: Expired due to Fees

• Current Assignee: HERE Global B.V. (Nokia 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): Lintz, Paul R.
• Application Number:
  US08/740,298
• Time in Patent Office: 1,257 Days
• Field of Search: 340/988, 340/990, 340/995, 701/200, 701/208, 701/209, 701/211, 707/2, 707/104
• 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. A computer program product for use in a navigation system wherein the navigation system includes a navigation application program that provides navigating features to a user of the navigation system and a geographic database stored on a physical storage medium in a computer-readable physical storage format, said computer program product comprising an interface layer comprising:

programming that accepts and processes requests for geographic data from the navigation application program;

programming that translates geographic data from said physical storage format and provides said geographic data to said navigation application program; and

programming that provides a cursor to said navigation application program in response to a request for geographic data from said navigation application program, said cursor including multiple records, and wherein said programming that provides a cursor is responsive to said programming that translates and is adapted to receive said geographic data therefrom.

2. The invention of claim 1 wherein said programming that provides a cursor further comprises:

programming that provides a first portion of said cursor in a logical data model format; and

programming that provides an entity identifier to a first remainder of said cursor wherein said first remainder is maintained in a compressed format.

3. The invention of claim 2 wherein said programming that provides a cursor further comprises:

a fetch next function that provides a second portion of said cursor in said logical data model format, said second portion comprised of said first remainder.

5. The invention of claim 1 wherein said interface layer further comprises:

programming that manages indexes responsive to said programming that accepts and processes requests and to index information, said programming that manages indexes providing an identifier for obtaining geographic data on said physical storage medium for responding to said requests by said navigation application program.

6. The invention of claim 5 wherein at least a portion of said index information is located on said physical storage medium, and wherein said programming that manages indexes provides parcel identifiers for obtaining pointers to parcels on said physical storage medium containing geographic data for responding to said requests by said navigation application program.

7. The invention of claim 5 wherein said programming that manages indexes further comprises:

an interface for translating a specific entity identifier passed from said navigation application program to a parcel identifier for a parcel on said physical storage medium.

8. The invention of claim 5 wherein said programming that manages indexes further comprises:

an interface for taking an index specifier and query parameters from said programming that accepts and processes requests and returning a set of parcel identifiers.

9. The invention of claim 5 further comprising:

programming that reads said index information from said physical storage medium into a buffer, wherein said programming that manages indexes is coupled to said buffer to obtain said index information therefrom.

12. The invention of claim 1 wherein said programming that decompresses geographic data further comprises:

a first interface for translation of geographic database entities from the physical storage format into an intermediate format; and

a second interface for translation of geographic database entities from said intermediate format to the decompressed format in which said geographic data are provided to said programming that accepts and processes requests.

13. The invention of claim 12 wherein said programming that decompresses further comprises:

programming responsive to a metadata table on said physical storage medium and said first interface and adapted to translate said geographic data in said intermediate format at a first version level to an intermediate format at a second version level and provide said geographic data in said intermediate format at a second version level to said second interface.

4. A computer program product for use in a navigation system wherein the navigation system includes a navigation application program for providing navigating features to a user of the navigation system and a geographic database stored on a physical storage medium in a compressed, computer-readable physical storage format, said computer program product comprising an interface layer located logically between said navigation application program and said geographic database, said interface layer comprising:

programming that accepts and processes requests for geographic data from the navigation application program; and

programming that decompresses geographic data from said physical storage format and provides said geographic data to said navigation application program in a decompressed format.

10. The invention of claim 4 wherein the physical storage format of the geographic database organizes said geographic data into a plurality of parcels, and wherein said interface layer further comprises:

programming for associating said requests with parcels in said physical storage format and

causing said parcels to be read from said physical storage medium.

11. The invention of claim 4 wherein the physical storage medium comprises a CD-ROM disk.

14. The invention of claim 4 wherein said interface layer further comprises:

programming that manages resources comprising;

programming that allocates and frees memory of said navigation system for use as a memory pool by said interface layer; and

programming that accesses a cache memory buffer in said memory pool that stores a parcel read from said physical storage medium, said parcel identified by means of a parcel identifier.

15. The invention of claim 14 wherein said programming that manages resources further comprises:

programming that initiates an I/O transaction from the physical storage medium to read said parcel therefrom if said programming that accesses a cache memory buffer finds that said parcel is not stored in said cache memory buffer.

16. The invention of claim 14 wherein said programming that manages resources further comprises:

programming that locks a cache memory when a parcel is stored therein and a buffer address is returned to said programming that decompresses geographic data.

17. The invention of claim 14 wherein said programming that manages resources further comprises:

programming that resizes said memory pool in response to a call from said navigation application program.

18. The method of claim 4 wherein said programming that decompresses further comprises:

programming that transforms said geographic data from said physical storage format into an intermediate decompressed format; and

programming that transforms said geographic data from said intermediate decompressed format to said decompressed format usable by said navigation application program.

19. The invention of claim 4 wherein said geographic data is provided to said navigation application program in a generic ASCII format.

20. The invention of claim 4 wherein said geographic data is provided to said navigation application program as data entity records of fixed lengths without cross-reference information.

21. A computer program product for use in a navigation system wherein the navigation system includes a navigation application program that provides navigating features to a user of the navigation system and a geographic database stored on a physical storage medium in a computer-readable physical storage format, said computer program product comprising an interface layer comprising:

programming that accepts and processes requests for geographic data from the navigation application program; and

programming that translates geographic data from said physical storage format and provides said geographic data to said navigation application program in a logical data model format, wherein said logical data model format includes uncompressed entity records of fixed lengths, and wherein said programming that translates further comprises;

programming that unpacks said geographic data from said physical storage format into a decompressed intermediate format; and

programming that transforms said geographic data from said decompressed intermediate format into data entities in said logical data format for returning to said navigation application program.

22. A computer program product for use in a navigation system wherein the navigation system includes a navigation application program that provides navigating features to a user of the navigation system and a geographic database stored on a physical storage medium in a computer-readable physical storage format, said computer program product comprising an interface layer comprising:

programming that accepts and processes requests for geographic data from the navigation application program;

programming that translates geographic data from said physical storage format and provides said geographic data to said navigation application program in a logical data model format,

programming that allocates and frees memory of said navigation system for use as a memory pool by said interface layer;

programming that accesses a cache memory buffer in said memory pool that stores a parcel read from said physical storage medium, wherein said parcel can be identified by means of a parcel identifier

programming that initiates an I/O transaction from the physical storage medium to read said parcel therefrom if said cache memory buffer accessing means finds that said parcel is not stored in said cache memory buffer;

wherein said programming that initiates an I/O transaction further comprises;

stores parcel identifiers in a queue and

reorders parcel identifiers while in said queue.

23. The invention of claim 22 wherein said programming that initiates an I/O transaction translates said parcel identifiers to physical media addresses while in said queue.

24. The invention of claim 22 wherein said navigation system further includes a media device driver and wherein said programming that initiates an I/O transaction obtains from said media device driver a physical read head position and uses said physical read head position when reordering said parcel identifiers.

25. A method of using a computer-based navigation system wherein said navigation system includes navigation application program functions wherein said navigation application program functions are adapted to use a geographic database stored on a computer-readable medium in a physical storage format, the method comprising:

accepting a request from one of said navigation application program functions for geographic data;

using an index to identify the geographic data in said physical storage format for responding to said request;

transforming geographic data stored in said physical storage format into a format usable by said navigation application program functions; and

after a plurality of data entities are identified in response to said request from said one of said navigation application program functions, providing a first partial result set of said plurality of data entities in said format usable by said navigation application program functions to said one of said navigation application program functions.

26. The method of claim 25 further comprising the step of:

if said plurality of data entities exceeds a first threshold, providing a first partial result set of said plurality of data entities up to said first threshold in said format usable by said navigation application program functions to said one of said navigation application program functions and maintaining entity identifiers for a portion of said plurality data entities exceeding said first threshold.

27. The method of claim 25 further comprising the steps of:

if said plurality of data entities exceeds a first threshold and a second threshold greater than said first threshold, providing a first partial result set of said plurality of data entities up to said first threshold in said format usable by said navigation application program functions to said one of said navigation application program functions,

maintaining entity identifiers for a portion of said plurality data entities exceeding said first threshold, and

maintaining a reference cursor to reexecute said request for geographic data for data entities exceeding said second threshold.

28. A method of using a computer-based navigation system wherein said navigation system includes navigation application program functions wherein said navigation application program functions are adapted to use a geographic database stored on a computer-readable storage medium in a physical storage format, the method comprising:

reading a metadata file from said storage medium;

storing a portion of said metadata file in memory;

accepting a request from one of said navigation application program functions for geographic data;

transforming geographic data stored in said physical storage format into a format usable by said navigation application including using said metadata file to translate from a version level of said physical storage format to a version level of said navigation application program functions; and

providing said transformed geographic data to said one of said navigation application program functions.

29. The method of claim 28 wherein said metadata file comprises tables for different version levels, and wherein the method further comprises the step of:

using a version level of a data access interface layer that performs the step of accepting a request from one of the navigation applications for geographic data to identify which of said tables to use.

30. The invention of claim 28 wherein said metadata file includes information that describes content of various data attributes and values appearing in a given database entity at a given version level.

31. The method of claim 28 wherein said step of transforming further comprises:

converting from said physical storage format into a decompressed intermediate format; and

converting from said decompressed intermediate format into the format useable by the navigation application.

32. The method of claim 28 wherein said step of transforming further comprises:

using said metadata file to extract a data element relative to a beginning of a particular physical storage format entity.

33. The method of claim 28 wherein the step of reading a metadata file from said storage medium is performed through an operating system kernel.

34. The method of claim 28 wherein the step of reading a metadata file from said storage medium is performed through a physical devices subsystem that includes an operation system isolation layer and a media device isolation layer.

35. The method of claim 28 wherein the step of reading a metadata file from said storage medium is performed at initialization.

36. The method of claim 28 further comprising the step of:

maintaining the metadata file in memory during operation of the navigation system so that said metadata file can be used during subsequent data accesses from said storage medium.

44. The invention of claim 34 further comprising the steps of:

when operating each of said navigation systems implemented on different hardware platforms,

using said navigation application to request geographic data from said interface layer programming according to said common interface; and

using said interface layer programming to access and read data from the geographic database in the same format associated therewith to satisfy requests for geographic data from said navigation application.

45. The invention of claim 34 wherein said interface layer programming further comprises:

query logic programming that receives requests from the navigation application for geographic data;

data transformation programming that transforms geographic data from a physical storage format of a physical storage medium upon which said geographic database is stored; and

data return programming that provides said transformed geographic data to said navigation application in response to said requests.

46. The invention of claim 45 wherein said interface layer programming further comprises:

indexes management programming responsive to said query logic programming and comprising;

programming that associates said requests from said navigation application with parcel identifiers associated with parcels in said physical storage format containing geographic data; and

programming that provides said parcel identifiers to memory management library programming to obtain said parcels to provide to said data transformation programming for transformation therein.

47. The invention of claim 46 wherein said indexes management programming further comprises:

programming that obtains said parcel identifiers from said geographic database, and

programming that obtains pointers to parcels on said physical storage medium containing geographic data for responding to said requests by said navigation application.

48. The invention of claim 46 wherein said programming that manages indexes further comprises:

programming that translates specific entity identifiers passed from said navigation application to parcel identifiers for parcels on said physical storage medium.

49. The invention of claim 46 wherein said programming that manages indexes further comprises:

programming that takes index specifiers and query parameters from said query logic programming and returns a set of parcel identifiers.

37. A computer program product for use in a navigation system wherein the navigation system includes a navigation application program that provides navigating features to a user of the navigation system and a geographic database stored on a physical storage medium in a computer-readable physical storage format, said computer program product comprising an interface layer comprising:

programming that accepts and processes requests for geographic data from the navigation application program; and

programming that translates geographic data from said physical storage format and provides said geographic data to said navigation application program, wherein said programming that translates is responsive to metadata provided with said geographic data and which is used to translate said geographic data at a first version level to a second version level and provide said geographic data at said second version level to said navigation application program.

38. The invention of claim 37 wherein said metadata comprises tables for different version levels.

39. The invention of claim 38 wherein said tables are provided for each data version level from an earliest version level to a current version level.

40. The invention of claim 37 wherein said storage medium comprises one of a CD-ROM disk and PCMCIA card.

41. The invention of claim 37 wherein said metadata is used to provide backward compatibility.

42. The invention of claim 37 wherein said metadata allows a newer navigation application software program to use an older version of a geographic database.

43. A method by which navigation systems implemented on different hardware platforms can use copies of a geographic database having a same format, the method comprising the steps of:

providing copies of interface layer programming to manufacturers of said navigation systems implemented on different hardware platforms, wherein said interface layer programming provides a common interface from which a navigation application in each of said navigation systems implemented on different hardware platforms can request geographic data contained in a geographic database associated therewith, wherein the geographic database associated with each of said navigation systems is in said same format; and

installing said copies of said interface layer programming in each of said navigation systems implemented on said different hardware platforms.

50. A computer program product for use in a navigation system wherein the navigation system includes a navigation application program for providing navigating features to a user of the navigation system and a geographic database stored on a physical storage medium in a computer-readable physical storage format, said computer program product comprising an interface layer comprising:

programming that provides a C language data structure view to the navigation application program;

programming that accepts and processes requests for geographic data from the navigation application program; and

programming that translates geographic data from said physical storage format and provides said geographic data to said navigation application program as a C language data structure in a fully decompressed form.