Providing navigation services using context-aware trajectory analysis

A computer system provides navigation services. Route data is processed to extract a plurality of routes, wherein each route comprises a plurality of links and nodes. A partition layer is generated for a map including the plurality of links and nodes of the routes, wherein the partition layer comprises a plurality of meshes each containing links and nodes of the map. A context is processed to remove invalid links and nodes from the map based on the context. The partition layer is updated by merging a subset of the plurality of meshes in response to the removal of the invalid links and nodes. A navigation service is provided for the plurality of routes based on the updated partition layer of the map. Embodiments of the present invention further include a method and program product for providing navigation services in substantially the same manner described above.

BACKGROUND

1. Technical Field

Present invention embodiments relate to providing navigation services, and more specifically, to providing location-based navigation services that are based on a context-aware trajectory analysis.

2. Discussion of the Related Art

Location-based navigation services may include any services that provide information related to a travel route of a vehicle, such as travel directions, estimated travel time, route conditions, and the like. With the spread of location-aware mobile devices and connected vehicles, the trajectories of vehicles in a geographic area may be analyzed to enhance the accuracy of a navigation service. As the accuracy of a navigation service increases, the trajectory analysis that supports the service becomes computationally expensive. However, efforts to lessen the computational requirements of a navigation service typically also reduce the accuracy of the service.

SUMMARY

According to one embodiment of the present invention, a computer system provides navigation services. Route data is processed to extract a plurality of routes, wherein each route comprises a plurality of links and nodes. A partition layer is generated for a map including the plurality of links and nodes of the routes, wherein the partition layer comprises a plurality of meshes each containing links and nodes of the map. A context is processed to remove invalid links and nodes from the map based on the context. The partition layer is updated by merging a subset of the plurality of meshes in response to the removal of the invalid links and nodes. A navigation service is provided for the plurality of routes based on the updated partition layer of the map. Thus, present invention embodiments reduce the amount of computational resources required to provide a navigation service without sacrificing the accuracy of the navigation service. By accounting for contexts, such as traffic conditions for the time of day, present invention embodiments may omit certain links and nodes from processing, thereby further reducing the computational requirements for a geographic area.

Various other embodiments of the present invention will now be discussed. In some embodiments, the navigation service comprises one or more of: real-time danger avoidance, and future traffic prediction. Thus, a navigation service may provide assistance while avoiding any dangerous situations and accounting for future traffic events, such as congestion. In some embodiments, the context is one or more of: a time and a day of a week, a weather condition, a vehicle type, and a traffic quantity. By removing links and nodes that are rendered invalid due to one or more contexts, the computational requirements for providing a navigation service are reduced. In some embodiments, generating the partition layer further comprises providing an initial layer comprising a plurality of meshes of equal size, identifying groups of adjacent meshes, wherein each group collectively includes a same number of links and nodes as a mesh in the group that has a highest number of links and nodes, and merging each identified group of adjacent meshes. By merging meshes, the overall number of meshes is reduced, which reduces the computational requirements for providing a navigation service that covers a geographical area. In some embodiments, merging a group of adjacent meshes generates a merged mesh having a level of granularity that is coarser than the levels of granularity of the meshes of the group of adjacent meshes. Merging meshes to generate a merged mesh having a coarser level of granularity enables navigation services to be provided to a larger area while requiring an amount of computational resources that would otherwise be used to provide navigation services to a smaller area. In some embodiments, a shape of a mesh of the plurality of meshes comprises a quadrilateral. Using quadrilateral-shaped meshes simplifies the merger process by ensuring that the shapes and/or sizes merged meshes can be easily predicted. In some embodiments, the subset of the plurality of meshes comprises one or more groups of meshes, wherein each group of meshes collectively includes a same number of links and nodes as a mesh in the group that has a highest number of links and nodes. By merging meshes such that each mesh has a same number of links and nodes, the processing requirements for providing a navigation service may be spread out evenly across the meshes. In some embodiments, the plurality of routes share a same origin and destination. When routes share an origin and destination, users traveling along the routes may utilize navigation services that benefit from shared computations for the geographical area encompassed by the routes, thereby reducing the overall amount computational requirements. In some embodiments the route data is received from a plurality of mobile devices, and the route data that is received from each mobile device comprises one or more of: a location of the mobile device, and a velocity of the mobile device. By receiving route data from multiple mobile sources, present invention embodiments may provide navigation services that benefit from more accurate and recent information. Embodiments of the present invention further include a method and program product for providing navigation services in substantially the same manner described above.

