Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-10-23
2002-10-29
Corrielus, Jean M. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C701S201000, C701S206000, C701S208000, C701S214000
Reexamination Certificate
active
06473770
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a system and method for facilitating access to and use of geographic data used with a navigation application program that provides navigating features and functions to an end-user, and more particularly, the present invention relates to a geographic database that includes geographic data of different types, each type of which is tailored to support one or more of the navigation functions and which operates with another of the different types, thereby facilitating certain navigation functions and enhancing performance.
Computer-based navigation application programs are available that provide end-users (such as drivers of vehicles in which the navigation systems are installed) with various navigating functions and features. For example, some navigation application programs are able to determine an optimum route to travel by roads between locations. Using input from an end-user, and optionally from equipment that can determine one's physical location (such as a GPS system), a navigation application program can examine various routes between two locations to determine an optimum route to travel from a starting location to a destination location in a geographic region. The navigation application program may then provide the end-user with information about the optimum route in the form of instructions that identify the maneuvers required to be taken by the end-user to travel from the starting location to the destination location. If the navigation system is located in an automobile, the instructions may take the form of audio instructions that are provided along the way as the end-user is traveling the route. Some navigation application programs are able to show detailed maps on computer displays outlining routes to destinations, the types of maneuvers to be taken at various locations along the routes, locations of certain types of features, and so on.
In order to provide these and other navigating functions, the navigation application program uses one or more detailed databases that include data which represent physical features in a geographic region. The detailed database may include data representing the roads and intersections in a geographic region and also may include information about the roads and intersections in a geographic region, such as turn restrictions at intersections, speed limits along the roads, street names of the various roads, address ranges along the various roads, and so on.
One difficulty in providing geographic data for use by a navigation application program relates to the efficient utilization of the available computer resources of the navigation system on which the navigation application program is run. Computer-based navigation application programs are provided on various platforms including some with relatively limited computer hardware resources. For example, navigation systems may be located in vehicles or may be hand-held. These types of navigation systems typically have relatively limited computer resources, such as limited memory and relatively slow I/O In order to provide a high a level of functionality in such systems, it is required that the available computer resources be used efficiently.
Given the relatively large size of the geographic database necessary to provide a desired level of navigating functionality to the end-user, it is accepted that all the data records for an entire geographic region cannot be loaded into the memory of the navigation system at the same time. This is especially true for navigation system platforms with limited resources, such as systems installed in vehicles or hand-held systems. Due to the limited memory resources of these navigation systems, it is necessary to load geographic data as needed from a storage medium, such as a CD-ROM disk, into the memory of the navigation system for use by the navigation application program. Unfortunately, as mentioned above, in these types of systems, I/O access from a storage medium may also be relatively slow. Thus, the relatively limited memory resources combined with the relatively slow I/O can limit the performance of some types of navigation systems, resulting in slow response. Aside from being undesirable, slow response in a navigation system may render the system useless for its intended purpose in certain circumstances. For example, if the navigation system is installed in a vehicle, the driver may require information from the navigation system about a desired route in a matter of seconds in order to utilize the information while driving. If the navigation system requires more than several seconds to calculate a route, the driver may have II moved beyond the point at which the routing information provided by the navigation system is relevant. Therefore, it is important that navigation systems operate efficiently in order to provide navigating information relatively quickly.
Navigation application programs may also be run on computer platforms that have in general greater memory resources and faster I/O, such as personal computers or networks. Although these systems may have more and faster resources, the considerations related to the efficient use of geographic data still apply, but on a larger scale. With these types of systems, even greater functionality can be provided if the limitations imposed by memory size and I/O are minimized.
Techniques have been devised or implemented to improve navigation system performance by organizing, structuring, or arranging the geographic database or the data in the database in particular ways. Because a navigation system uses geographic data in certain known and expected ways to perform known functions, the geographic data can be organized, structured, or arranged in a manner that facilitates their use in these known ways by the navigation system.
One technique that can be implemented in a geographic database to enhance operation of the navigation system is to provide separate collections or subsets of the geographic data for use by each of the separate functions in the navigation application program. For instance, the route calculation function normally uses only a portion of all the information in the geographic database that is associated with a segment of a road. When the route calculation function is being run, it may require information such as the speed along a road segment, turn restrictions from one road segment to another, and so on. However, the route calculation function does not necessarily require the name of the road to calculate a route. Similarly, when using the map display function, some of the information associated with a road segment, such as the speed limits or turn restrictions, is not required. Instead, when the map display function is run, it uses only a portion of the information associated with the road segment, such as the shapes and locations of roads, and possibly the names of the roads. Even further, when the route guidance function is being run, some of the information associated with a segment of a road, such as the speed and turn restrictions, is not required. Instead, when the route guidance function is being run, it uses information that includes the name of the road represented by the road segment record, the address range along the road segment, any signs along the road segment, and so on. Although there may be some overlap as to the types of information used by the various navigation functions, some of the data used by any one of these navigation functions is not used by another of the functions. If all the information relating to each road segment were associated with a single data entry in a single database, each data entity record would be relatively large. Thus, whenever any one of the navigation functions accessed an entity record, it would have to read into memory a significant amount of information much of which would not be needed by the navigation function. Moreover, when reading the data entity from disk, relatively few data entities could be read at a time since each data entity would be relatively large.
In order to
Ashby Richard A.
Bouzide Paul M.
Doddapaneni Srinivasa
Fernekes Robert P.
Friederich Matthew
Corrielus Jean M.
Kaplan Lawrence M.
Kozak Frank J.
Navigation Technologies Corp.
Shutter Jon D.
LandOfFree
Segment aggregation and interleaving of data types in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Segment aggregation and interleaving of data types in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Segment aggregation and interleaving of data types in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2983193