TECHNOLOGICAL FIELD

An example embodiment relates generally to processing probe information/data to generate and/or determine traffic and/or map information/data. An example embodiment relates generally to the determination of which probe trajectories of probe information/data to process to generate and/or determine traffic and/or map information/data.

BACKGROUND

Traffic and/or map information/data corresponding to a road network are often determined based on the processing of probe information/data captured by probe vehicles as they traverse portions of a road network. It can be computationally very expensive to process all of the probe information/data. Additionally, a significant portion of the probe information/data corresponds to a disproportionately small percentage of the road network. For example, a significant portion of the probe information/data corresponds to the most heavily traveled segments of the road network. Meanwhile, the probe information/data provides less coverage of less heavily traveled segments of the road network. Thus, reducing computational expense of processing the probe information/data by merely reducing the amount of probe information/data processed via random selection results in the coverage of the traffic and/or map information/data generated and/or determined from the processing of the randomly reduced to be diminished. In particular, the coverage of less heavily traveled segments of the road network is diminished.

BRIEF SUMMARY OF SOME EXAMPLE EMBODIMENTS

Various embodiments provide a technical solution to the technical problem of reducing the computational expense of generating and/or determining traffic and/or map information/data by processing probe information/data. Additionally, various embodiments provide a technical improvement to the increasing the resiliency of the traffic and/or map information/data determined by the processing of the probe information/data against deanonymization attacks.

Various embodiments provide methods, apparatus, systems, computer program products and/or the like configured to generating and/or determining traffic and/or map information/data based on probe information/data. For example, an analysis apparatus receives a plurality of instances of probe information/data from a plurality of probe apparatuses. The analysis apparatus links two or more instances of probe information/data (e.g., based on a session identifier associated with and/or provided as part of each instance of the two or more instances of probe information/data and/or the like) into a time-ordered sequence to generate a probe trajectory. A plurality of the generated probe trajectories are selected for analysis based on the desired coverage of the resulting traffic and/or map information/data and/or the computational resources available and/or slated for use in the generating and/or determining of the traffic and/or map information/data from the probe information/data. The selected probe trajectories may then be map-matched and analyzed to generate and/or determine the traffic and/or map information/data. Once the traffic and/or map information/data is determined, it may be provided to one or more consumer apparatuses. In various embodiments, a consumer apparatus may use the traffic and/or map information/data to perform one or more navigation functions. Some non-limiting examples of navigation functions include localization, route determination, lane level route determination, operating a vehicle along a lane level route, route travel time determination, lane maintenance, route guidance, lane level route guidance, provision of traffic information/data, provision of lane level traffic information/data, vehicle trajectory determination and/or guidance, vehicle speed and/or handling control, route and/or maneuver visualization, a low sensor quality mitigation function, and/or the like.

In various embodiments, the selection of the probe trajectories is performed based on the spatial familiarity of at least one instance of probe information/data of a probe trajectory. In an example embodiment, the selection of a probe trajectory is based on the least spatially familiar instance of probe information/data of the two or more instance of probe information/data that were linked to generate the probe trajectory. For example, a spatial familiarity score may be determined for each instance of probe information/data linked to generate the probe trajectory. The least familiar familiarity of the probe trajectory, which is the familiarity score associated with the instance of probe information/data of the probe trajectory having the familiarity score indicating the least amount of spatial familiarity, may then be used to determine whether the probe trajectory is to be selected or not. In an example embodiment, the determination of whether or not the probe trajectory is to be selected or not may be based on the comparison of the least familiar familiarity score of the probe trajectory with a selection threshold requirement. In an example embodiment, the determination of whether or not the probe trajectory is to be selected or not may be a probabilistic selection of probe trajectories, where probe trajectories having least familiar familiarity scores that indicate a lower level of familiarity are more likely to be selected compared to probe trajectories having least familiar familiarity scores that indicate a higher level of familiarity.

In various embodiments, each instance of probe information/data comprises location information/data indicating a location of a corresponding probe apparatus when the instance of probe information/data was captured and a timestamp indicating the date and/or time at which the instance of probe information/data was captured. In an example embodiment, the probe informatind/data comprises a session identifier configured to enable the analysis apparatus to link instances of probe information/data generated by the same probe apparatus and/or the same probe apparatus during a single trip and/or ignition cycle of a corresponding probe vehicle. In various embodiments, the instance of probe information/data may further comprise speed information/data indicating a travel speed of the probe apparatus, information/data captured by one or more sensors onboard the probe vehicle, a result of analysis of information/data captured by one or more sensors onboard the probe vehicle, and/or the like.