DETAILED DESCRIPTION

Present invention embodiments relate to providing navigation services, and more specifically, to providing location-based navigation services that are based on a context-aware trajectory analysis. A navigation service may provide real-time information relating to a vehicle's route that is based on factors such as driving conditions, traffic, and the like. For example, a navigation service may prompt a driver to take an alternate route because of a road closure or a traffic jam ahead. A navigation service may provide information to a user device or, in the case of a self-driving vehicle, may integrate into an autonomous navigation system.

In order to support accurate, real-time navigation services, a large volume of information relating to a given geographical area must be collected and processed. The information may be collected from multiple mobile devices in the geographical area. For example, devices such as smartphones may provide location information to a system, including a device's position at a moment in time. By analyzing the trajectories of multiple mobile devices, a navigation service can identify present traffic conditions and predict future conditions.

To provide accurate services for a geographical area, the area may be divided into smaller elements that are processed separately. In general, when a geographical area is divided into finely-grained elements, the accuracy of a navigation service's analysis increases, but so do the computational requirements of the service. For regions where road networks are complex, such as urban areas, finely-grained elements may be required. However, in rural areas, more coarsely-grained elements are suitable. Present invention embodiments divide an area into variously-sized meshes that are based on a road network's complexity. The size of each mesh may be optimized according to the number of links and nodes (e.g., roads and junctions) in the mesh. For example, high-complexity regions may be processed using many smaller meshes, and low-complexity regions may be processed using fewer, larger meshes. Thus, present invention embodiments reduce the amount of computational resources required to provide a navigation service without sacrificing the accuracy of the service. Present invention embodiments also factor in contexts, such as traffic conditions for the time of day, in order to omit certain links and nodes from processing, thereby further reducing the computational requirements for a geographic area. For example, in an urban region where traffic quantity is extremely low during the evening, coarsely-grained meshes may be applied despite the road network density for the region being high. Thus, present invention embodiments provide navigation services for various applications, such as fleet management systems in which long-distance route searching and navigation is constantly employed. Additionally, navigation services may support public transportation systems, by providing context-aware operation management, as well as traffic control systems, which utilize real-time traffic predictions.

It should be noted that references throughout this specification to features, advantages, or similar language herein do not imply that all of the features and advantages that may be realized with the embodiments disclosed herein should be, or are in, any single embodiment of the invention. Rather, language referring to the features and advantages is understood to mean that a specific feature, advantage, or characteristic described in connection with an embodiment is included in at least one embodiment of the present invention. Thus, discussion of the features, advantages, and similar language, throughout this specification may, but do not necessarily, refer to the same embodiment.

These features and advantages will become more fully apparent from the following drawings, description and appended claims, or may be learned by the practice of embodiments of the invention as set forth hereinafter.

Present invention embodiments will now be described in detail with reference to the Figures.FIG. 1is a block diagram depicting a computing environment100for providing navigation services in accordance with an embodiment of the present invention. As depicted, computing environment100includes a plurality of client devices105A-105N, a trajectory analysis server140, and a database server170. It is to be understood that the functional division among components of computing environment100have been chosen for purposes of explaining present invention embodiments and is not to be construed as a limiting example.

Each client device105A-105N includes a network interface110, at least one processor115, a location module120, and memory125, which includes a navigation application130. User device105may include any mobile computing device, such as a laptop computer, a tablet computer, a netbook computer, a personal digital assistant (PDA), a smart phone, or any programmable mobile electronic device capable of executing computer readable program instructions. Network interface110enables components of each client device105A-105N to send and receive data over a network, such as network135. Each client device105A-105N may include internal and external hardware components, as depicted and described in further detail with respect toFIG. 7.

