System and method for accessing compactly stored map element information from memory

• US 6,081,802 A
• Filed: 08/12/1997
• Issued: 06/27/2000
• Est. Priority Date: 08/12/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Atherton, Mark Blelock, Harrington, Paul Sean
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US08/909,805
• Time in Patent Office: 1,050 Days
• Field of Search: 707/1-206, 711/146, 345/432, 375/341, 348/146
• US Class Current: 711/146
• CPC Class Codes: G06T 9/004 Predictors, e.g. intraframe, interframe coding
• CPC Class Codes: Y10S 707/919 Geographic
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Accessing compactly stored map element information from memory using a received encoded identification reference which identifies a map element, such as a link or a node. A link represents a thoroughfare on a map and a node represents an end point of a thoroughfare on the map. A block number is determined and an offset value is determined from the map element'"'"'s identification reference. The block number provides a memory address for the beginning of a block of memory representing a region of the map. The offset value is a memory offset relative to the block'"'"'s memory address. If the block referenced by the block number has not yet been loaded, the block having information about the map element is loaded. Once loaded, the information about each link type of map element in the region is read. The link information is stored within a designated part of a block data structure. Additionally, the link information is used to reconstruct information about the map region'"'"'s node type of map elements. Once reconstructed, the node information is stored within another part of the block data structure. The block data structure remains in a memory cache so that information about the map element can be quickly accessed while information about the map element remains compactly stored in the block of memory.

Claims

1. In a computer system comprising a display device, a processing unit, a user input device, and a memory comprising a plurality of blocks of memory, each block of memory comprising a plurality of memory locations, the display device operable for displaying a computerized road map comprising a plurality of map elements, a method for retrieving information stored in at least one block of memory associated with at least one map element, comprising the steps of:

selecting at least one map element in the electronic map using the user input device,

wherein each map element is selected from the group consisting essentially from a thoroughfare on the computerized roadmap or an endpoint connected to the thoroughfare on the computerized roadmap;

retrieving an identification reference associated with the map element in response to selecting the map element, the identification reference comprising;

a block number associated with at least one block of memory location containing the information associated with the map element, and

an offset value defining at least one memory location within a memory that contains the information associated with the map element;

retrieving the block of memory defined by the block number;

reconstructing the block of memory in a virtual memory; and

retrieving the information associated with the map element from the block of memory location defined by the offset value.

2. The method of claim 1, wherein the computerized road map is divided into a plurality of geographic regions and each geographic region is associated with at least one block of memory.

3. The method of claim 1, wherein the step of reconstructing the block of memory comprises the steps of:

retrieving the plurality of information from the block of memory;

expanding the plurality of information; and

storing the expanded plurality of information in a block data structure in a virtual memory.

4. The method of claim 3, wherein the map element represents a thoroughfare on the computerized road map.

5. A computer-readable medium having computer-executable instructions for executing the steps of claim 1.

6. An apparatus operable for performing the steps of claim 1.

7. A computer-readable medium containing computer executable instructions for accessing information about a plurality of link elements related to a region of a computerized road map, a plurality of node elements related to the region of the computerized road map, comprising the steps of:

retrieving a first block of memory from a storage device associated with the region of the computerized road map;

reconstructing the first block of memory in a virtual memory;

retrieving information associated with at least one link element from the reconstructed first block of memory, the information comprising;

a partial identification reference associated with first node element in the computerized road map, the partial identification reference comprising a first offset value defining a memory location within the reconstructed first block of memory that contains information associated the first node element, and

a full identification reference associated with a second node element in the computerized road map, the identification reference comprising a block number associated with second block of memory associated with the second node element and a second offset value defining a memory location within the second block of memory that contains information associated the second node element;

reconstructing information about each of the node elements from the information about the link elements; and

loading the reconstructed information into a new block data structure.

8. The computer-readable medium of claim 7, wherein each of the plurality of link elements represents a thoroughfare within the region of the map.

9. The computer-readable medium of claim 7, wherein the first node element and the second node element each represent an endpoint of a thoroughfare within the region of the map.

10. The computer-readable medium of claim 7, wherein the full identification reference comprises:

a block number that defines at least one memory location storing the information associated with the map element, and

an offset value defining at least one memory location within the virtual memory that contains the information associated with the map element.

11. The computer-readable medium of claim 10, wherein the block number provides a memory storage location of the block of memory.

12. The computer-readable medium of claim 7, wherein the reconstructing step further comprises;

retrieving the link information associated with each node element;

expanding the link information associated with each node element; and

storing the expanded information in a block data structure in the virtual memory.

13. A method for creating a block data structure comprising a plurality of link elements and a plurality of node elements associated with a computerized road map, the link element comprising a plurality of link information and the plurality of node elements comprising a plurality of node information, comprising the steps of:

retrieving the plurality of link information associated with each link element from a memory device;

storing the plurality of link information within a first part of the block data structure for each link element;

for each link element performing a sequence comprising the steps of;

determining every node element associated with the link element;

retrieving the plurality of node information associated with each node element associated with the link element from the memory device;

reconstructing the plurality of node information associated with each node element associated with each link element; and

storing the reconstructed information associated with each node elements within a second part of the block data structure.

14. The method of claim 13, wherein the first part of the block data structure includes the end of the block data structure.

15. The method of claim 14, wherein the second part of the block data structure includes the beginning of the block data structure.

16. The method of claim 13, wherein the information related to each of the link elements comprises a TO reference associated with the second node element and a FROM reference associated with the first node element.

17. The method of claim 16, wherein the information related to the first node element and the second node element comprise a list of the link elements related to the first and second the node elements.

18. The method of claim 17, wherein the list includes the link elements having the FROM reference associated with the first and second the node elements.

19. The method of claim 17, wherein the list further includes those of the link elements being two-way and having the TO reference associated with the first and second the node elements.

20. A system for accessing information about a plurality of map elements associated with a region of a computerized road map, wherein each map element is associated with an identification reference, comprising:

a processor;

a cache of memory coupled to the processor, the cache of memory for maintaining a block data structure;

a storage device coupled to the processor, the storage device for maintaining a block of memory; and

the processor being operative to;

receive a user input signal selecting at least one of the plurality of map elements;

retrieve the identification reference associated with the selected map element, the identification reference comprising a block number representing a memory storage location of the block of memory within the storage device and an offset value representing a memory location within the block data structure of information about the one of the map elements;

load the block of memory from the storage device having information about the map elements related to the region into a virtual memory,

create the block data structure in the cache of memory,

store information related to a link type of the map elements in a first part of the block data structure,

reconstruct information related to a node type of the map elements and store the reconstructed information in a second part of the block data structure, and

access the information about the map elements within the block data structure.