In various embodiments, the spatial familiarity score for an instance of probe information/data is determined based on a spatial familiarity model. For example, the probe trajectories may be selected in series, such that the spatial familiarity (e.g., similarity) between a particular probe trajectory (e.g., the instances of probe information/data thereof) being considered for selection may be determined based on the already selected probe trajectories. In an example embodiment, the spatial familiarity of an instance of probe information/data may be determined by comparing the location information/data of the instance of probe information/data to a familiarity and/or spatial coverage model corresponding to the already/previously selected probe trajectories. In an example embodiment, the familiarity and/or spatial coverage model is a tree data structure (e.g., a K-D tree). In an example embodiment, the familiarity and/or spatial coverage model is a grid model. For example, the location information/data of each already/previously selected probe trajectory is binned based on its proximity to a grid point. For example, as described above, the sampling of the space provided by the plurality of instances of probe information/data is non-uniform. This non-uniformity may be taken advantage of by binning the kernel density estimator. In an example embodiment, a linear binning approximation is used for kernel density estimation such that data points are redistributed along a fixed-size grid, so that the grid only stores a weight value for every grid point, where the weight is inversely proportional to how close a data point fell to that grid point. In various embodiments, the pairwise distances between the location information/data of an instance of probe information/data and the location information/data of each already/previously selected probe trajectory or grid point is transformed into a familiarity score using a kernel function. For example, the kernel function may be configured to provide spatial smoothing when estimating familiarity, in an example embodiment.

In various embodiments, only the selected probe trajectories are processed for use in generating and/or determining the traffic and/or map information/data. For example, the selected probe trajectories may be map-matched to a traversable map element (TME). In various embodiments, a TME may be a link or segment of road network (e.g., defined by an intersection and/or node located at each end of the link or road segment) or a traversable lane of a link or road segment of the road network. For example, each instance of probe information/data of a probe trajectory may be map-matched to a TME of a digital map that represents a road network. In an example embodiment, the probe trajectory is segmented into probe trajectory segments, wherein each probe trajectory segment includes the instances of probe information/data of the probe trajectory that were map-matched to the same TME. For example, a first probe trajectory segment includes the instances of probe information/data of the probe trajectory that were map-matched to a first TME. The probe trajectory segments may be binned and/or grouped based on the corresponding map-matched TME, and then each bin and/or group of probe trajectory segments may be analyzed to generate and/or determine traffic and/or map information/data for the corresponding TME. The traffic and/or map information/data corresponding to a TME may be provided by itself, packaged with traffic and/or map information/data corresponding to other TMEs, and/or packaged as a layer, for example, of a digital map and/or a digital map tile (e.g., a pre-defined portion of the digital map that represents a portion of the road network that corresponds to the TME to which the traffic and/or map information/data corresponds). As indicated above, the analysis apparatus may provide the traffic and/or map information/data (possibly as part of a digital map and/or digital map tile) such that one or more consumer apparatuses receive the traffic and/or map information/data such that at least one of the one or more consumer apparatuses may use the traffic and/or map information/data for performing one or more navigation functions.

In various embodiments, the selection process used to select the probe trajectories provides an improvement to the art. For example, the selection process ensures that an application specific appropriate level of coverage of the road network is provided by the generated and/or determined traffic and/or map information/data while reducing the computational resources required for generating and/or determining the traffic and/or map information/data and increasing the resiliency of the traffic and/or map information/data to deanonymization attacks.

In an example embodiment, a plurality of instances of probe data are received by an analysis apparatus. Each instance of probe data comprises location data indicating a location of a probe apparatus when the instance of probe data was generated and a timestamp indicating the date and/or time when the instance of probe data was generated. The analysis apparatus comprises a processor, memory, and a communication interface. The analysis apparatus generates a plurality of probe trajectories from the plurality of instances of probe data. A probe trajectory of the plurality of probe trajectories is generated by linking two or more instances of probe data corresponding to a same trip and time ordering the two or more instances of probe data based on the timestamp of each of the two or more instances of probe data. The analysis apparatus defines a set of selected probe trajectories. The set of selected probe trajectories is defined by determining a least familiar familiarity score for a first probe trajectory of the plurality of probe trajectories based on a familiarity model corresponding to instances of probe data of selected probe trajectories of the set of selected probe trajectories, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory, and when it is determined to select the first probe trajectory, adding the first probe trajectory to the set of selected probe trajectories. The analysis apparatus generated traffic and/or map data based on the set of selected probe trajectories. The analysis apparatus provides the traffic and/or map data such that a consumer apparatus receives the traffic and/or map data.

