Caching for pathfinding computation

Details Caching for pathfinding computation Caching for pathfinding computation

1999-08-06

2002-04-23

Zanelli, Michael J. (Department: 3661)

Data processing: vehicles, navigation, and relative location

Navigation

Determination of travel data based on the start point and...

C701S209000

Reexamination Certificate

active

06377887

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a system for caching data for a pathfinding computation.
2. Description of the Related Art
The computer has revolutionized the idea of a map from an image statically depicting the location of physical features to the electronic map, which consists of geographically referenced electronic data quantifying a physical, social or economic system. The range of information included in electronic maps is unlimited; for example, electronic maps could include distances between elements, driving time, lot numbers, tax information, tourist information, etc. Additionally, storing a map as a file on a computer allows for unlimited software applications to manipulate that data.
One advantage of the electronic map is to store and determine costs associated with various portions of a map. Examples of cost include time, distance, tolls paid, ease of turning, quality of scenery, etc. Thus, a traveler may wish to know how far that traveler can drive without paying more than $10 in tolls, what restaurants are within a 10 minute drive, or what gas stations are within a one mile walk. In each of these situations, the traveler desires to know where they can travel to within a given cost. A more detailed discussion of costs can be found in U.S. patent application Ser. No. 08/756,263, Using Multiple Levels Of Costs For A Pathfinding Computation, filed Nov. 25, 1996, Richard F. Poppen, now U.S. Pat. No. 5,893,081 incorporated herein by reference.
Electronic maps can also be used for pathfinding, which is a method for computing a route between an origin and a destination. An electronic map that is used for pathfinding must carry information about the connectivity of a road network, that is, information about the ways in which pieces of road do or do not connect to each other, for example, where there are ordinary intersections, where there are overpasses, where turns are restricted, and so on. For an area of any significant extent, this is a very large amount of information. An electronic map can include tens or hundreds of megabytes of data. In order to hold such vast quantities of data economically and allow a user to replace maps with updated copies easily, many current pathfinding apparatus (which includes general purpose computers with pathfinding software, automotive navigation systems or other map application equipment) use CD-ROMs to store the electronic map data.
Although CD-ROMs hold a great deal of data, accessing that data can be relatively slow. For example, a typical CD-ROM drive used for automotive pathfinding may take on the order of ⅓ of a second for each read access. If a pathfinding system had to wait ⅓ of a second every time it needed data, the time needed to compute a path would not be acceptable to a user. A user of a navigational pathfinding system stored in a car typically would demand very fast reponse times when requesting a path because a user currently driving in the car needs to know which way to turn. For these reasons, it is very important to minimize the number of disk accesses required to compute a path. It is noted that some systems may use peripheral devices other than CD-ROMs, for example, hard disks, floppy disks, solid state memory, etc. These other storage devices suffer similar access time limitations.
One attempt to minimize the number of disk accesses required to compute a path includes grouping map data into clusters, that is, grouping together on a CD-ROM (or other storage device) information about sets of road segments often used in the same path computation. For example, a number of consecutive segments of the same street, road segments that cross each other or road segments that lead to a highway may be stored in a single cluster. Note that these clusters need not be geographically based. Information about roads on two sides of a river in an area that is not close to a bridge would probably not be stored in the same cluster, since the roads would not be used in relation to each other during path calculation even though they may be quite close to each other geographically. Information about highways over a wide area are good candidates to be stored together in one cluster because a path computation typically explores the connections of highways with other highways. There are many ways to cluster data to increase performance. One example of clustering data can be found in U.S. patent application Ser. No. 08/245,690, Method for Clustering Multi-Dimensional Data, filed May 18, 1994, Poppen et al., now U.S. Pat. No. 5,706,503, incorporated herein by reference. When clustering is used with a suitable cache methodology, the time for pathfinding is saved because information needed by the pathfinding computation is often already in the cache (or main memory) having been read as part of a cluster which includes data already used.
Caching is a well-known process of saving records recently read in order to reduce the number of disk/memory accesses. One of the most well known forms of caching includes using a small memory local to a processor called a cache memory. Certain data recently used is typically stored in the cache memory, with access to the cache memory being quicker than access to main memory. In this example, the cache memory caches data between main memory and a processor.
Another example of caching is to cache data between a storage device and main memory. An alternative to using a cache memory separate from main memory is to use a portion of main memory as the cache memory. When data is read from the storage device it is typically kept in the cache memory portion (hereinafter called “cache”) of the main memory for a certain amount of time so that later access to that data will be quicker than accessing the storage device. The portion of the memory allocated as the cache will hold a number of records of data along with an indication of how recently each record has been used. When the program needs to read a given record, the program first looks in the cache for the record. If the record is in the cache, the program uses the information stored in the cache rather than reading the disk file again. If the record is not in the cache, and there is enough unused space in the cache to hold the record, the record is read into the cache and then used by the program. If the record is not in the cache and there is not enough unused space in the cache to hold the record, the least recently used record or records are discarded to provide sufficient room to hold the new record. A record of data could include one or more clusters of data or another suitable arrangement of data. If map data is clustered in such a way that information regarding a given road segment is often used shortly after the use of information regarding another road segment in the same cluster there will be a significant speed improvement in the pathfinding process because the number of accesses to the CD-ROM will be decreased.
The path calculation remains a lengthy process even when using a cache as described above. Every cluster used in the computation still needs to be read at least once. Since the pathfinding computation may need to read a large number of clusters at the beginning of the pathfinding computation, the user of the pathfinding apparatus still spends a significant amount of time waiting for the pathfinding apparatus to read all the data prior to a path being calculated.
Therefore, a system is needed that reduces the amount of time needed to calculate a path from an electronic map.
SUMMARY OF THE INVENTION
The present invention, roughly described, provides for a system for computing a path in a processor readable representation of a network that caches data to be used in a pathfinding process. In one embodiment, the system chooses, automatically, an origin in a processor readable representation of a network without the pathfinding computation being requested. A preliminary pathfinding exploration is commenced and sets (or records) of data are loaded, as needed, into a processor reada

Affiliated with

Also associated with

Rating

Caching for pathfinding computation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Caching for pathfinding computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Caching for pathfinding computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2836051