Location module120may include any mechanism for determining a present location of a client device. Location module120may receive one or more signals from ground-based, air-based, and/or satellite-based services in order to calculate a present position. In some embodiments, location module120is equipped to receive Global Positioning System (GPS) signals to determine the location of a client device105. The location of each client device105A-105N may be described in terms of a latitude, a longitude, and/or an elevation.

Navigation application130may include one or more modules or units to perform various functions of present invention embodiments described below. Navigation application130may be implemented by any combination of any quantity of software and/or hardware modules or units, and may reside within memory125of each client device105for execution by a processor, such as processor115.

Navigation application130may present information relating to navigation to a user of user device105. In general, navigation application130may receive information from a navigation service that relates to a user's trajectory. In some embodiments, navigation application130presents a real-time visual map and/or directions to a user to facilitate travel to a user-provided or other destination. For example, navigation application130may present a route to a user, may provide warnings of upcoming traffic events, conditions, or hazards, and the like. A user may provide information to navigation application130, including the user's route or destination, the type of vehicle in which the user is traveling, and travel preferences, such as a preference to avoid toll roads, a preference to avoid highways, and the like.

Network135may include a local area network (LAN), a wide area network (WAN) such as the Internet, or a combination of the two, and includes wired, wireless, or fiber optic connections. In general, network135can be any combination of connections and protocols known in the art that will support communications between each client device105, trajectory analysis server140, and/or database server170via their respective network interfaces110in accordance with embodiments of the present invention.

Trajectory analysis server140includes a network interface110, at least one processor115, memory145, and a database165. Memory145includes a map module150, a partition module155, and a context analysis module160. In various embodiments of the present invention, trajectory analysis server140may include a laptop computer, a tablet computer, a netbook computer, a personal computer (PC), a desktop computer, a personal digital assistant (PDA), a smart phone, or any programmable electronic device capable of executing computer readable program instructions. Network interface110enables components of trajectory analysis server140to send and receive data over a network, such as network135. In general, trajectory analysis server140analyzes trajectories of users and contexts of the trajectories to provide navigation services. Trajectory analysis server140may include internal and external hardware components, as depicted and described in further detail with respect toFIG. 7.

Map module150, partition module155, and context analysis module160may include one or more modules or units to perform various functions of present invention embodiments described below. Map module150, partition module155, and context analysis module160may be implemented by any combination of any quantity of software and/or hardware modules or units, and may reside within memory145of trajectory analysis server140for execution by a processor, such as processor115.

Map module150may receive and process roadway information for one or more geographical areas. In particular, map module150may process roadway information to identify nodes (e.g., junctions) and links (e.g., roadways) between nodes. Thus, map module150may output one or more maps comprising links and nodes for a selected area. Map module150may receive roadway information from a database, such as database175of database server170. In some embodiments, map module150retrieves roadway information from a Geographic Information System (GIS). Map module150may receive updated roadway information according to a predetermined schedule or on an ad hoc basis when updated map information becomes available. For example, when a new highway is opened, map module150may receive updated roadway information, which map module150processes to identify new links and/or nodes.

Partition module155may process a map that is output by map module150by dividing the map according to its links and nodes. In particular, partition module155may generate a partition layer for a map that includes a plurality of meshes, each corresponding to a particular region of the map. Each mesh may include one or more links and/or nodes, and may conform to any shape. In some embodiments, meshes are polygons, such as quadrilaterals; in further embodiments, meshes are rectangular- or square-shaped. Partition module155may generate a partition layer by generating an initial layer that partitions a map into meshes of equal size at high particular granularity level. For example, the initial layer may be a grid in which each mesh is a square mesh encompassing a same area. The length of the sides of each mesh may be a predetermined value, such as one hundred feet or one mile. In some embodiments, the size of the initial meshes and the alignment of the meshes may correspond to a land surveying system; for example, the meshes may correspond to sections, townships, or ranges, or subdivisions thereof, of the Public Land Survey System.