According to a first aspect of the present invention, a method is provided. In an example embodiment, the method comprises receiving, by an analysis apparatus, a plurality of instances of probe data. Each instance of probe data comprising location data indicating a location of a probe apparatus when the instance of probe data was generated and a timestamp indicating the date and/or time when the instance of probe data was generated. The analysis apparatus comprises a processor, memory, and a communication interface. The method further comprises generating, by the analysis apparatus, a plurality of probe trajectories from the plurality of instances of probe data. A probe trajectory of the plurality of probe trajectories is generated by linking two or more instances of probe data corresponding to a same trip and time ordering the two or more instances of probe data based on the timestamp of each of the two or more instances of probe data. The method further comprises defining, by the analysis apparatus, a set of selected probe trajectories. Defining the set of selected probe trajectories comprises determining a least familiar familiarity score for a first probe trajectory of the plurality of probe trajectories based on a familiarity model corresponding to instances of probe data of selected probe trajectories of the set of selected probe trajectories, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory, and when it is determined to select the first probe trajectory, adding the first probe trajectory to the set of selected probe trajectories. The method further comprises generating, by the analysis apparatus, traffic and/or map data based on the set of selected probe trajectories; and providing, by the analysis apparatus, the traffic and/or map data such that a consumer apparatus receives the traffic and/or map data.

In an example embodiment, the consumer apparatus is configured to use at least a portion of the traffic and/or map data to perform a navigation function. In an example embodiment, the familiarity model is a grid model. In an example embodiment, the traffic and/or map data is provided as part of a digital map or a tile of a digital map. In an example embodiment, the traffic and/or map data is generated by map-matching the selected probe trajectories of the set of selected probe trajectories. In an example embodiment, the traffic and/or map data comprises volume related traffic and/or map data which is determined by applying a correction factor that is determined based on a ratio of a density function of the plurality of instances of probe data to a density function of instances of probe data of selected probe trajectories of the set of selected probe trajectories. In an example embodiment, determining the least familiar familiarity score for the first probe trajectory comprises determining two or more familiarity scores, wherein each familiarity score of the two or more familiarity scores corresponds to an instance of probe data of the two or more instances or probe data linked to form the first probe trajectory; and identifying a least familiar familiarity score from the two or more familiarity scores. In an example embodiment, when it is determined to select the first probe trajectory, the familiarity model is updated based on the two or more instances of probe data of the first probe trajectory. In an example embodiment, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory comprises determining whether the least familiar familiarity score satisfies a familiarity threshold requirement. In an example embodiment, the familiarity threshold requirement is defined such that the traffic and/or map data has an application appropriate coverage of a corresponding road network. In an example embodiment, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory comprises assigning a selection probability to the first probe trajectory and determining whether to select the first probe trajectory based on the selection probability. In an example embodiment, the selection probability is assigned such that the traffic and/or map data has an application appropriate coverage of a corresponding road network.

According to another aspect of the present invention, an apparatus is provided. In an example embodiment, the apparatus comprises at least one processor, a communications interface configured for communicating via at least one network, and at least one memory storing computer program code. The at least one memory and the computer program code are configured to, with the processor, cause the apparatus to at least receive a plurality of instances of probe data. Each instance of probe data comprising location data indicating a location of a probe apparatus when the instance of probe data was generated and a timestamp indicating the date and/or time when the instance of probe data was generated. The at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to at least generate a plurality of probe trajectories from the plurality of instances of probe data. A probe trajectory of the plurality of probe trajectories is generated by linking two or more instances of probe data corresponding to a same trip and time ordering the two or more instances of probe data based on the timestamp of each of the two or more instances of probe data. The at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to at least define a set of selected probe trajectories by determining a least familiar familiarity score for a first probe trajectory of the plurality of probe trajectories based on a familiarity model corresponding to instances of probe data of selected probe trajectories of the set of selected probe trajectories, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory, and, when it is determined to select the first probe trajectory, adding the first probe trajectory to the set of selected probe trajectories. The at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to at least generate traffic and/or map data based on the set of selected probe trajectories; and provide the traffic and/or map data such that a consumer apparatus receives the traffic and/or map data.

