Navigation system with distributed computing architecture
Abstract
This record has no abstract on file.
Term
Projected expiry 26 March 2028.
- Priority
- Filed
- Granted
- Today
- Projected expiry
6 claims: 2 independent, 4 dependent
- 1地域の中の地理的特徴を表す地理的データの保存庫を含む サーバを作動させる方法であって、 前記地域は、より小さな複数の地理的区域に分割されており、 クライアント・コンピュータから、地理的データを求める要求を受信するステップ、 サーバに記憶される、どの事前に計算された地理的データの集合を、前記要求に応答するためにクライアント・コンピュータに送るかを決定するステップであって、 前記保存庫内の地理的データの第1の集合が、事前に計算された、第1の均等のバイト・サイズの地理的データの集合を含み、前記保存庫内の地理的データの第2の集合が、事前に計算された、第2の均等のバイト・サイズの地理的データの集合を含み、 前記事前に計算された地理的データの集合の各々が、 前記 地域の中に位置する 複数の 地理的区域の 各々の 中の地理的特徴を表す全てのデータ・レコードを含 む、前記ステップ 、及び、 前記クライアント・コンピュータに送ると決定された、前記事前に計算された地理的データの集合を発送するステップ、を含む方法。
- 2起点と目的地の間のルートを決定するステップ、及び、 前記クライアント・コンピュータへ、前記ルートを指示するデータを発送するステップ、を更に含む、請求項1に記載の方法。
- 3前記ルートを決定するステップが、 前記地理的区域のどれが、前記ルートに沿って配置されるかを特定するステップ、及び、 前記ルートに沿って配置されるものとして特定された地理的区域を表す、前記事前に計算された地理的データの集合を発送することを決定するステップ、を含む、請求項2に記載の方法。
- 4前記事前に計算された地理的データの集合内に包含されるデータによって表される道に対する、前記クライアント・コンピュータの位置を決定するステップ、 前記クライアント・コンピュータの位置を用いて、ビジネス、及び/又は、人に関する情報を見つけ出すステップ、及び、 ビジネス、及び/又は、人に関する情報を指示するデータを、前記クライアント・コンピュータに発送するステップ、を更に含む、請求項1に記載の方法。
- 5アプリケーションを、前記クライアント・コンピュータにダウンロードするステップを更に含む、請求項1に記載の方法。
- 6前記アプリケーションが、アプレット、プラグイン、メモリ・マネジャ・アプリケーション、及び、前記クライアント・コンピュータの上に既にインストールされた、アプリケーションに対する更新、のうちの1つである、請求項 5 に記載の方法。
Independent claims6
100 paragraphs, as filed
The present invention relates to a system that provides navigation-related services and data to end users across regions. More specifically, the present invention includes a centrally located server, which provides a geographic database associated thereto. Of end users who have and are located across service areas<u style="single">Computer</u>Regarding systems that have come to provide navigation-related services and data.
The navigation system provides various useful features such as calculating a route to a desired destination, providing guidance according to the calculated route, displaying a map, and the like. There are various computer architectures for navigation systems that deliver navigation-related and map-related features. One form of architecture for a navigation system is a local navigation system device owned by an end user (such as a vehicle driver). These end-user local navigation system devices obtain geographic data from remote geographic databases. Remotely located geographic databases possess a relatively large amount of geographic data. The server associated with the remotely located geographic database processes requests for navigation-related or map-related data from the end user's local navigation system equipment. When an end user's local navigation system unit requests data, the server accesses the associated geographic database to obtain the data needed to meet the request, and then the end user requesting this data. Send to the local navigation system device.
This type of navigation system architecture offers several advantages. One of the benefits is related to providing updated geographic data. The geographic data used in the navigation system needs to be continuously updated. For example, new roads are created, roads are closed due to road construction, detours are set up, new stores are opened, speed limits are changed, and new turn limits are set at intersections. Or the name of the street may be changed. This type of change can affect movement through the region. Therefore, the geographic data used in the navigation system should be updated regularly to accurately reflect the changes in the displayed geographic features. The computer architecture in which individual local navigation system devices obtain geographic data from a single geographic database provides an advantage in updating geographic data. In a computer architecture where individual local navigation system units obtain data from a single geographic database associated with a central server, the need for updates arises only in the central database.
Navigation system architectures, where individual local navigation system devices now obtain data from a single geographic database associated with a central server, have associated advantages, but there are additional considerations. is there. One of the considerations pertains to providing data to a variety of different computer platforms used by end users. The central server preferably supports a wide variety of different types of end-user computer platforms. These different end-user computer platforms may have different amounts of memory, different processing speeds, different operating systems, and other different resources. Some of these different types of end-user computer platforms may include multipurpose arithmetic units that run navigation applications. Other end-user computer platforms may include dedicated equipment such as in-vehicle navigation systems. Some of these different end-user computer platforms can provide both audio and visible information to the end user, while other end-user computer platforms provide audio only or video only. .. It is preferred that each of the computer platforms receive geographic data suitable for the resources of that platform. is this,<u style="single">Computer</u>It involves transmitting sufficient data to make use of the available resources of the platform in a meaningful way, but not transmitting data that is not available on the platform.
<p> Therefore, the server is a different type of end user.<u style="single">Computer</u>There is a need for improvement to be able to provide navigation-related services and data in order to respond to this.</p><p> In addition, the data is from the central server to the end user<u style="single">Computer</u>In the navigation system architecture sent to, the data is sent to the server and the end user.<u style="single">Computer</u>There is a need for improvement to ensure that both are effectively managed.</p>
<p> To meet these and other objectives, the present invention provides navigation-related services to end-users.<u style="single">Computer</u>Consists of systems and methods for providing to. The server manages downloadable geographic data, which is pre-computed corresponding to certain subdivisions that divide the entire service area by the server.<u style="single">Set of data</u>Is systematized into. The server is a pre-computed and selected geographic data<u style="single">Set of data</u>The end user's<u style="single">Computer</u>Respond to requests for navigation services and data by sending to. End user<u style="single">Computer</u>Each of them received from the server<u style="single">Set of data</u>Is stored in the memory cache. End user<u style="single">Computer</u>Is<u style="single">Set of data</u>Use the data in to provide navigation-related features locally.</p>
I.<u style="single">Overview of distributed navigation system</u> Figure 1 shows Region 100. Region 100 can correspond to either a metropolitan or rural area, a state, a country or a combination thereof, or any other area of similar size. This area 100 has a road network 104.
The navigation system 110 serves end users within the region 100 (eg, vehicle drivers and passengers and others). This navigation system 110 is used by end users to obtain navigation-related and map-related services for Region 100. Navigation-related and map-related services include route calculation and guidance, personal and corporate search services (eg Electronic Yellow and White Pages), maps, search for points of interest, destination selection and more. Includes information about traveling along.
The navigation system 110 is a combination of hardware, software and data. The navigation system 110 includes remote components (eg, centrally located hardware, software or data away from the end user) and local components (eg, hardware, software or data physically located with each end user). including.
Among the remote components of the navigation system 110 is the navigation service server 120. Related to the navigation service server 120 are the working geographic database 122 and the downloadable geographic data storage (ie, repository) 124. The navigation service server 120, the working geographic database 122, and the downloadable geographic data storage device 124 are managed and operated by the navigation service provider 128.
Local components of the navigation system 110 are various computer platforms 130 that are activated by the end user to request and obtain navigation-related and map-related features and geographic data from the navigation service provider 128. Is included. These various computer platforms 130 ("End User"<u style="single">Computer</u>Or "customer's<u style="single">Computer</u>(Also known as) has the appropriate hardware and software to access the navigation service provider 128 via the data network 170, vehicles 134, personal computers 140, personal organizers (eg PDAs, PalmPilot). A (registered trademark) type device) 150, a mobile phone 160, or a navigation system device 132 mounted on another type of computer can be included.
The data network 170 may use any suitable technology and / or protocol currently available, as well as any technology and / or protocol that will be available in the future. For example, the data network can use WAP, TCP / IP, and more. More than one protocol can be used for the data network 170, with appropriate transformations.
The data network 170 can be part of the Internet or can be connected to the Internet.
The network 170 can include a wireless portion 172. The wireless portion 172 of the data network 170 is the end user's mobile<u style="single">Computer</u>Allow bidirectional communication between 130 and service provider 128. The radio portion 172 can be implemented in a cellular fashion, PCS, satellite, FM, radio, or any form of technology that will be developed in the future. The radio portion 172 may include one or more transmitters 174 such as transponder towers, antenna towers, FM towers, satellites and other suitable means. The transmitter 174 has a suitable communication link 176 with the network 170 and / or the service provider 128. The link 176 can be a terrestrial line or wireless. The transmitter 174 is a mobile service provider 128 and end user.<u style="single">Computer</u>Includes suitable technology to enable two-way communication with 130.
One of the features of the navigation system 110 in Figure 1 is the different types of end-users.<u style="single">Computer</u>It corresponds to 130. The navigation system 110 in Figure 1 has a different format.<u style="single">Computer</u>Allow end users with 130 to receive navigation services from the navigation service provider 128 and to obtain and use geographic data from the navigation service provider 128.
II.<u style="single">Navigation service server</u> A.<u style="single">Overview</u> FIG. 2 is a block diagram showing some of the components of Navigation Service Provider 128. Navigation service server 120 of navigation service provider 128 includes server application 200. One of the server applications 200 is the subscriber service application 204. The end user is required to be a subscriber in order to use some or all of the other services provided by Navigation Service Provider 128. The subscriber service application 204 provides a service corresponding to this function. Some of our subscriber services include registration, payment, renewal, subscriber identification, targeted advertising and more. The subscriber service application 204 manages and uses the subscriber database 208, which holds different types of information about different subscribers.
In addition to the server application 200, there is a communication application 212. Communication application 212 interfaces with a data network (170 in Figure 1) to send and receive messages to and from end users. The communication application 212 also maintains a communication session with the end user.
Server application 200 includes navigation-related application 216. The navigation-related application 216 uses the working geographic database 122 associated with the navigation service server 120 to provide a variety of different types of navigation-related services. One of the navigation-related applications 216 is the route calculation application 220. Given the data that identifies the location of the starting point and the destination, the route calculation application 220 calculates the route between the starting point and the destination. The route calculation application 220 can use any of a variety of means or algorithms that serve this purpose. A method of calculating the route is disclosed in US Pat. No. 6,192,314, the entire disclosure of which is incorporated herein by reference. For example, the route calculation method is A.<sup>*</sup>It can include either an algorithm or a Dixtra algorithm. (The method disclosed in the above-mentioned patent describes only some of the methods capable of calculating the route, but the content claimed here is any of the specific route calculation methods. Any suitable route calculation method known or will be developed in the future can be used.)
Regardless of the method used, the route calculation application 220 outputs a list in the form of a list that identifies a continuous sequence of paths (or these compartments) that form a legitimate answer route between the origin and the destination. give. "Legal answer routes" are subject to confirmed traffic regulations such as one-way streets, turn restrictions and more. The method used in the route calculation application 220 can be designed so that the answer route is optimized to meet one or more predetermined criteria. Such criteria can include the shortest travel time, the shortest distance, the minimum number of turns, and so on. If the method used in the route calculation application 220 is designed to find an answer route optimized for one or more criteria, then the answer route is also ideally one or more of these. Meet more criteria.
In addition to the navigation-related application 216, there is a corporate and personal search application 224. Corporate and personal search application 224 includes features in yellow and white page format. The business and personal search application 224 finds the location or address of a particular business or individual, or finds other information about a particular business or individual. The Enterprise and Personal Search application 224 also provides to search for the location or address of a category of enterprise or individual based on various criteria. For example, the corporate and personal search application 224 is a restaurant in a particular ethnic style (eg Chinese) or chain store (eg McDonald's) within a certain distance (eg 5 miles) from a particular location (eg end user location). Provides a search for all of. The enterprise and personal search application 224 can assist the end user in finding an interested enterprise, individual or location that can be used as a destination, and then the route calculation application 220 provides the answer route to that point. You can ask.
To provide navigation-related features, the routing application 220 and the search application 224 use data from the working geographic database 122. The working geography database 122 contains data representing roads and intersections in an area (100 in Figure 1), as well as turn limits at intersections, speed limits along roads, street names on various roads, and address ranges along roads. It also contains information about roads and intersections represented as others. The working geography database 122 also holds information and other information about points of interest and companies. The working geography database 122 can be systematized to facilitate the execution of navigation-related functions. Methods for organizing geographic databases to improve the performance of certain navigation-related features are described in US Pat. No. 5,974,419, US Pat. No. 5,968,109, and US Pat. No. 5,953,722. Incorporated here by citation.
The other navigation-related application 216 in the navigation service server 120 is the geographic data providing application 228. The geographic data providing application 228 provides geographic data to the end user.<u style="single">Computer</u>Manage downloading to 130. According to one embodiment of the navigation system (110 in Figure 1), certain navigation-related functions are performed remotely on the navigation service server 120 towards the end user, while other navigation-related functions ,end user·<u style="single">Computer</u>Runs locally on the 130 towards the end user. For example, according to one embodiment, the route calculation is performed on the navigation service server 120 in order to utilize the latest traffic information. Directions provide information in the way each end user prefers, and each end user<u style="single">Computer</u>For each end user to accommodate each of the 130 resources<u style="single">Computer</u>Run locally on 130.
End user<u style="single">Computer</u>The navigation application above is for the end user<u style="single">Computer</u>Geographical data can be requested to perform certain navigation-related functions locally on. In this embodiment, the end user<u style="single">Computer</u>Each of them obtains the geographic data needed to locally perform certain navigation-related functions from the navigation service server 120. Navigation service server 120 is the end user<u style="single">Computer</u>The data to be transmitted to 130 is obtained from the downloadable geodata storage device 124. The geographic data providing application 228 of the navigation server 120 is an end user from the downloadable geographic data storage device 124<u style="single">Computer</u>Manage the supply of geographic data up to 130.
The geographic data providing application 228 performs several functions. One of the functions performed by the geographic data providing application 228 is from the downloadable geographic data storage device 124 to the end user.<u style="single">Computer</u>Is to determine the appropriate data to send to. This decision can take into account several factors. According to one embodiment, the end user<u style="single">Computer</u>Identify a collection of geographic data. Navigation service provider 128 can store different collections 232 of geographic data in downloadable geographic data storage device 124. Each of the individual collections 232 is an individual representation of the entire region (100 in Figure 1). The configuration of these different collections 232 will be described in more detail later. Once it is determined which data to send from the collection 232 of the geographic data, the geodata providing application 228 selects a specific data portion from the collection 232 and the selected data, as described in more detail later. Part of the end user<u style="single">Computer</u>Send to.
According to another embodiment, the geographic data providing application 228 may refer to the subscriber database 208 to determine a suitable collection of geographic data 232 to select the data to send to a particular end user. it can. The subscriber database 208 can manage information that identifies a collection of geographic data from which the data to be sent to each end user is selected. According to yet another embodiment, the geographic data providing application 228 can determine a collection of geographic data suitable for selecting data to be sent to a particular end user by other means.
From the downloadable geographic data storage device 124, to the end user<u style="single">Computer</u>The geographic data to be sent to is selected After determining the collection 232, a specific portion of the geographic data to be sent is selected. To perform this function, the geographic data providing application 228 is (1) end-user<u style="single">Computer</u>Take into account the location of, (2) where the end-user platform goes, and (3) other factors. If the end user follows the route calculated by the route calculation application 220, the geographic data providing application 228 selects data representing an area along this route. The area along the route can be called a "course map". The scale of the course map is determined by the geographic data providing application 228. This decision can take into account the end user's specification of the course map scale. Alternatively, the geographic data providing application 228 can determine a suitable course map scale based on stored information about end-user preferences and computer platform resources. This stored information is managed in the subscriber database 208.
B.<u style="single">Downloadable geographic data</u> As mentioned above, the geographic data providing application 228 transfers which data to the end user.<u style="single">Computer</u>Decide if you want to send to 130. Geographic data providing application 228 is an end user<u style="single">Computer</u>The data to be transmitted to is obtained from the downloadable geographic data storage device 124 managed by the navigation service server 120. From the navigation service server 120 to the end user<u style="single">Computer</u>To facilitate downloading data to 130, the data is systematized into one or more predetermined collections 232. In addition, each of the data collections 232 in the downloadable geographic data storage 124 is divided into multiple groups (ie, ""<u style="single">Set of data</u>") Is systematized. In one embodiment, each<u style="single">Set of data</u>The data stored in is spatially determined, i.e., each representing a geographic feature.<u style="single">Set of data</u>The data in are close to each other. More specifically, each<u style="single">Set of data</u>The data stored in represents the geographic features owned by the distinct distinctes of the multiple distinct geographic divisions that divide the entire region represented (100 in Figure 1).
As mentioned above, according to this embodiment, the downloadable geographic data storage device 124 includes a variety of different collections 232. Each of these collections 232 consists of a separate display of 100 for all regions. Each of these collections 232 has multiple<u style="single">Set of data</u>Is systematized into.
3 and 4 show how the data stored in each of the downloadable geographic data storage 124 collections 232 is systematized by one embodiment. FIG. 3 shows a map 300 of the area 100 already shown in FIG. In FIG. 3, the grid 304 is superimposed on the map 300 representing the area 100. The grid 304 is composed of grid lines 308. Grid line 308 divides the represented area 100 into multiple areas 312. In this embodiment, the area 312 is rectangular, however, in another embodiment the area 312 can have a different shape. Grid line 308 of grid 304 represents the boundary of area 312. These areas 312 can be of different sizes as shown in FIG. Alternatively, the areas 312 can all be the same size. Whether the size of the area 312 and whether the size of the area 312 are all the same means that the data representing the geographical features contained in these geographical divisions are obtained.<u style="single">Set of data</u>Determined by the procedure used to systematize. Similarly, the location of the boundaries of area 312 provides data representing the geographic features contained in these geographic divisions.<u style="single">Set of data</u>Determined by the procedure used to systematize.<u style="single">Set of data</u>A method of determining the boundaries of an area to generate is described in US Pat. No. 5,974,419, the entire disclosure of which is incorporated herein by reference.
each<u style="single">Set of data</u>In the generation of 312, the individual data records 336 representing the geographic features contained in each of the separate areas 312 are separate data records.<u style="single">Set of data</u>Collected together in 320 (or grouping). That is, of the data (of each collection 232)<u style="single">Set of data</u>Each of the 320s contains all data records 336 representing the geographic features contained in the corresponding geographic division 312. Therefore, (all in collection 232)<u style="single">Set of data</u>All geographic divisions 312 (corresponding to 320) make up 100 of the entire region. That is, of the data<u style="single">Set of data</u>Each of the 320 is a road, an intersection, a point of interest and said<u style="single">Set of data</u>Can include multiple data records 336 representing other features within the corresponding geographic segment 312.
According to one embodiment, all in each collection 232<u style="single">Set of data</u>320 is uniform<u style="single">Set of data</u>-Has a size. For example, of data<u style="single">Set of data</u>Each of the 320s can have 1K, 2K, 4K, 8K, 16K, 32K and other sizes. Each of the collection 232<u style="single">Set of data</u>· The size is for the end user who will use the data<u style="single">Computer</u>It can be determined based on several factors, including the memory resources of. According to this embodiment, one collection 232<u style="single">Set of data</u>320 is another collection of 232<u style="single">Set of data</u>It can be different in size from 320. For example, one collection 232 is 32K in size.<u style="single">Set of data</u>On the other hand, another collection 232 is 16K in size<u style="single">Set of data</u>Can have.
As shown in FIGS. 3 and 4, each of the collections 232 has a plurality.<u style="single">Set of data</u>Can include 320. Collection 232<u style="single">Set of data</u>Each of the 320s corresponds to a separate one of the geographical divisions 312 located within the entire region 100. In the downloadable data storage device 124, each of the collections 232 and the collections 232<u style="single">Set of data</u>Each of the 320s is pre-calculated. In other words, the determination and generation of each collection 232 and all that make up each collection 232.<u style="single">Set of data</u>The determination and generation of 320 is that any of the data in the downloadable data storage device 124 is of the end user.<u style="single">Computer</u>It will be done before it becomes available for download to any of the 130. This facilitates the decision of which data to send to the end user. The end user is his or her<u style="single">Computer</u>When requesting data for local use in, the navigation service server 120 determines which specific data records the end user needs and which data records to send to the end user. You don't have to judge. Instead, the navigation service server 120 includes all geographic divisions 312 required by the end user and containing data representing all the geographic features in these geographic divisions 312.<u style="single">Set of data</u>Determine if you want to send 320 to the end user. Sent to end user<u style="single">Set of data</u>320 represents a clip or slice of all data representing the region. these<u style="single">Set of data</u>320 contains all of the individual data records needed by the end user. This systematization and processing facilitates computation on the navigation service server 120. The geographic data providing application 228 on the navigation service server 120 is provided by the end user.<u style="single">Set of data</u>Determine if you need any data that corresponds to the defined geographic segment 312 that corresponds to, and if so, correspond to the geographic segment 312.<u style="single">Set of data</u>Send all of to the end user. This systematization and processing also provides a way for end-users to manage memory resources, as described in more detail later.<u style="single">Computer</u>Facilitates the calculation with.
End-users from downloadable data storage device 124, except as described below.<u style="single">Computer</u>When the data is downloaded to, the data is all<u style="single">Set of data</u>It will be downloaded to. This means that all data records 336 representing the geographic features contained in each of the geographic divisions 312 are accessed together as a group. Therefore,<u style="single">Set of data</u>320 is the end user<u style="single">Computer</u>Represents the amount of data records downloaded at the same time for use in. Of the data<u style="single">Set of data</u>Is the end user<u style="single">Computer</u>When sent to<u style="single">Set of data</u>All data records of the end user<u style="single">Computer</u>Available at. In one embodiment<u style="single">Set of data</u>All data records in are end-user<u style="single">Computer</u>-It is stored in the system memory at the same time.
C.<u style="single">A collection of different types of data</u> As mentioned above, the downloadable geographic data storage device 124 contains a different collection 232 of geographic data. These different collections 232 all represent the same region (100 in Figure 1), but can contain different formats of data (ie, separately systematized data). All of these different collections of data 232 are as described above.<u style="single">Set of data</u>Is systematized into. As mentioned above, in the collection<u style="single">Set of data</u>232 is uniform<u style="single">Set of data</u> It is preferable to match the size. However, in one collection 232<u style="single">Set of data</u>Uniform size in another collection 232<u style="single">Set of data</u>It may be different from the uniform size of. Some of the contents of collection 232 are described below.
(1)<u style="single">First collection of downloadable geographic data</u> Figure 5 shows the geographic data 336 in one of collections 232 (1).<u style="single">Set of data</u>It is a schematic used to explain the content in one of 320.<u style="single">Set of data</u>Data 336 in 320 corresponds to one of the geographical divisions 312 (1). In this embodiment<u style="single">Set of data</u>320 contains all data 336 representing all the features contained in geographic division 312 (1). As an example,<u style="single">Set of data</u>320 is the<u style="single">Set of data</u>Contains data representing all roads in geographical division 312 (1) corresponding to 320. Each road is represented as a series of connected sections, which correspond to a road section between adjacent intersections along the road or a road section between an intersection and a road dead end. In this embodiment, each road section is represented by a separate data entity (or data record). Each data record representing a road section is a displayed road such as the speed limit (or speed range) of the road section, the functional classification (ie rank) of the road section, the number of lanes along the road section, and so on. Includes (or shows) data about the interval.
The data record representing the road section also includes data indicating the location of the road section. In one embodiment, this information includes a description of a node record representing the end point of a road section. Related to node records is data that indicates the location (eg, latitude, longitude, and altitude, if necessary) of the end point (ie, node) of the road section. For non-straight road sections, additional data is included to show the shape of the road section. In one embodiment, shape point data is used for this purpose. Shape points identify the location of points along the road section between the end points of the road section (eg, latitude, longitude, and altitude if necessary). By using one or more shape points, it is possible to represent the shape of a road section other than a straight line.
Records representing road sections also include data showing the names of one or more road sections. In one embodiment, this information includes a description of one or more name records. In this embodiment, the road name record and other named geographic features are the same.<u style="single">Set of data</u>include.
In the embodiment shown in FIG.<u style="single">Set of data</u>320 also contains data for points of interest. The point of interest data contains information about the point of interest. Points of interest include businesses, public facilities and others. The point of interest data includes information about the point of interest displayed, such as name, type (eg, hotel, restaurant, chain store, museum, police station, etc.), address, phone number, and so on. In this embodiment, the data record of the point of interest included in the geographic segment is the same data, along with road section data, node data, and name data.<u style="single">Set of data</u>include.
In the data collection 232 (1) in Figure 5, all<u style="single">Set of data</u>Is 16K in size (but any other data size can be used). Figure 6 shows another data collection 232 (2). In FIG. 6, collection 232 (2) contains the same type of data, such as road section records, node records, name records, point records of interest, and more.<u style="single">Set of data</u>Divided into 320. However, it produces collection 232 (2) in Figure 6.<u style="single">Set of data</u>320 is in collection 232 (1) in Figure 5.<u style="single">Set of data</u>Has a different size. In collection 232 (2) of Figure 6<u style="single">Set of data</u>Are each 32K in size. Figure 6<u style="single">Set of data</u>Each of the 320s is shown in Figure 5.<u style="single">Set of data</u>Each contains more data than each<u style="single">Set of data</u>Can represent a wider geographical division. Therefore, as shown in FIG.<u style="single">Set of data</u>The geographical division 312 (2) corresponding to 320 is shown in Fig. 5.<u style="single">Set of data</u>It is larger than the geographical division 312 (1) corresponding to 320.
Figure 7 shows another data collection 232 (3). The data collection 232 (3) shown in FIG. 7 is the same type of data as the collections 232 (1) and 232 (2) shown in FIGS. 5 and 6, respectively, such as road section records and node records. Includes name records, point records of interest, and more. In addition, each in the data collection 232 (3) of Figure 7.<u style="single">Set of data</u>Also includes pronunciation data. The pronunciation data corresponds to the geographic features and / or the names of points of interest in the displayed geographic divisions. Pronunciation data is from the end user<u style="single">Computer</u>To be able to play these names audibly using 130 suitable hardware and software<u style="single">Set of data</u>In 320, a phonetic representation corresponding to the geographical feature and / or the name of the point of interest in the represented geographic division is included. In the data collection 232 (3) of Figure 7, each<u style="single">Set of data</u>The 320 contains 64K of data, but other data sizes can be used.
FIG. 8 shows three additional data collections, 232 (4) (1), 232 (4) (2), and 232 (4) (3). In this embodiment, each of collections 232 (4) (1), 232 (4) (2), and 232 (4) (3) contains only some type (or attribute) of data. For example, collection 232 (4) (1) contains only route data, such as interval records and node records. Collection 232 (4) (2) contains only name records. Collection 232 (4) (3) contains only point records of interest. Each of these collections 232 (4) (1), 232 (4) (2), and 232 (4) (3) corresponds to a separate geographic division 312.<u style="single">Set of data</u>Systematized to 320. Therefore, in collection 232 (4) (1)<u style="single">Set of data</u>320 includes section records and node records representing roads and intersections in geographical division 312 (4). Collection 232 (4) (2) contains name records representing the names of geographic features and / or points of interest in geographic division 312 (4). Collection 232 (4) (3) contains a point of interest record that represents the location of the point of interest in geographic division 312 (4). In the data collections 232 (4) (1), 232 (4) (2), and 232 (4) (3) in Figure 8, respectively.<u style="single">Set of data</u>The 320 contains 16K data (although other uniform data sizes can be used).
The different data collection embodiments shown in FIGS. 5-8 are some of the data collections that can be stored in a downloadable geographic data storage device (124 in FIG. 2) on the navigation service server 120. Represents only different forms of. Downloadable geographic data storage device 124 comes in different sizes<u style="single">Set of data</u>Can include a collection of data that holds. In addition, the downloadable geodata storage devices 124 were systematized separately from each other.<u style="single">Set of data</u>Can include data collections that hold. For example, the downloadable geographic data storage device 124 is for data systematized in alphabetical order or by administrative system (eg, city, county, state and country).<u style="single">Set of data</u>Can include collections that own.
III.<u style="single">End user computer</u> A.<u style="single">Overview</u> As mentioned above, each end user<u style="single">Computer</u>Use (130 in Figure 1) to get the data from the navigation service server 120. Also, as mentioned above, the data obtained from the navigation service server 120 is used by the end user.<u style="single">Computer</u>Some navigation related functions are performed locally above. Of different end users<u style="single">Computer</u>Has different hardware and software, so the end user<u style="single">Computer</u>The navigation-related functions performed above can be varied for each platform of the end user. Therefore, in the next section, the end user<u style="single">Computer</u>The configuration of is described. For all end users<u style="single">Computer</u>However, it does not always provide all the functions described below, and some end users.<u style="single">Computer</u>It should be understood that can provide additional or other functionality.
Of different end users<u style="single">Computer</u>May have different hardware and software resources, but all end users<u style="single">Computer</u>Receives data from the navigation service server (120 in Figure 1). end user·<u style="single">Computer</u>Some or all of them receive geographic data from downloadable geographic data storage device 124 on the navigation service server 120. End users receiving geographic data from downloadable geographic data storage device 124<u style="single">Computer</u>130 is the data obtained from the navigation service server 120 using the memory management features described below.<u style="single">Set of data</u>Can be processed.
B.<u style="single">End-user computer components</u> Figure 9 shows the end user<u style="single">Computer</u>It is a block diagram of several components in one of 130. End user<u style="single">Computer</u>130 includes communication system 400. End user<u style="single">Computer</u>The communication system 400 in 130 includes the hardware and software components required to send and receive messages to and from the navigation server (120 in Figure 1) over the data network 170. Communication system 400 is an end-user<u style="single">Computer</u>Interface with other components in 130.
End user<u style="single">Computer</u>The 130 also includes a user interface 410. The user interface 410 allows the end user to<u style="single">Computer</u>Enter the information in 130 for the end user<u style="single">Computer</u>Be able to receive information from 130. User interface 410 includes hardware and software components. For example, user interface 410 provides a display, microphone, speaker, keypad, or information.<u style="single">Computer</u>Can include other types of means for inputting to and outputting information from it. User interface 410 includes assistive software capable of providing menus, prompts, audio and more. User interface 410 is an end-user<u style="single">Computer</u>Interface with other components in 130.
End user<u style="single">Computer</u>130 includes navigation-related application 420. Navigation-related application 420 uses geographic data obtained from navigation server 120 to provide a variety of different types of navigation-related services. One of the navigation-related applications 420 is the positioning application 420 (1). The positioning application 420 (1) uses the geographic data obtained from the navigation server 120 to represent the road network of the end user.<u style="single">Computer</u>Find the position of 130. Positioning application 420 (1) is also end-user<u style="single">Computer</u>Data can also be obtained from positioning system 430, which is part of 130. Positioning system 430 uses GPS, speculative navigation, or a combination of these or other technologies to provide end-users.<u style="single">Computer</u>The position of 130 can be obtained. The method of positioning is disclosed in US Pat. No. 6,192,312, the entire disclosure of which is incorporated herein by reference. Positioning application 420 (1) is needed, i.e., but not all end-users.<u style="single">Computer</u>Can provide positioning or assist in positioning.
End user<u style="single">Computer</u>In addition to the navigation application 420 in, there is routing 420 (2). The routing application 420 (2) uses the data from the navigation server 120 to instruct the end user to travel to the desired destination.
Methods for route guidance using geographic data are described in US Pat. No. 6,199,013, the entire disclosure of which is incorporated herein by reference.
End user<u style="single">Computer</u>In addition to the navigation application 420 in, there is a map display 420 (3). Map display 420 (3) uses data from the navigation service server 120 to provide end-user information.<u style="single">Computer</u>Provides a realistic map on the display screen of the user interface 410 in. This map is for end users<u style="single">Computer</u>It is possible to indicate the division around the position of, the division along the route followed by the end user, the division around the position specified by the end user, or other specified division. Methods for screen display using geographic data are disclosed in US Pat. No. 6,092,076 and US Pat. No. 6,163,749, the entire disclosure of which is incorporated herein by reference.
End user<u style="single">Computer</u>In addition to the navigation application 420 above, there is a reroute application 420 (4). The rerouting application 420 (4) is used to receive guidance so that the end user can follow when the end user deviates from the route to the destination. The rerouting application 420 (4) uses the data from the navigation server 120 to calculate a new route to the destination or a route to return to the original route. Route recalculation application 420 (4) can perform route calculations using the same methods as described in US Pat. No. 6,129,314, the entire disclosure of which is incorporated herein by reference.
End user<u style="single">Computer</u>In addition to the navigation application 420 above, there is a query application 420 (5). The query application 420 (5) is used to generate a query (ie, request for information) to the navigation application (216 in Figure 2) on the navigation service server 120. The query can be a request to calculate the route using the route calculation application 220, or a company, individual using a search service 224 or any other service or application provided by the navigation service server 120. Or it can be a request for information about a point of interest. The query application 420 (5) sends a message to the navigation service server 120, waits for a response, receives the response, and then manages to use the requested data locally, eg, in the local application 420. ..
End user<u style="single">Computer</u>In addition to the navigation application 420 above, there is a reference application 420 (6) at the point of interest. Point of Interest Application 420 (6) uses a point of interest reference (ie, search). Data describing the points of interest are stored on the navigation service server 120 or locally.
C.<u style="single">End-user computer memory management capabilities</u> End user<u style="single">Computer</u>130 includes the memory management application 500. Memory management application 500 is an end user<u style="single">Computer</u>Manage 130 memory resources. A function performed by the memory management application 500 is the management of geographic data received from the navigation server 120. As part of this feature, the memory management application 500 is available to the end user from the downloadable geographic data storage device 124 of the navigation service server 120<u style="single">Computer</u>Of the geographic data received in<u style="single">Set of data</u>Manage 320. Of geographic data<u style="single">Set of data</u>The method of managing the memory in memory is disclosed in US Pat. No. 6,073,076 and US Pat. No. 6,047,280, the entire disclosure of which is incorporated herein by reference.
Referring to FIG. 9, the memory management application 500 is used by the navigation-related application 420 for end-user use.<u style="single">Computer</u>Reserved some 504 of 130 memory 506, and more<u style="single">Cache for a set of data</u>Reserve another part 514 for use as a 520. Memory management application 500 is an end user<u style="single">Computer</u>The size of these parts 504 and 514 can be determined at the time of initialization of 130 or at any time thereafter. This decision can take into account the total amount of available memory installed. In addition, the memory management application 500 can determine the reallocable portion 528 of memory 506. Some or all of this reassignable part 528 may be used or used for the navigation application 420.<u style="single">Cache for a set of data</u>Can be used for 520. Use of reallocable portion 528 is end-user<u style="single">Computer</u>At the time of execution of 130, the memory management application 500 determines based on the end user's request.
End user<u style="single">Computer</u>During the operation of 130, the end user<u style="single">Computer</u>Navigation-related application 420 in 130 downloaded from navigation service server 120<u style="single">Set of data</u>Use the data contained in 320. End user<u style="single">Computer</u>To improve the performance of 130, end user<u style="single">Computer</u>A cache 520 is provided in the memory 506 of 130. Cache 520, in particular, has a lot of geographic data downloaded from Navigation Services Server 120.<u style="single">Set of data</u>Used to store 320. Geographical data in cache 520<u style="single">Set of data</u>By saving many<u style="single">Set of data</u>By storing in memory in a usable state, the end user<u style="single">Computer</u>Supports navigation-related application 420 in 130.<u style="single">Set of data</u>It is possible to keep the memory in a usable state from the navigation service server 120.<u style="single">Set of data</u>The relatively large delay associated with obtaining is avoided.<u style="single">Cache for a set of data</u>The 520 also has geographic data that is expected to require navigation capabilities soon.<u style="single">Set of data</u>Can also be used to store. Like above-mentioned,<u style="single">Cache for a set of data</u>The configuration and operation of the 520 is performed by the memory management application 500.
<u style="single">Cache for a set of data</u>The size of is based on various factors.<u style="single">Cache for a set of data</u>One of the factors that influences the size of<u style="single">Set of data</u>Is the size of.<u style="single">Set of data</u>Against the size of<u style="single">Cache for a set of data</u>Depending on the size of<u style="single">Cache for a set of data</u>How much<u style="single">Set of data</u>Is decided whether it can be secured. As mentioned above, in some embodiments<u style="single">Set of data</u>Is stored in the downloadable geographic data storage device 124 of the navigation service server 120 in standard sizes such as 2K, 4K, 8K, 16K, 32K and others. Therefore, the end user<u style="single">Computer</u>of<u style="single">Cache for a set of data</u>Locally storable due to size of 520<u style="single">Set of data</u>The number of is determined. For example, 384K<u style="single">Cache for a set of data</u>Are each 16K in size<u style="single">Set of data</u>Can store up to 24. Similarly, larger size<u style="single">Set of data</u>Can be stored less, whereas smaller sizes<u style="single">Set of data</u>You can also save more. In one embodiment<u style="single">Cache for a set of data</u>520 are all the same size<u style="single">Set of data</u>Used to hold, or in another embodiment,<u style="single">Cache for a set of data</u>520 is of various sizes<u style="single">Set of data</u>Can be owned.
<u style="single">Cache for a set of data</u>Another factor that affects the size of the end user is<u style="single">Computer</u>All 130 available memory resources. Of limited memory resources<u style="single">Computer</u>Is<u style="single">Cache for a set of data</u>Provides a relatively small portion of the memory, whereas it has a large memory resource<u style="single">Computer</u>Has a relatively large amount of memory<u style="single">Cache for a set of data</u>Can be provided to.
<u style="single">Cache for a set of data</u>Yet another factor that may affect the amount of memory used by the 520 is<u style="single">Cache for a set of data</u>The relative size of the memory 514 allocated to the 520 and the memory 504 allocated to the navigation application 420.<u style="single">Cache for a set of data</u>Allocating a relatively large amount of memory relative to the 520 constrains the amount of memory 504 available in the navigation application 420, and vice versa, for the end user.<u style="single">Computer</u>It does not necessarily improve the performance of. Memory management application 500 allocates memory for navigation application 420 and<u style="single">Cache for a set of data</u>Algorithms can be included to determine the proper balance between memory allocation for use in. Required for navigation applications<u style="single">Set of data</u>(As determined by Memory Manager 500)<u style="single">Cache for a set of data</u>If not at 520, memory manager 500 is from navigation service server 120<u style="single">Set of data</u>To request.
IV.<u style="single">motion</u> A.<u style="single">Route guidance</u> (1)<u style="single">Overview</u> One of the functions performed by the navigation system 110 is route guidance. The route guidance gives the end user a command to reach the desired destination. FIG. 10 is a flow chart showing steps in process 600 for providing end users with information to follow a route to a desired destination performed by the navigation system 110 of FIG.
(2)<u style="single">Function prior to route guidance</u> a.<u style="single">Destination selection</u> Directions are associated with, or begin with, one or more other functions performed by the navigation system 110. There are steps to determine the origin and destination of the route before the information to follow the route is provided to the end user (step 610 in FIG. 10). Destination determination involves providing the end user with a means of selecting a location in Region 100. Destination selection can include addresses, street intersections, map locations, or other location-finding means. Alternatively, the destination selection can include the end user's designation criteria or category, eg, the identification of the end user's location matching a particular type of restaurant located within a specified distance.
In the embodiments of FIGS. 1 and 10, the destination selection function can be performed using a combination of locally available data, hardware or software and remote data, hardware or software. .. According to one embodiment, the end user is his or her<u style="single">Computer</u>At 130, locally available hardware and software (eg, query application 420 (5) in FIG. 9) is used to access the search application in navigation service server 120 (224 in FIG. 2). The end user uses this combination of local hardware and software and remote hardware and software to access the working database 122 of the navigation service server 120 and locate it as a destination. .. The destination can be an address, a person's name, a company address, or a company name. Alternatively, the end user can use a search application (224 in Figure 2) to find an individual, company, or point of interest by a location, eg, a bank near a designated location.
In some cases, the end user is the end user<u style="single">Computer</u>A positioning application locally mounted on the navigation service server 120 (420 (1) in Figure 9) is first used to identify his or her current location, which is then transferred to the search application 224 on the navigation service server 120. It can be specified and used to search for individuals, businesses or points of interest on a location basis.
In another embodiment, the end user can use locally available data, hardware or software to determine the destination. According to yet another embodiment, the destination selection function uses locally available data, hardware or software, and data obtained from a remote navigation service server of the end user.<u style="single">Computer</u>Can be run on.
b.<u style="single">Designation of departure place</u> The starting point (ie, the starting point) is also required to calculate the route. In some cases, the end user's current location can be used as the starting point. The end user's current location is that of the end user<u style="single">Computer</u>It can be determined using the positioning application 420 (1) locally installed in the 130 navigation applications 420. When performing this function, positioning application 420 (1) can use locally available data. These locally available data are end-user<u style="single">Computer</u>Can be part of the geographic database built into. Alternatively, locally available data is pre-obtained from the navigation service server 120 in response to a previous request made by the end user using query application 420 (5). According to yet another embodiment, the starting point can be determined in the same way as the destination. According to yet another embodiment, the end user's current position is that of the end user.<u style="single">Computer</u>It can be specified using the coordinates obtained using the positioning system (430 in FIG. 9) in. According to yet another embodiment, the user can explicitly indicate where the route begins. This is the same as the destination selection described above.
(3)<u style="single">Route calculation</u> After the origin and destination have been specified, process 600 includes a step in which data indicating the origin and destination is received by the routing application 220 on navigation server 120 (step 622 in FIG. 10). As mentioned above, the route calculation application 220 seeks an answer route that is a legally valid continuous sequence of roads (or sections thereof) between a designated starting point and a destination. The route calculation application 220 uses the data in the working geographic database 122. The operation of the route calculation application 220 has already been described. When the answer route is calculated, it identifies a sequence of routes or sections that generate a continuous, legally valid route from origin to destination.
Output 650 is given after the route calculation application 220 calculates the answer route. FIG. 11 is a schematic representation of the components of output 650 of the route calculation application 220. The route calculation output 650 includes a numbered list that identifies a plurality of road sections. In FIG. 11, a plurality of road sections are specified by data entity IDs. These IDs are assigned by the developers of the working geographic database 122 to the data entities that represent these road sections. Multiple road section data entities in output 650 of route calculation application 220 are labeled seg1, seg2, seg3, ... seg (n). The plurality of data entities represent road sections that generate a route between a continuous navigable origin and destination calculated by the route calculation application 220. Instead of using the data entity ID, the route calculation application 220 may also use other means for identifying the road section that produces the answer route.
The route calculation output 650 can include other information in addition to the list of road sections.
(4)<u style="single">Providing routes (and additional data) to end users</u> After the route calculation application 220 of the navigation service server 120 calculates the answer route, the navigation service server 120 can provide the end user with guidance to follow the answer route.<u style="single">Computer</u>Send data to 130. The navigation service server 120 is an end user<u style="single">Computer</u>Send two types of data to 130. First, the navigation service server 120 outputs 650 of the route calculation application 220 indicating the road section that generates the answer route to the end user.<u style="single">Computer</u>Send to 130 (step 656 in Figure 10). In addition to the data 650 indicating the answer route, the navigation service server 120 also transmits additional data 660 related to the answer route. Additional data 660 associated with the answer route is used in combination with data 650 indicating the answer route to provide the end user with meaningful guidance for traveling the route.
Navigation service server 120 for end users<u style="single">Computer</u>Additional data 660 transmitted to 130 is obtained from downloadable geodata storage device 124. After the answer path has been calculated (in step 636), the geographic data providing application (228 in Figure 2) is the end user's data from the geodata storage device 124 where data can be downloaded.<u style="single">Computer</u>Determine if it will be sent to 130 (step 668 in Figure 10). As described above, the data contained in the downloadable geographic data storage device 124 is systematized into a plurality of collections 232, each of which is a plurality of collections 232.<u style="single">Set of data</u>It is systematized into (320 in Fig. 4). Therefore, which geographic data is of the end user<u style="single">Computer</u>When deciding whether to send to 130, the geographic data providing application 228 tells you which data<u style="single">Set of data</u>Determines whether to send 320 from a particular collection 232.
As mentioned above, the determination of which collection 232 to use when transmitting geographic data can be determined in a variety of different ways. One way is for the end user<u style="single">Computer</u>To include an application that identifies the collection from which the data will be sent. Collection 232 can be identified by ID or description. Alternatively, the geographic data providing application 228 can query the subscriber database 208 in FIG. 2 to determine which collection 232 to use for a particular end user. Alternatively, the geographic data providing application 228 can use one collection by default. Any other means can be used to determine a suitable collection for use.
In addition to specifying which collection 232 to use when sending geographic data, the end user<u style="single">Computer</u>The application in also saves the data received from the navigation service server by the end user.<u style="single">Computer</u>The memory resources available in can be shown in geographic data providing application 228. Alternatively, the end user<u style="single">Computer</u>The size of the memory resource available in can be saved as a configuration parameter in the subscriber database 208 in Figure 2, or the default memory size can be used in another approach.
Specific in collection 232 after the collection 232 of data to use has been determined<u style="single">Set of data</u>320 is selected. Figure 12 shows the geographic data providing application 228 as an end user.<u style="single">Computer</u>Which data<u style="single">Set of data</u>Explains how to decide whether to send. FIG. 12 shows a map 690 of a portion of region 100. Route 700 is shown on map 690. Route 700 is shown as multiple connected road sections 706. Map 690 also shows an outline 710 from geographical divisions 312 (A) to 312 (L). As mentioned above, each of these geographic divisions 312 (A) to 312 (L) is a separate piece of data.<u style="single">Set of data</u>Contains the geographic features represented by the data contained in 320<u style="single">Set of data</u>The entire collection of geographic data 232 is divided within. The geographic data providing application 228 uses the position of the road section in the answer route 650 as calculated by the route calculation application 220 to cross the answer route or geographically within a specified distance from the road section in the answer route 312 To identify. (The designated distance can be set.) The geographical division that the answer route crosses or is close to the answer route can be determined by any of the preferred means. For example, the route calculation application 220 may use the IDs of these geographic divisions (or their own) when the answer routes are calculated.<u style="single">Set of data</u>ID) can be saved.
When the answer route crosses or the geographical divisions 312 (A) to 312 (L) close to the answer route are determined, the end user<u style="single">Computer</u>Contains data representing the geographic features contained in the geographic division for transmission to 130<u style="single">Set of data</u>320 is decided.
Geographic data providing application 228 corresponds to the answer route<u style="single">Set of data</u>The end user's<u style="single">Computer</u>When sending to<u style="single">Set of data</u>Are transmitted in the order corresponding to the route starting from the place of departure. In this way, the end user<u style="single">Computer</u>Contains data that represent the characteristics around the place of departure<u style="single">Set of data</u>First receives, then contains data representing features around the next part of the route<u style="single">Set of data</u>To receive.
Corresponds to the answer route<u style="single">Set of data</u>The end user's<u style="single">Computer</u>When sending to the geographic data providing application 228, all corresponding answer paths<u style="single">Set of data</u>The end user's<u style="single">Computer</u>Can be sent immediately to. Alternatively, the geographic data providing application 228<u style="single">Set of data</u>Send only some of them first, then<u style="single">Set of data</u>The rest of the can be sent at one or more next time. End user<u style="single">Computer</u>But all identified as corresponding to the answer path<u style="single">Set of data</u>If you have enough memory resources to hold the geographic data providing application 228, all<u style="single">Set of data</u>Immediately of the end user<u style="single">Computer</u>Can be sent to. However, the end user<u style="single">Computer</u>But all identified as corresponding to the answer path<u style="single">Set of data</u>If you do not have enough memory resources to hold the geographic data providing application 228, the end user<u style="single">Computer</u>Can be held in memory<u style="single">Set of data</u>You can send as many as the number of. First sent by geographic data providing application 228<u style="single">Set of data</u>Corresponds to the first part of the route. Geographic data providing application 228 corresponds to the answer route<u style="single">Set of data</u>The geographic data providing application 228 is not transmitted when only some of the<u style="single">Set of data</u>Maintain a list that identifies. According to this embodiment, the end user is first stored in memory.<u style="single">Set of data</u>After following the path through the area represented by<u style="single">Computer</u>Corresponds to the navigation service server for the next part of the route<u style="single">Set of data</u>Request to send. Corresponds to the answer route stored in the geographic data providing application 228<u style="single">Set of data</u>Which next using the list of<u style="single">Set of data</u>The end user's<u style="single">Computer</u>Quickly identify whether to send to.
Returning to process 600 in Figure 10, all the answers that correspond to the answer path.<u style="single">Set of data</u>Is the end user<u style="single">Computer</u>If sent to, the process ends (steps 722 and 724). All corresponding to the answer route<u style="single">Set of data</u>Is the end user<u style="single">Computer</u>If it is not sent to (for example, the end user's<u style="single">Computer</u>Is all<u style="single">Set of data</u>Not sent if you don't have enough memory to hold it)<u style="single">Set of data</u>The data that identifies the data is saved (step 725). This process then involves the end user<u style="single">Computer</u>Corresponds to the next part of the route<u style="single">Set of data</u>Wait until you request. Upon receiving a request for the next part of the route, additional data<u style="single">Set of data</u>Is the end user<u style="single">Computer</u>Is sent to (again in step 720). These steps correspond to the answer path<u style="single">Set of data</u>Is repeated until all are transmitted (steps 722 and 724).
(5)<u style="single">Providing navigation-related functions on the end user's computer</u> FIG. 13 shows the end user when receiving route-indicating data 650 and additional data 660 from the navigation service server 120.<u style="single">Computer</u>The process 750 executed above is shown. First, the data 650 and 660 are of the end user<u style="single">Computer</u>Received at 130 (step 760).
Memory management application 500, if not already done<u style="single">Cache for a set of data</u>End-user's for use as 520<u style="single">Computer</u>Reserve a portion of the memory of (step 764).<u style="single">Cache for a set of data</u>Memory management application 500 receives when generating<u style="single">Set of data</u>Take into account the size of. For example<u style="single">Set of data</u>If is 64K in size, the memory management application 500 will have 200<u style="single">Set of data</u>You can reserve enough 1280K of memory to own. Memory management application 500<u style="single">Set of data</u>Additional data 660 in the form of 320,<u style="single">Cache for a set of data</u>Save to 520 (step 770).
Generated by memory management application 500<u style="single">Cache for a set of data</u>520 is all about all routes<u style="single">Set of data</u>Cannot be large enough to secure. In this case, the memory management application 500 is in the order in which it was sent from the navigation service server 120.<u style="single">Set of data</u>Save and<u style="single">Cache for a set of data</u>More when is full<u style="single">Set of data</u>Stop saving. In this way, the additional data corresponding to the beginning of the route<u style="single">Set of data</u>660,<u style="single">Cache for a set of data</u>It is saved in. At this time, the additional data corresponding to the next part of the route<u style="single">Set of data</u>660 is<u style="single">Cache for a set of data</u>Not saved in. The memory management application 500 can store (or store) the size of the cache in the geographic data providing application 228.<u style="single">Set of data</u>A message indicating the number of) can be sent. Alternatively, the memory management application 500 can be added to the geographic data providing application 228.<u style="single">Cache for a set of data</u>When is full<u style="single">Set of data</u>You can send a message to stop sending.
End user<u style="single">Computer</u>In the data 650 showing the answer route,<u style="single">Cache for a set of data</u>Not saved in 520. Instead, data 650 indicating the answer path is stored in the working portion of memory (504 in FIG. 9), and the data is stored in the end user's data.<u style="single">Computer</u>Used in 130 different navigation applications 420.
End user<u style="single">Computer</u>In, the navigation application (420 in FIG. 9) uses additional data 660 associated with the answer path in combination with data 650 indicating the answer path to provide navigation-related functionality (step 776). For example, the end user<u style="single">Computer</u>The route guidance application 420 (2) of 130 can use the route data 650 and the additional data 660 to give a move command at a specific position along the answer route. As an example, the route guidance application 420 (2) uses the route data 650 and the additional data 660 to give a movement instruction such as "Next intersection, turn left". These additional data 660s are used to give these instructions as text or voice instructions on the display screen.
According to another embodiment, the route data 650 and the additional data 660 related to the answer route are provided by the end user.<u style="single">Computer</u>Used in 130 map display applications 420 (3) for end-users<u style="single">Computer</u>A map of the route can be given to the display screen of the user interface (410 in Fig. 9). The route map can be in the form of a "course map".
According to yet another embodiment, the route data 650 and the additional data 660 can be used to indicate the location of a road section that is not part of the answer route but is adjacent to the answer route. These data are for vehicle positioning hardware and software, such as end-users.<u style="single">Computer</u>Used in positioning application 420 (1) to determine if the end user deviates from the answer path, and if so (eg using rerouting application 420 (4)). You can determine how to return to the answer path.
As mentioned above, all data related to all answer paths represented by data 650.<u style="single">Set of data</u>It is not possible to store the 320 first. In this case, it contains data representing geographic features along the first part of the route.<u style="single">Set of data</u>Only the end user<u style="single">Computer</u>of<u style="single">Cache for a set of data</u>First saved in. Then, after the end user travels halfway along the path, the end user finally<u style="single">Cache for a set of data</u>-Approach the position of the data coverage at the end. For example, looking back at Figure 12, the end user<u style="single">Computer</u>of<u style="single">Cache for a set of data</u>But 6 data<u style="single">Set of data</u>Six corresponding areas 312 (A) to 312 (F) if provided with space to store only<u style="single">Set of data</u>But first<u style="single">Cache for a set of data</u>Will be saved in. Then, after the end user has traveled along the route to the point indicated by B, the end user<u style="single">Cache for a set of data</u>The scope of the additional data stored in is closer to the end of the scope. When the end user is in this position, the end user<u style="single">Computer</u>Query application 420 sends a new request for navigation-related services and data to the navigation service server 120 (steps 790 and 792). This new request can be based on the previous request or can be treated as a request for a new route.
One way is to end-user<u style="single">Computer</u>But that<u style="single">Cache for a set of data</u>Locally contained in<u style="single">Set of data</u>Approaching the edge of the scope corresponding to, further from the navigation service server<u style="single">Set of data</u>When requesting (step 792), this new request can be based on the previous request. If the new request is relative to the previous request, the process at the navigation service server is the end user's (in step 725 of Figure 10).<u style="single">Computer</u>Not pre-sent to<u style="single">Set of data</u>Which using the list to identify<u style="single">Set of data</u>To decide whether to send next. these<u style="single">Set of data</u>Is obtained from downloadable data storage device 124 and is of the end user's<u style="single">Computer</u>Will be sent to. These new<u style="single">Set of data</u>Is the end user<u style="single">Computer</u>When received at, step 760 initiates process 750.
According to another method, the end user<u style="single">Computer</u>Is the<u style="single">Cache for a set of data</u>Locally contained in<u style="single">Set of data</u>Approaching the edge of the scope corresponding to, further from the navigation service server<u style="single">Set of data</u>(Step 792), the request can be processed by the navigation service server as a request for an entirely new route. The navigation service server executes process 600 starting at step 622 in Figure 10. The navigation service server 120 uses the route calculation application 220 to calculate a new route to the destination, using point B as the new starting point (also step 636 in FIG. 10). By processing the request for the next leg of the route as a request for the new route, the navigation service server's route calculation application 220 takes into account any changes in road conditions that may occur since the previous route was calculated. be able to. The navigation service server 120 is then the end user's<u style="single">Computer</u>With a new route (in the form of new route data 650) and (in the form of new route data 650)<u style="single">Set of data</u>In the form of new additional data 660<u style="single">Set of data</u>Is transmitted (also steps 656 and 720 in FIG. 10). New route data 650 and new additional data 660 are end-user<u style="single">Computer</u>When received at, these are treated as entirely new routes.<u style="single">Cache for a set of data</u>Was stored in<u style="single">Set of data</u>Is a new received in connection with the next leg of the route<u style="single">Set of data</u>Can be rewritten with.
B.<u style="single">Map display without route guidance</u> In another embodiment, the end user can request geographic data for map display without necessarily requesting a route. For example, the end user may seek to get a map of the area surrounding the location where he or she is located. In this case, the end user requests his or her to map around his or her geographic location.<u style="single">Computer</u>To operate. The end user can use the query application 420 (5) for this purpose. The end user can also specify his or her location, or the query application 420 (5) obtains data indicating the end user's current location from the positioning system 430 (if any). This information can be included in the request for map display data.
The request for the map display data is processed by the navigation service server 120 in the same manner as the request for the route information described above. In this case, it is not necessary to calculate the route. The navigation service server contains geographic data that represents features around the designated location.<u style="single">Set of data</u>To identify. The navigation service server then, as mentioned above, these<u style="single">Set of data</u>The end user's<u style="single">Computer</u>Send to. End user<u style="single">Computer</u>In these<u style="single">Set of data</u>Is processed in the same manner as previously described for FIG.
Instead of requesting map data for his or her end user's current location, the end user can request map data for any location. The end user can use any of the preferred means to identify the location where the map data is required.
C.<u style="single">Other features</u> End user<u style="single">Computer</u>Any of the features provided in can be used in combination with each other or separately. For example, the positioning function (ie, using the positioning application 420 (1) of FIG. 9) can be performed without the map display function or the route guidance function.
III.<u style="single">Another embodiment</u> A.<u style="single">Feature-based data collection selection</u> In connection with FIG. 8, a collection of data systematized by format (or function) has been described. Various types and functions of data collection are provided. For example, different collections of data can be given in addition to route guidance, map display, vehicle positioning, voice data, non-voice data and more. End user<u style="single">Computer</u>When you request geographic data, the navigation service server will indicate the type of data. This type is for end users<u style="single">Computer</u>Can be specified according to the resource supported by. This type can also specify, depending on the function, the data that the end user's platform needs to perform. For example, if the end user intends only to display a map and not to provide route guidance, the end user's<u style="single">Computer</u>Can specify the data sent from the map display collection. In this way, the end user<u style="single">Computer</u>Does not send data that it does not need, which allows it to send more data of the specified type.
B.<u style="single">Layer-based data collection</u> In addition to the data collection types described above (232 in FIGS. 5-8), the downloadable data storage device 124 in FIG. 2 can include layer-based collections. Layer-based collections use the ranking assigned to roads in the area. Ranking can be associated with the functional classification of roads. Trunk roads that move faster are generally assigned to higher orders, and smaller roads that move generally slower are assigned to lower orders. Data representing higher ranked roads are stored in one or more collections separate from the lower ranked roads using these rankings.
C.<u style="single">Download applets and plugins</u> In addition to data representing the route and additional data representing geographical features along the route (or around other locations), the end user<u style="single">Computer</u>There are other types of data and information available from navigation service providers. According to one embodiment, the navigation service provider provides the navigation application to the end user.<u style="single">Computer</u>Can be sent to. The navigation service server is the end user<u style="single">Computer</u>The navigation application sent to can be a new application or an updated version of a previous version of the navigation application. Navigation applications sent by navigation service providers should include any of the applications running on the end user's computer platform, including routing, mapping, positioning, query services, rerouting, memory management, and more. Can be done. In one embodiment, these navigation applications are transmitted as applets or plug-ins. Referring again to FIG. 2, in one embodiment, the navigation service provider 128 stores the navigation applet (or plug-in) 800 in the downloadable storage device 802 of the navigation service server 120. Then, upon receiving a request from the end user, the navigation service server 120 sends the navigation applet or plug-in to the end user.<u style="single">Computer</u>Send to. Applets or plugins are end-user<u style="single">Computer</u>Can be used in. Applets or plugins are end-user<u style="single">Computer</u>Can be used with other applications such as browsers installed on. In this embodiment, the end user identifies the type of navigation function desired, and then the navigation service server is used in the applet (or plug-in) as well as in the navigation applet (or plug-in). Also send the data that becomes. As an example, if the end user wants to get directions, the navigation service server will provide a route guidance applet, data showing the route, and additional data showing the geographic features along the route. Send. The routing applet is an end-user<u style="single">Computer</u>When downloaded to and properly installed, it works in the same way as the routing application (420 (2) in Figure 9). In this way, both software and data about the functionality desired by the end user is provided by the navigation service provider.
IV.<u style="single">advantage</u> Various advantages can be obtained from the disclosed embodiments of the system. As mentioned above, the navigation system 110 has many different types of end users.<u style="single">Computer</u>It corresponds to. Navigation servers of different types<u style="single">Computer</u>If you have to determine the appropriate data format to send to each of the, the navigation server will be overwhelmed. Therefore, the navigation server is a pre-computed data<u style="single">Set of data</u>Is used, which facilitates this process.
Pre-calculated data<u style="single">Set of data</u>Is from the navigation server to the end user<u style="single">Computer</u>Designed to be treated as the smallest unit of size of data transferred for use in. Pre-calculated<u style="single">Set of data</u>Has a uniform size, which makes it end-user<u style="single">Computer</u>Can easily manage these.
A separate work database used by the navigation service server (122 in Figure 2) and the end user<u style="single">Computer</u>Another advantage comes from having downloadable geographic data (124 in Figure 2) for use in. The working database can be optimized for use on the server, and the data contained in the downloadable geographic data storage is for the end user.<u style="single">Computer</u>Can be optimized for use in.
Another advantage of the disclosed embodiments is the pre-computed data sent by the navigation service provider to the end user.<u style="single">Set of data</u>Is that it can be guaranteed to have connectivity. When data representing features along the route is transmitted to the end user, it is preferred that all road sections reachable by the end user are represented. This can include a considerable amount of processing. Pre-calculated data using any of the disclosed embodiments.<u style="single">Set of data</u>Is generated, the connectivity of all the roads represented is guaranteed.
The detailed description above is intended to be considered as explanatory rather than limiting, and the appended claims include all equivalents and are the scope of the present invention. It should be understood that it is intended to define.
<figref num="1">End-users with geographic data located across regions<u style="single">Computer</u>It is a figure explaining the component of the navigation system to send to.</figref><figref num="2">It is a block diagram which shows the component of the navigation service provider of FIG.</figref><figref num="3">A map of the area in FIG. 1 and an embodiment for systematizing downloadable geographic data stored in a navigation server using this map will be described.</figref><figref num="4">It is a diagram showing some components in a collection of geographic data stored in the downloadable geographic data storage device shown in FIG.</figref><figref num="5">It is a diagram showing one component in a collection of geographic data stored in the downloadable geographic data storage device shown in FIG.</figref><figref num="6">It is a diagram showing another component in a collection of geographic data stored in the downloadable geographic data storage device shown in FIG.</figref><figref num="7">It is a diagram showing another component in a collection of geographic data stored in the downloadable geographic data storage device shown in FIG.</figref><figref num="8">FIG. 5 shows the components of an additional collection of geographic data stored in the downloadable geographic data storage device shown in FIG.</figref><figref num="9">End users shown in Figure 1<u style="single">Computer</u>It is a block diagram which shows one of the components.</figref><figref num="10">It is a flowchart which shows the step in the process executed by the navigation service server of FIG.</figref><figref num="11">From the navigation service server for the process shown in Figure 10 to the end user<u style="single">Computer</u>It is a block diagram which shows the component of the route data transmitted to.</figref><figref num="12">It is a map used to explain a part of the process in FIG.</figref><figref num="13">After the navigation service server runs the process in Figure 10, the end user<u style="single">Computer</u>It is a flowchart of the steps executed in.</figref>
Every citation, both ways
| Document | Relation | Office |
|---|---|---|
| JP2001012960A | Cites | Japan |
| JP2000283777A | Cites | Japan |
| JP2000236571A | Cites | Japan |
| JP2000123290A | Cites | Japan |
| JP11143358A | Cites | Japan |
| JP10103993A | Cites | Japan |
| JP2001084493A | Cites | Japan |
| JP09325040A | Cites | Japan |
| JP11345247A | Cites | Japan |
14 members in 5 offices
Priority claims5
| Document | Office | Kind | Date |
|---|---|---|---|
| 09838094 | United States of America | – | |
| 83809401 | United States of America | A | |
| 83809401 | United States of America | A | |
| 2001838094 | – | – | – |
| US20010838094 | – | – | – |
Members14
| Document | Office | Kind | |
|---|---|---|---|
| EP1251335A2 | European Patent Office (EPO) | A2 | |
| US2002169778A1 | United States of America | A1 | |
| JP2003090735A | Japan | A | |
| US6691128B2 | United States of America | B2 | |
| US2004107220A1 | United States of America | A1 | |
| EP1251335A3 | European Patent Office (EPO) | A3 | |
| JP2008175830A | Japan | A | |
| EP1251335B1 | European Patent Office (EPO) | B1 | |
| AT454609T | Austria | T | |
| ATE454609T1 | Austria | T1 | |
| DE60234975D1 | Germany | D1 | |
| JP4460816B2 | Japan | B2 | |
| US7801904B2 | United States of America | B2 | |
| JP4928490B2This record | Japan | B2 |
18 legal events, as the office reported them to INPADOC
Over the term
Point at a mark for the eventEvents
| Event | Code | |
|---|---|---|
| Cancellation because of no payment of annual feesLAPS | LAPS | |
| Renewal fee payment (event date is renewal date of database)FPAY | FPAY | |
| Written notification of registration of transferJAPANESE INTERMEDIATE CODE: R350R350 | R350 | |
| Request for change of ownership or part of ownershipJAPANESE INTERMEDIATE CODE: R313113S111 | S111 | |
| Renewal fee payment (event date is renewal date of database)FPAY | FPAY | |
| Certificate of patent or registration of utility modelJAPANESE INTERMEDIATE CODE: R150R150 | R150 | |
| First payment of annual fees (during grant procedure)JAPANESE INTERMEDIATE CODE: A61A61 | A61 | |
| Written decision to grant a patent or to grant a registration (utility model)JAPANESE INTERMEDIATE CODE: A01A01 | A01 | |
| Written decision to grant a patent or to grant a registration (utility model)JAPANESE INTERMEDIATE CODE: A01A01 | A01 | |
| Decision of grant or rejection writtenTRDD | TRDD | |
| Transfer to examiner for re-examination before appeal (zenchi)AppealJAPANESE INTERMEDIATE CODE: A911A911 | A911 | |
| Written amendmentJAPANESE INTERMEDIATE CODE: A523A521 | A521 | |
| Written amendmentJAPANESE INTERMEDIATE CODE: A523A521 | A521 | |
| Decision of refusalJAPANESE INTERMEDIATE CODE: A02A02 | A02 | |
| Written amendmentJAPANESE INTERMEDIATE CODE: A523A521 | A521 | |
| Written permission of extension of timeJAPANESE INTERMEDIATE CODE: A602A602 | A602 | |
| Written request for extension of timeJAPANESE INTERMEDIATE CODE: A601A601 | A601 | |
| Notification of reasons for refusalJAPANESE INTERMEDIATE CODE: A131A131 | A131 |
Numbers
- Publication
- 4928490
- Publication, DOCDB
- 4928490
- Publication, EPODOC
- JP4928490B
- Application
- 80957
- Application, DOCDB
- 2008080957
- Application, EPODOC
- JP20080080957
Titles2
- Japanese
- 分散型計算アーキテクチャによるナビゲーション・システム
- English
- Navigation system with distributed computing architecture
Classification
- CPC, 6
- G01C21/3881
- G01C21/34
- G06F16/29
- G01C21/3889
- G01C21/3896
- Y10S707/99943
- IPC, 9
- G01C21 00
- G08G1 005
- G08G1 137
- G09B29 00
- G09B29 10
- G01C21 32
- G01C21 34
- G06F15 00
- G06F17 30