Partition module155may modify the meshes in the initial layer to generate a partition layer based on a static division method. In particular, meshes may be merged so that each mesh of a map encompasses a same number of links and/or nodes. For example, meshes may be merged such that the resulting partition layer comprises meshes that each contain three nodes and two links. Since densely-populated areas may have more complex roadways than rural areas, the resulting partition layer may feature many, smaller meshes corresponding to urban regions, and fewer, larger meshes that correspond to rural areas. A partition layer based on a static division method may be further modified according to one or more contexts. In particular, context analysis module160may process a context to provide instructions to remove certain nodes and links, and partition module155may modify a partition layer accordingly by further merging affected meshes. For example, if a particular mesh no longer contains any links or nodes, it may be merged with an adjacent mesh. The process of generating and modifying partition layers will be depicted and described in further detail below with reference toFIGS. 2 and 3.

Context analysis module160may receive one or more contexts for a trajectory and process each context to identify links and nodes that may be invalid due to a particular context. A context may include any event or condition that enables links and nodes to be removed from consideration. Contexts may include particular times of day and days of the week, weather conditions, vehicle types, and traffic quantities. A link may be removed if the traffic quantity on the link is zero or nearly zero. For example, if a particular roadway is so congested that it is unusable, or alternatively, if the roadway sees no traffic, then a link corresponding to the roadway may be removed from consideration. A node may be removed if all links leading to the node are also removed.

Context analysis module160may analyze a time of day or day of week to determine whether links and roads may be removed based on the predicted traffic for the link at the present time. Context analysis module160may receive weather information or traffic quantity information from a database, such as database165of trajectory analysis server140or database175of database server170. To process a vehicle type, context analysis module160may receive a vehicle type from a user, e.g., via navigation application130of a client device105. If the vehicle cannot travel along a particular link, context analysis module160may then remove the link. For example, if a vehicle type indicates that the vehicle is over a certain weight or size, then context analysis module160may identify links that cannot support the weight or size of the vehicle. After context analysis module160processes one or more contexts to identify links and nodes that can be removed, partition module155may modify a partition layer to account for the removal of links and nodes.

Database165may include any non-volatile storage media known in the art. For example, database165can be implemented with a tape library, optical library, one or more independent hard disk drives, or multiple hard disk drives in a redundant array of independent disks (RAID). Similarly, data on database165may conform to any suitable storage architecture known in the art, such as a file, a relational database, an object-oriented database, and/or one or more tables. Database165may store data relating to the generation of partition layers based on context-aware trajectory analyses, including maps, partition layers generated by the static division method, context information, and context-specific partition layers.

Database server170includes a network interface110, at least one processor115, and a database175. In various embodiments of the present invention, database server170may include a laptop computer, a tablet computer, a netbook computer, a personal computer (PC), a desktop computer, a personal digital assistant (PDA), a smart phone, or any programmable electronic device capable of executing computer readable program instructions. Network interface110enables components of database server170to send and receive data over a network, such as network135. Database server170may include internal and external hardware components, as depicted and described in further detail with respect toFIG. 7.

Database175may include any non-volatile storage media known in the art. For example, database175can be implemented with a tape library, optical library, one or more independent hard disk drives, or multiple hard disk drives in a redundant array of independent disks (RAID). Similarly, data on database175may conform to any suitable storage architecture known in the art, such as a file, a relational database, an object-oriented database, and/or one or more tables. Database175may store data relating to contexts, such as weather information, traffic information, including recurring traffic patterns, and the like. In some embodiments, database server170is a GIS server and database175stores geographical information, including roadway information, for a given area.

FIG. 2is a flow chart depicting a method200of generating a partition layer via static division in accordance with an embodiment of the present invention.