In an example embodiment, the consumer apparatus is configured to use at least a portion of the traffic and/or map data to perform a navigation function. In an example embodiment, the familiarity model is a grid model. In an example embodiment, the traffic and/or map data is provided as part of a digital map or a tile of a digital map. In an example embodiment, the traffic and/or map data is generated by map-matching the selected probe trajectories of the set of selected probe trajectories. In an example embodiment, the traffic and/or map data comprises volume related traffic and/or map data which is determined by applying a correction factor that is determined based on a ratio of a density function of the plurality of instances of probe data to a density function of instances of probe data of selected probe trajectories of the set of selected probe trajectories. In an example embodiment, determining the least familiar familiarity score for the first probe trajectory comprises determining two or more familiarity scores, wherein each familiarity score of the two or more familiarity scores corresponds to an instance of probe data of the two or more instances or probe data linked to form the first probe trajectory; and identifying a least familiar familiarity score from the two or more familiarity scores. In an example embodiment, when it is determined to select the first probe trajectory, the familiarity model is updated based on the two or more instances of probe data of the first probe trajectory. In an example embodiment, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory comprises determining whether the least familiar familiarity score satisfies a familiarity threshold requirement. In an example embodiment, the familiarity threshold requirement is defined such that the traffic and/or map data has an application appropriate coverage of a corresponding road network. In an example embodiment, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory comprises assigning a selection probability to the first probe trajectory and determining whether to select the first probe trajectory based on the selection probability. In an example embodiment, the selection probability is assigned such that the traffic and/or map data has an application appropriate coverage of a corresponding road network.

In still another aspect of the present invention, a computer program product is provided. In an example embodiment, the computer program product comprises at least one non-transitory computer-readable storage medium having computer-readable program code portions stored therein. The computer-readable program code portions comprise executable portions configured, when executed by a processor of an apparatus, to cause the apparatus to receive a plurality of instances of probe data. Each instance of probe data comprising location data indicating a location of a probe apparatus when the instance of probe data was generated and a timestamp indicating the date and/or time when the instance of probe data was generated. The computer-readable program code portions further comprise executable portions configured, when executed by a processor of an apparatus, to cause the apparatus to generate a plurality of probe trajectories from the plurality of instances of probe data. A probe trajectory of the plurality of probe trajectories is generated by linking two or more instances of probe data corresponding to a same trip and time ordering the two or more instances of probe data based on the timestamp of each of the two or more instances of probe data. The computer-readable program code portions further comprise executable portions configured, when executed by a processor of an apparatus, to cause the apparatus to define a set of selected probe trajectories by determining a least familiar familiarity score for a first probe trajectory of the plurality of probe trajectories based on a familiarity model corresponding to instances of probe data of selected probe trajectories of the set of selected probe trajectories, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory, and, when it is determined to select the first probe trajectory, adding the first probe trajectory to the set of selected probe trajectories. The computer-readable program code portions further comprise executable portions configured, when executed by a processor of an apparatus, to cause the apparatus to generate traffic and/or map data based on the set of selected probe trajectories; and provide the traffic and/or map data such that a consumer apparatus receives the traffic and/or map data.

In an example embodiment, the consumer apparatus is configured to use at least a portion of the traffic and/or map data to perform a navigation function. In an example embodiment, the familiarity model is a grid model. In an example embodiment, the traffic and/or map data is provided as part of a digital map or a tile of a digital map. In an example embodiment, the traffic and/or map data is generated by map-matching the selected probe trajectories of the set of selected probe trajectories. In an example embodiment, the traffic and/or map data comprises volume related traffic and/or map data which is determined by applying a correction factor that is determined based on a ratio of a density function of the plurality of instances of probe data to a density function of instances of probe data of selected probe trajectories of the set of selected probe trajectories. In an example embodiment, determining the least familiar familiarity score for the first probe trajectory comprises determining two or more familiarity scores, wherein each familiarity score of the two or more familiarity scores corresponds to an instance of probe data of the two or more instances or probe data linked to form the first probe trajectory; and identifying a least familiar familiarity score from the two or more familiarity scores. In an example embodiment, when it is determined to select the first probe trajectory, the familiarity model is updated based on the two or more instances of probe data of the first probe trajectory. In an example embodiment, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory comprises determining whether the least familiar familiarity score satisfies a familiarity threshold requirement. In an example embodiment, the familiarity threshold requirement is defined such that the traffic and/or map data has an application appropriate coverage of a corresponding road network. In an example embodiment, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory comprises assigning a selection probability to the first probe trajectory and determining whether to select the first probe trajectory based on the selection probability. In an example embodiment, the selection probability is assigned such that the traffic and/or map data has an application appropriate coverage of a corresponding road network.