A map of an area is divided into a plurality of meshes at a fine level of granularity at operation210. The map may correspond to a geographic area in which one or more routes are located. Map module150may first produce a map that includes nodes that are connected by links. Partition module155may then generate an initial layer that includes a grid of meshes. Each mesh in the initial layer may be sized according to a fine level of granularity. The granularity of a mesh refers to the size of the mesh: at a fine level of granularity, each mesh is a smaller size, and as meshes are merged together to form larger meshes, the level of granularity becomes coarser. For example, at a fine level of granularity, each mesh may be a square with sides that are half of a mile in length; merging together four of these meshes to advance a level of granularity may produce a larger square mesh having sides that are each one mile in length. The fine level of granularity may correspond to a predetermined size. In some embodiments, the size of meshes in the initial layer is based on the overall size of the map. In particular, the length of a side of each mesh may be a percentage of the overall length of the map in one dimension. For example, each mesh in the initial layer may have sides that are 5% of the length of a map.

Meshes are temporarily merged by one level of granularity at operation220. Partition module155may temporarily merge two or more adjacent meshes to form a larger mesh at a coarser level of granularity. In some embodiments, partition module155only merges meshes if the merger would produce a mesh that is either rectangular or square in shape.

A temporarily-merged mesh is selected for processing at operation230. Partition module155may select an unprocessed mesh that has resulted from a temporary merge operation. At operation240, partition module155determines whether the temporary merger resulted in an increase in the number of links and/or nodes in the merged mesh as compared to the constituent mesh having the highest number of links and/or nodes. The positioning of the initial layer of meshes may result in some meshes that contain more nodes and/or links than other meshes. If two meshes can be merged without increasing the number of links and/or nodes in the merged mesh as compared to the constituent mesh having the highest number of links and/or nodes, the temporary merge operation is accepted at operation250. Otherwise, the temporary merge operation is discarded and the meshes are not merged at operation260. Thus, any mesh that does not contain any links or nodes may be merged with a mesh that does.

Operation270determines whether there are any remaining unprocessed meshes. If there are temporarily-merged meshes that have not yet been processed, then method200returns to operation230to process another temporarily-merged mesh.

Operation280determines whether all of the temporary merge operations resulted in an increase in the number of nodes and/or links (e.g., operation280determines whether the outcome of operation240is “YES” for all of the temporarily-merged nodes that were processed). Thus, partition module155may output a partition layer that comprises meshes which may be sized according to various levels of granularity, but may each contain a same number of links and nodes.

FIG. 3is a flow chart depicting a method300of generating a context-specific partition layer in accordance with an embodiment of the present invention.

A context is selected at operation310. The context may include any information that can indicate whether particular links or nodes are relevant for a route. A context may include a time of day and/or a day of the week, a weather condition, a vehicle type, a traffic quantity, and the like, as each of these conditions can affect whether a vehicle can traverse particular links and nodes. For example, some roadways in a geographical area may consistently become congested at certain times of day or in the presence of certain weather conditions, such as rain or snow. Similarly, some vehicle types may not be permitted to use specific roadways due to height and/or weight restrictions. Context analysis module160may select and process each context to generate a partition layer that is specific to a particular context or a combination of contexts.

Invalid links and nodes are removed according to the selected context at operation320. Context analysis module160may determine which links and nodes can be removed from a map due to the selected context. Context analysis module160may determine the validity of a link or a node by analyzing prior traffic data to identify patterns. For example, data collected from client devices105A-105N may indicate that traffic in a particular link becomes stationary at a particular time of a day or during heavy rainfall. In some embodiments, validity information may be provided for links and nodes that identifies particular contexts in which a link or node may be invalid.

Meshes are adjusted based on an updated map at operation330. In some embodiments, map module150receives a listing of invalid links and/or nodes from context analysis module160, and map module150removes any invalid links or nodes to generate an updated map. Partition module155may then adjust meshes for a partition layer of the map accordingly so that the partition layer is updated to reflect the removal of links and nodes. In some embodiments, partition module155may generate a partition layer that is specific to one or more contexts in the same manner that partition module155generates a partition layer using a static division method, except that the context-specific partition layer accounts for links and nodes that are invalid due to one or more contexts.

Operation340determines whether there are any remaining unprocessed contexts. If there are remaining contexts that have not yet been processed, a next context is selected for processing at operation310.

FIG. 4is a flow chart depicting a method400of providing a navigation service in accordance with an embodiment of the present invention.

A context is extracted for a trip at operation410. A context may include a time of day and/or a day of the week, a weather condition, a vehicle type, and a traffic quantity. Each context may be received by a client device, such as client device105A, for a particular trip. When a user provides a trip destination to a client device, navigation application130may send information relating to one or more contexts for the trip to trajectory analysis server140. For example, when a user initiates a trip via navigation application130, navigation application130may transmit user-provided information about the user's vehicle (e.g., weight, size, make and model information, etc.) as well as a destination to trajectory analysis server140. In some embodiments, each route is received from a client device, such as client devices105A-105N. The routes may share an origin and a destination, but may traverse different paths. For example, two routes may span from a first location to a second location, but may take different roadways in between.

Additionally, route data may be analyzed by map module150to identify a plurality of routes of users that share a same context, origin, and destination. The trajectories of routes may be assigned into a map by map module150, and coordinate sequences may be extracted for each trajectory that identify the meshes through which each trajectory passes. Thus, similar trajectories may be grouped together as members of a same pattern for the purpose of providing navigation services. When users share trajectories, the users may be provided with one or more navigation services that are based on a same partition layer of a map, thereby saving computing resources.

Operation420determines whether there is a partition layer for the context. If there is a partition layer for the context of the trip, then that context-specific partition layer is selected at operation440. Otherwise, a partition layer based on a static division method is selected at operation430.

The travel route is analyzed using the selected partition layer at operation450. The travel route may be analyzed by one or more navigation services based on the partition layer that is selected for the route. One or more computations may be performed for each mesh in the partition layer to provide a navigation service at operation460. In some embodiments, the computations for each mesh may be parallelized; since each mesh contains a same number of links and nodes, the processing requirements for each mesh are approximately equal. Navigation services may include services such as real-time danger avoidance and future traffic prediction. For example a mesh-by-mesh analysis of traffic conditions may enable a navigation service to anticipate traffic congestion and modify a route to avoid the identified congested area. In some embodiments, processed results may be stored for the identification of traffic patterns in the future in order to provide more accurate navigation services. One or more navigation services may analyze traffic trajectory patterns for each mesh by processing information relating to the trajectories of vehicles, which can be provided by client devices105A-105N. For example, each client device105A-105N may provide a location and/or a velocity for processing by trajectory analysis server140and its modules.

FIGS. 5A and 5Bare maps presented with partition layers in accordance with an embodiment of the present invention. Map500depicts a geographical area including an initial partition layer in which each mesh is a same size. For example, mesh505is the same size as every other mesh in the initial layer. Once the initial layer is processed according to presented embodiments, some meshes may be merged together to generate a partition layer. Map550depicts the same geographical area with a partition layer comprising meshes of various sizes. For example, while meshes555and560are different sizes, both meshes may contain a same number of links and/or nodes.

FIGS. 6A and 6Bare map representations presented with partition layers in accordance with an embodiment of the present invention. Map600depicts a geographical area including a partition layer that is produced according to a static division method, as presented herein. In contrast, map650depicts the same geographical area with a context-specific partition layer. The partition layer of map600may be processed to generate the context-specific partition layer of map650by removing links and nodes that are rendered invalid due to a particular context. For example, context analysis module160may determine that some links and/or nodes may be removed from mesh605and adjacent meshes, enabling partition module155to merge the meshes into a larger mesh655.

FIG. 7is a block diagram depicting components of a computer10suitable for executing the methods disclosed herein. Computer10may implement client devices105A-105N, trajectory analysis server140, and/or database server170in accordance with embodiments of the present invention. It should be appreciated thatFIG. 7provides only an illustration of one embodiment and does not imply any limitations with regard to the environments in which different embodiments may be implemented. Many modifications to the depicted environment may be made.