According to yet another aspect of the present invention, an apparatus is provided. In an example embodiment, the apparatus comprises a processor, a memory, and a communication interface configured to communicate via at least one network. In an example embodiment, the apparatus comprises means for receiving a plurality of instances of probe data. Each instance of probe data comprising location data indicating a location of a probe apparatus when the instance of probe data was generated and a timestamp indicating the date and/or time when the instance of probe data was generated. In an example embodiment, the apparatus comprises means for generating a plurality of probe trajectories from the plurality of instances of probe data. A probe trajectory of the plurality of probe trajectories is generated by linking two or more instances of probe data corresponding to a same trip and time ordering the two or more instances of probe data based on the timestamp of each of the two or more instances of probe data. In an example embodiment, the apparatus comprises means for defining a set of selected probe trajectories. Defining the set of selected probe trajectories comprises determining a least familiar familiarity score for a first probe trajectory of the plurality of probe trajectories based on a familiarity model corresponding to instances of probe data of selected probe trajectories of the set of selected probe trajectories, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory, and when it is determined to select the first probe trajectory, adding the first probe trajectory to the set of selected probe trajectories. In an example embodiment, the apparatus comprises means for generating traffic and/or map data based on the set of selected probe trajectories. In an example embodiment, the apparatus comprises means for providing the traffic and/or map data such that a consumer apparatus receives the traffic and/or map data.

According to yet another aspect of the present invention, a component of an apparatus is provided. In an example embodiment, the component comprises a computer-readable medium. In an example embodiment, the component comprises a digital map stored on the computer-readable medium. The digital map comprises a first plurality of data records. Each of the first plurality of data records represents a corresponding TME. At least some of the first plurality of data records further comprise traffic and/or map data for the corresponding TME generated by receiving, by an analysis apparatus, a plurality of instances of probe data, each instance of probe data comprising location data indicating a location of a probe apparatus when the instance of probe data was generated and a timestamp indicating the date and/or time when the instance of probe data was generated; generating, by the analysis apparatus, a plurality of probe trajectories from the plurality of instances of probe data, wherein a probe trajectory of the plurality of probe trajectories is generated by linking two or more instances of probe data corresponding to a same trip and time ordering the two or more instances of probe data based on the timestamp of each of the two or more instances of probe data; defining, by the analysis apparatus, a set of selected probe trajectories, wherein defining the set of selected probe trajectories comprises determining a least familiar familiarity score for a first probe trajectory of the plurality of probe trajectories based on a familiarity model corresponding to instances of probe data of selected probe trajectories of the set of selected probe trajectories, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory, and when it is determined to select the first probe trajectory, adding the first probe trajectory to the set of selected probe trajectories; map matching one or more probe trajectory segments corresponding to one or more probe trajectories of the set of selected probe trajectories to the corresponding TME; and generating, by the analysis apparatus, traffic and/or map data for the corresponding TME based on the one or more probe trajectory segments map-matched to the corresponding TME.

In an example embodiment, the traffic and/or map data is configured for use in perform a navigation function. In an example embodiment, the familiarity model is a grid model. In an example embodiment, the traffic and/or map data is generated by map-matching the selected probe trajectories of the set of selected probe trajectories. In an example embodiment, the traffic and/or map data comprises volume related traffic and/or map data which is determined by applying a correction factor that is determined based on a ratio of a density function of the plurality of instances of probe data to a density function of instances of probe data of selected probe trajectories of the set of selected probe trajectories. In an example embodiment, determining the least familiar familiarity score for the first probe trajectory comprises determining two or more familiarity scores, wherein each familiarity score of the two or more familiarity scores corresponds to an instance of probe data of the two or more instances or probe data linked to form the first probe trajectory; and identifying a least familiar familiarity score from the two or more familiarity scores. In an example embodiment, when it is determined to select the first probe trajectory, the familiarity model is updated based on the two or more instances of probe data of the first probe trajectory. In an example embodiment, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory comprises determining whether the least familiar familiarity score satisfies a familiarity threshold requirement. In an example embodiment, the familiarity threshold requirement is defined such that the traffic and/or map data has an application appropriate coverage of a corresponding road network. In an example embodiment, determining whether to select the first probe trajectory based on the least familiar familiarity score for the first probe trajectory comprises assigning a selection probability to the first probe trajectory and determining whether to select the first probe trajectory based on the selection probability. In an example embodiment, the selection probability is assigned such that the traffic and/or map data has an application appropriate coverage of a corresponding road network.