As depicted, the computer10includes communications fabric12, which provides communications between computer processor(s)14, memory16, persistent storage18, communications unit20, and input/output (I/O) interface(s)22. Communications fabric12can be implemented with any architecture designed for passing data and/or control information between processors (such as microprocessors, communications and network processors, etc.), system memory, peripheral devices, and any other hardware components within a system. For example, communications fabric12can be implemented with one or more buses.

Memory16and persistent storage18are computer readable storage media. In the depicted embodiment, memory16includes random access memory (RAM)24and cache memory26. In general, memory16can include any suitable volatile or non-volatile computer readable storage media.

One or more programs may be stored in persistent storage18for execution by one or more of the respective computer processors14via one or more memories of memory16. The persistent storage18may be a magnetic hard disk drive, a solid state hard drive, a semiconductor storage device, read-only memory (ROM), erasable programmable read-only memory (EPROM), flash memory, or any other computer readable storage media that is capable of storing program instructions or digital information.

The media used by persistent storage18may also be removable. For example, a removable hard drive may be used for persistent storage18. Other examples include optical and magnetic disks, thumb drives, and smart cards that are inserted into a drive for transfer onto another computer readable storage medium that is also part of persistent storage18.

Communications unit20, in these examples, provides for communications with other data processing systems or devices. In these examples, communications unit20includes one or more network interface cards. Communications unit20may provide communications through the use of either or both physical and wireless communications links.

I/O interface(s)22allows for input and output of data with other devices that may be connected to computer10. For example, I/O interface22may provide a connection to external devices28such as a keyboard, keypad, a touch screen, and/or some other suitable input device. External devices28can also include portable computer readable storage media such as, for example, thumb drives, portable optical or magnetic disks, and memory cards.

Software and data used to practice embodiments of the present invention can be stored on such portable computer readable storage media and can be loaded onto persistent storage18via I/O interface(s)22. I/O interface(s)22may also connect to a display30. Display30provides a mechanism to display data to a user and may be, for example, a computer monitor.

Data relating to providing navigation services using context-aware trajectory analysis (e.g., map information, context information, trajectory information, route information, navigation service information, vehicle information, etc.) may be stored within any conventional or other data structures (e.g., files, arrays, lists, stacks, queues, records, etc.) and may be stored in any desired storage unit (e.g., database, data or other repositories, queue, etc.). The data transmitted between client devices105A-105N, trajectory analysis server140, and/or database server170may include any desired format and arrangement, and may include any quantity of any types of fields of any size to store the data. The definition and data model for any datasets may indicate the overall structure in any desired fashion (e.g., computer-related languages, graphical representation, listing, etc.).

Data relating to providing navigation services using context-aware trajectory analysis (e.g., map information, context information, trajectory information, route information, navigation service information, vehicle information, etc.) may include any information provided to, or generated by, client devices105A-105N, trajectory analysis server140, and/or database server170. Data relating to providing navigation services using context-aware trajectory analysis may include any desired format and arrangement, and may include any quantity of any types of fields of any size to store any desired data. The data relating to providing navigation services using context-aware trajectory analysis may include any data collected about entities by any collection mechanism, any combination of collected information, and any information derived from analyzing collected information.

It will be appreciated that the embodiments described above and illustrated in the drawings represent only a few of the many ways of providing navigation services using context-aware trajectory analysis.

It is to be understood that the software (e.g., server software, networking software, navigation application130, map module150, partition module155, context analysis module160, etc.) of the present invention embodiments may be implemented in any desired computer language and could be developed by one of ordinary skill in the computer arts based on the functional descriptions contained in the specification and flow charts illustrated in the drawings. Further, any references herein of software performing various functions generally refer to computer systems or processors performing those functions under software control. The computer systems of the present invention embodiments may alternatively be implemented by any type of hardware and/or other processing circuitry.

The software of the present invention embodiments (e.g., server software, networking software, navigation application130, map module150, partition module155, context analysis module160, etc.) may be available on a non-transitory computer useable medium (e.g., magnetic or optical mediums, magneto-optic mediums, floppy diskettes, CD-ROM, DVD, memory devices, etc.) of a stationary or portable program product apparatus or device for use with stand-alone systems or systems connected by a network or other communications medium.