DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Status of Claims
This action is in reply to the patent application filed on January 8, 2025.
Claims 1-20 are currently pending and have been examined.
This action is made Non-FINAL.
The examiner would like to note that this application is being handled by examiner Christine Huynh.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claim(s) 1-4, 6-10, 12-16, and 20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Linder et al. (US 20190360818 A1) in view of Li (CN 109059939 A).
Regarding claims 1-4, 6-10, 12-16, and 20:
With respect to claims 1 and 8, Linder teaches:
receiving raw trajectory data comprising a collection of data points from a location tracking system, the raw trajectory data representing a trajectory of a moving target on a mapped area; (“The apparatus of some embodiments may be caused to receive a probe data point including a location;” [0007], “By way of example, the map data service provider can collect geographic data and dynamic data to generate and enhance the map database 110 and dynamic data such as traffic-related data contained therein. There can be different ways used by the map developer to collect data. These ways can include obtaining data from other sources, such as municipalities or respective geographic authorities, such as via global information system databases. In addition, the map developer can employ field personnel to travel by vehicle along roads throughout the geographic region to observe features and/or record information about them, for example. Also, remote sensing, such as aerial or satellite photography and/or LIDAR, can be used to generate map geometries directly or through machine learning as described herein. However, the most ubiquitous form of data that may be available is vehicle data provided by vehicles, such as mobile device 104, as they travel the roads throughout a region.” [0036]), where a collection of data points from location tracking systems, such as a GPS, are collected. The collected data represents a trajectory of a moving target on a mapped area, such as a vehicle.
receiving road network data of the mapped area, the road network data comprising road segments across a path of the trajectory; (“The map data service provider may include a map database 110 that may include node data, road segment data or link data, point of interest (POI) data, traffic data or the like. The map database 110 may also include cartographic data, routing data, and/or maneuvering data. According to some example embodiments, the road segment data records may be links or segments representing roads, streets, or paths, as may be used in calculating a route or recorded route information for determination of one or more personalized routes. The node data may be end points corresponding to the respective links or segments of road segment data. The road link data and the node data may represent a road network, such as used by vehicles, cars, trucks, buses, motorcycles, and/or other entities.” [0035], “As shown in FIG. 3, a link is obtained from among a list of links at 150. The list of links may be a list of road links for a geographical region stored, for example, in map database 110.” [0043]), this shows that road network data of a mapped area is acquired.
partitioning the raw trajectory data to trajectory segments of a maximum length l; (“A link from the list of links is obtained at 150 and vertices along the link are identified at 155. Identifying vertices along the length of the link, as described further below, involves identifying points along the link that are spaced apart from a prior point along the link by a predefined distance, beginning with an end point or node of the link, and ending at the opposite end point or node.” [0043], “Spatial searches are computationally expensive. For example, probe-centric map matching techniques for large probe data sets, such as millions of probe points, can incur substantial execution time and costs since the number of spatial searches is proportional to the number of probe points.” [0006], “For each link, the link is divided into sub-sections according to the points established along the link, spaced apart by boundary separation distance (S). At each point, a spatial boundary may be generated to capture probe data points within the spatial boundary for quick and efficient map matching of the probe data points. FIG. 4 illustrates a road link 200 that extends between nodes 215 and includes vertex points 205 that divide the link 200 into sub-segments between the points.” [0051]), where the data is spaced apart from a prior point along the link by a predefined distance.
partitioning the road network data into spatially indexed shards, each spatially indexed shard corresponding to a defined geographical region around a respective one of the trajectory segments; (“Identifying vertices along a length of the road link which essentially divides the link into a plurality of sub-segments may be performed according to a particular distance or length of each sub-segment or a distance between each identified vertex. In an instance in which a road link is a straight line, point latitude and longitude for each vertex may be computed at increments of a distance (S) along the link. Given the initial point latitude and longitude of the starting point or node of the link, all points along the link can be computed proceeding in the same direction along the link at the set distance (S) between the vertices/points.” [0044], “As shown in FIG. 3, a link is obtained from among a list of links at 150. The list of links may be a list of road links for a geographical region stored, for example, in map database 110.” [0043], “As noted above, embodiments described herein may compile geographic data into a physical storage format (PSF) to organize and/or configure the data for performing navigation-related functions and/or services. This may include representing a geographical area with tiles, where the region in the map database is divided into and stored as a plurality of tiles. Each road link may be associated with the tile in which it is found or a reference point of the road link is found” [0049], and 155 of FIG. 3), shows partitioning the road link into spatially indexed lengths. The corresponding geographical data of the road links are stored.
performing a distributed spatial distance join between the trajectory segments and the partitioned road network data, wherein performing the distributed spatial distance join comprises selecting road segments from the partitioned road network data located within a distance D from each trajectory segment so that the selected road segments are a subgroup of the partitioned road network data; (160 in FIG. 3, 330 in FIG. 5, “For each link, the link is divided into sub-sections according to the points established along the link, spaced apart by boundary separation distance (S). At each point, a spatial boundary may be generated to capture probe data points within the spatial boundary for quick and efficient map matching of the probe data points. FIG. 4 illustrates a road link 200 that extends between nodes 215 and includes vertex points 205 that divide the link 200 into sub-segments between the points.” [0051]), where a spatial boundary may be generated to capture probe data points within the spatial boundary.
assembling the trajectory from the trajectory segments; (“Referring again to FIG. 5, a probe data point may be received at 350 including a location represented by the probe data point. The probe data point may be received from a probe representing the location of a vehicle, and may be received via communications interface 16 before being processed by processor 12 of apparatus 10, for example. At 360, a spatial boundary for a road link may be determined in which the probe data point is located. This determination may be made based on one or more road links and their associated spatial boundaries being retrieved based on a map tile or portion thereof in which the probe data point is determined to be located, while a more refined road link determination may be made based no which of those road links include the location of the probe data point within their spatial boundary.” [0058]), where the spatial boundary for a road link may be determined in which the probe data point is located based on the map tile.
performing a map matching operation using the assembled trajectory and the selected road segments to produce a path on the mapped area that best aligns with the path of the trajectory; (370 in FIG. 5, “At 370, the probe data point is map-matched with the road link within whose spatial boundary region the probe data point location falls.” [0058], “One a probe data point has been map matched to a particular road link, according to some embodiments, the probe data point may be projected onto the road link. This projection may at least partially mitigate GPS or locationing error in the probe data point location. As locationing means often have error, probe data points may not fall directly on a road segment, such that map matching may help align the probe data points with an identified and mapped road link represented by a poly line.” [0059]), where a map matching operation is performed to produce a path on the mapped area that aligns with the path of the trajectory.
However, Linder does not teach distributing map matching between a plurality of machines, but Li teaches (“The technology of the present invention can be deployed to one or more machines, and the same set of calculation results and map data can be shared between multiple machines, and can be split at any time. You can group multiple map matching sequences into one machine, or you can split a very large number of matching sequences onto multiple machines. At the same time, it can heat expand or reduce machine nodes, which is convenient for multiple calculation operations.” (21)), where a plurality of machines can be used. While Linder teaches a processor, Li teaches computation and data being split between multiple processors. Thus, it would have been obvious to a person of ordinary skill in the art where the plurality of machines includes a primary machine in an attempt to provide an improved system or method, as a person with ordinary skill has good reason to pursue the known options within his or her technical grasp. In turn, because the product as claimed has the properties predicted by the prior art, it would have been obvious to make the system or product where there is a master machine.
It would have been obvious to one of ordinary skill in the art before the effective filling date of the instant application to have combined Linder’s offline map matching with Li’s plurality of machines because (“You can group multiple map matching sequences into one machine, or you can split a very large number of matching sequences onto multiple machines. At the same time, it can heat expand or reduce machine nodes, which is convenient for multiple calculation operations.” See Li (21)).
With respect to claim 2, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 1. The combination of Linder and Li teaches offline map matching of claim 1. Linder further teaches:
wherein performing the map matching operation comprises setting a maximum probe distance for matching the trajectory data to the selected road segments; (“In order to ensure that the spatial area represented by the geometric shapes (polygons, circles, ellipses, etc.) captures probe data points that should be map matched to the associated road link, the spatial boundary separation distance (S) that defines the separation distance along the road link between neighboring vertices may be at least partially based on a map matching tolerance T, that is, the predefined distance within which a probe point should be map-matched to a polyline.” [0052]), where the probe distance is comparable to tolerance T, as it is the predefined distance within which a probe point should be map-matched to a polyline.
With respect to claim 3, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 2. The combination of Linder and Li teaches offline map matching of claim 2. Linder further teaches:
wherein the distance D is a hyperparameter selected to match the maximum probe distance; (“In order to ensure that the spatial area represented by the geometric shapes (polygons, circles, ellipses, etc.) captures probe data points that should be map matched to the associated road link, the spatial boundary separation distance (S) that defines the separation distance along the road link between neighboring vertices may be at least partially based on a map matching tolerance T… In this regard, the distance shown as 220 is greater than the tolerance T, and the spatial boundary separation distance S may be determined from the equation: RB2=T2+(S/2)2 as S=2(RB2− T2)1/2, where RB is the radius of the circular boundary region 210. As such, the probe data points that are within a perpendicular distance D shown as 220 of the road link 200 will be map matched to the road link. The probe data points will fall into one, or possibly two of the boundary regions 210.” [0052]), where the distance is based on the probe distance.
With respect to claim 4, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 1. The combination of Linder and Li teaches offline map matching of claim 1. Linder further teaches:
wherein performing the map matching operation comprises a Hidden Markov Model-based approach; (“The probabilistic map-matching algorithms may include, for example, Viterbi and hidden Markov model techniques.” [0004]).
With respect to claim 6, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 1. The combination of Linder and Li teaches offline map matching of claim 1. Linder further teaches:
wherein the raw trajectory data represent coordinates from a global positioning system (GPS); (“The apparatus of an example embodiment may be embodied by a variety of computing devices including, for example, such as a navigation system, an advanced driver assistance system (ADAS), a GPS system or the like.” [0026], “By way of example, the map data service provider can collect geographic data and dynamic data to generate and enhance the map database 110 and dynamic data such as traffic-related data contained therein.” [0036]), where data is collected from GPS information.
With respect to claim 7, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 1. The combination of Linder and Li teaches offline map matching of claim 1. Linder further teaches:
wherein partitioning the raw trajectory data comprises selecting the maximum length l so that a number of road segments near the trajectory segments is balanced with a time cost incurred when assembling the trajectory segments back to the trajectory; (“Spatial searches are computationally expensive. For example, probe-centric map matching techniques for large probe data sets, such as millions of probe points, can incur substantial execution time and costs since the number of spatial searches is proportional to the number of probe points.” [0006], “For each link, the link is divided into sub-sections according to the points established along the link, spaced apart by boundary separation distance (S). At each point, a spatial boundary may be generated to capture probe data points within the spatial boundary for quick and efficient map matching of the probe data points. FIG. 4 illustrates a road link 200 that extends between nodes 215 and includes vertex points 205 that divide the link 200 into sub-segments between the points.” [0051]), where the data can be divided in a way for quick and efficient map matching of the probe data points. Thus, it would have been obvious to a person of ordinary skill in the art to select a maximum length so that the number of road segments is balanced with a time cost incurred in an attempt to provide an improved system or method, as a person with ordinary skill has good reason to pursue the known options within his or her technical grasp. In turn, because the product as claimed has the properties predicted by the prior art, it would have been obvious to make the system or product where the number of road segments is balanced with a time cost incurred.
With respect to claim 9, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 8. The combination of Linder and Li teaches offline map matching of claim 8. Linder further teaches:
wherein the distance D is a hyperparameter selected to match a maximum probe distance used when matching the raw trajectory data to the selected road segments during the map matching operation; (“In order to ensure that the spatial area represented by the geometric shapes (polygons, circles, ellipses, etc.) captures probe data points that should be map matched to the associated road link, the spatial boundary separation distance (S) that defines the separation distance along the road link between neighboring vertices may be at least partially based on a map matching tolerance T, that is, the predefined distance within which a probe point should be map-matched to a polyline.” [0052]), where the probe distance is comparable to tolerance T, as it is the predefined distance within which a probe point should be map-matched to a polyline. (“In this regard, the distance shown as 220 is greater than the tolerance T, and the spatial boundary separation distance S may be determined from the equation: RB2=T2+(S/2)2 as S=2(RB2− T2)1/2, where RB is the radius of the circular boundary region 210. As such, the probe data points that are within a perpendicular distance D shown as 220 of the road link 200 will be map matched to the road link. The probe data points will fall into one, or possibly two of the boundary regions 210.” [0052]), where the distance is based on the probe distance.
With respect to claim 10, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 9. The combination of Linder and Li teaches offline map matching of claim 9. Linder further teaches:
wherein to perform the map matching operation comprises a Hidden Markov Model-based approach; (“The probabilistic map-matching algorithms may include, for example, Viterbi and hidden Markov model techniques.” [0004]).
With respect to claim 12, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 9. The combination of Linder and Li teaches offline map matching of claim 9. Linder further teaches:
wherein the raw trajectory data are represented as an ordered list of tuples; (“As shown in FIG. 3, a link is obtained from among a list of links at 150. The list of links may be a list of road links for a geographical region stored, for example, in map database 110.”, “The probe data points may be put into a computationally efficient spatial data structure such as, for example, a k-d-tree to optimize the map-matching of determining a boundary region into which a probe data point falls.” [0056]), where the collected data is organized in a data structure such as a list, which is comparable to being organized in tuples.
With respect to claim 13, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 9. The combination of Linder and Li teaches offline map matching of claim 9. Linder further teaches:
wherein the raw trajectory data contain latitude, longitude, and timestamp information; (“Probe points are frequently captured by global positioning systems (“GPS”), navigation systems or the like. Each probe point is associated with a location, such as may be expressed in terms of latitude and longitude. Some probe points are also associated with a heading and a speed at which the GPS system or the navigation system was moving at the time at which the probe point was captured.” [0002]), where the data collected from the GPS include latitude and longitude and the time which the point was captured.
With respect to claim 14, Linder teaches:
instructing the master machine to obtain raw trajectory data from one or more external sources over a network, the raw trajectory data comprising a collection of coordinates and timestamps from a location tracking system, the raw trajectory data representing a trajectory of a moving target on a mapped area; (“The apparatus of some embodiments may be caused to receive a probe data point including a location;” [0007], “By way of example, the map data service provider can collect geographic data and dynamic data to generate and enhance the map database 110 and dynamic data such as traffic-related data contained therein. There can be different ways used by the map developer to collect data. These ways can include obtaining data from other sources, such as municipalities or respective geographic authorities, such as via global information system databases. In addition, the map developer can employ field personnel to travel by vehicle along roads throughout the geographic region to observe features and/or record information about them, for example. Also, remote sensing, such as aerial or satellite photography and/or LIDAR, can be used to generate map geometries directly or through machine learning as described herein. However, the most ubiquitous form of data that may be available is vehicle data provided by vehicles, such as mobile device 104, as they travel the roads throughout a region.” [0036]), where a collection of data points from location tracking systems, such as a GPS, are collected. The collected data represents a trajectory of a moving target on a mapped area, such as a vehicle.
However, Linder does not teach a master machine, but Li teaches (“The technology of the present invention can be deployed to one or more machines, and the same set of calculation results and map data can be shared between multiple machines, and can be split at any time. You can group multiple map matching sequences into one machine, or you can split a very large number of matching sequences onto multiple machines. At the same time, it can heat expand or reduce machine nodes, which is convenient for multiple calculation operations.” (21)), where a plurality of machines can be used. While Linder teaches a processor, Li teaches computation and data being split between multiple processors. Thus, it would have been obvious to a person of ordinary skill in the art where the plurality of machines includes a primary machine in an attempt to provide an improved system or method, as a person with ordinary skill has good reason to pursue the known options within his or her technical grasp. In turn, because the product as claimed has the properties predicted by the prior art, it would have been obvious to make the system or product where there is a master machine.
instructing the master machine to obtain road network data for the mapped area from one or more external sources over the network, the road network data comprising road segments in the vicinity of the trajectory; (“The map data service provider may include a map database 110 that may include node data, road segment data or link data, point of interest (POI) data, traffic data or the like. The map database 110 may also include cartographic data, routing data, and/or maneuvering data. According to some example embodiments, the road segment data records may be links or segments representing roads, streets, or paths, as may be used in calculating a route or recorded route information for determination of one or more personalized routes. The node data may be end points corresponding to the respective links or segments of road segment data. The road link data and the node data may represent a road network, such as used by vehicles, cars, trucks, buses, motorcycles, and/or other entities.” [0035], “As shown in FIG. 3, a link is obtained from among a list of links at 150. The list of links may be a list of road links for a geographical region stored, for example, in map database 110.” [0043]), this shows that road network data of a mapped area is acquired.
instructing the master machine to partition the raw trajectory data into trajectory segments of a maximum length l; (“A link from the list of links is obtained at 150 and vertices along the link are identified at 155. Identifying vertices along the length of the link, as described further below, involves identifying points along the link that are spaced apart from a prior point along the link by a predefined distance, beginning with an end point or node of the link, and ending at the opposite end point or node.” [0043]), where the data is spaced apart from a prior point along the link by a predefined distance.
instructing the master machine to partition the road network data into spatially indexed shards, each spatially indexed shard corresponding to a defined geographical region around a respective one of the trajectory segments; (“Identifying vertices along a length of the road link which essentially divides the link into a plurality of sub-segments may be performed according to a particular distance or length of each sub-segment or a distance between each identified vertex. In an instance in which a road link is a straight line, point latitude and longitude for each vertex may be computed at increments of a distance (S) along the link. Given the initial point latitude and longitude of the starting point or node of the link, all points along the link can be computed proceeding in the same direction along the link at the set distance (S) between the vertices/points.” [0044], “As shown in FIG. 3, a link is obtained from among a list of links at 150. The list of links may be a list of road links for a geographical region stored, for example, in map database 110.” [0043], “As noted above, embodiments described herein may compile geographic data into a physical storage format (PSF) to organize and/or configure the data for performing navigation-related functions and/or services. This may include representing a geographical area with tiles, where the region in the map database is divided into and stored as a plurality of tiles. Each road link may be associated with the tile in which it is found or a reference point of the road link is found” [0049], and 155 of FIG. 3), shows partitioning the road link into spatially indexed lengths. The corresponding geographical data of the road links are stored.
Linder does not teach, but Li teaches:
instructing the master machine to distribute the trajectory segments and the partitioned road network data across the two or more worker machines; (“the observation state is a GPS coordinate acquired by the device, and the GPS point is centered, and the circle is drawn with a specified or dynamic radius, and all the roads in the circle are To make a vertical line, the intersection of the vertical line and the road is the possible actual position. The K-nearest nearest neighbor method can be used to estimate several possible actual states, and a true observation state to obtain the vehicle's trajectory sequence S.” (12), “The technology of the present invention can be deployed to one or more machines, and the same set of calculation results and map data can be shared between multiple machines, and can be split at any time. You can group multiple map matching sequences into one machine, or you can split a very large number of matching sequences onto multiple machines. At the same time, it can heat expand or reduce machine nodes, which is convenient for multiple calculation operations.” (21)), where a plurality of machines can be used. While Linder teaches a processor, Li teaches computation and data being split between multiple processors. Thus, it would have been obvious to a person of ordinary skill in the art where the plurality of machines includes a primary machine and worker machines in an attempt to provide an improved system or method, as a person with ordinary skill has good reason to pursue the known options within his or her technical grasp. In turn, because the product as claimed has the properties predicted by the prior art, it would have been obvious to make the system or product where there is a master machine and worker machines.
It would have been obvious to one of ordinary skill in the art before the effective filling date of the instant application to have combined Linder’s offline map matching with Li’s plurality of machines because (“You can group multiple map matching sequences into one machine, or you can split a very large number of matching sequences onto multiple machines. At the same time, it can heat expand or reduce machine nodes, which is convenient for multiple calculation operations.” See Li (21)).
Linder in combination with Li further teaches:
instructing the master machine to perform a distributed spatial distance join between the trajectory segments and the partitioned road network data, wherein performing the distributed spatial distance join comprises instructing the two or more worker machines to select road segments from the partitioned road network data located within a distance D from each trajectory segment so that the selected road segments form a subgroup of the partitioned road network data; (160 in FIG. 3, 330 in FIG. 5, “For each link, the link is divided into sub-sections according to the points established along the link, spaced apart by boundary separation distance (S). At each point, a spatial boundary may be generated to capture probe data points within the spatial boundary for quick and efficient map matching of the probe data points. FIG. 4 illustrates a road link 200 that extends between nodes 215 and includes vertex points 205 that divide the link 200 into sub-segments between the points.” [0051]), where a spatial boundary may be generated to capture probe data points within the spatial boundary.
instructing the master machine to assemble the trajectory from the trajectory segments; (“Referring again to FIG. 5, a probe data point may be received at 350 including a location represented by the probe data point. The probe data point may be received from a probe representing the location of a vehicle, and may be received via communications interface 16 before being processed by processor 12 of apparatus 10, for example. At 360, a spatial boundary for a road link may be determined in which the probe data point is located. This determination may be made based on one or more road links and their associated spatial boundaries being retrieved based on a map tile or portion thereof in which the probe data point is determined to be located, while a more refined road link determination may be made based no which of those road links include the location of the probe data point within their spatial boundary.” [0058]), where the spatial boundary for a road link may be determined in which the probe data point is located based on the map tile.
instructing the two or more worker machines to perform a map matching operation using the assembled trajectory and the selected road segments to produce a path on the mapped area that best aligns with a path of the trajectory; (370 in FIG. 5, “At 370, the probe data point is map-matched with the road link within whose spatial boundary region the probe data point location falls.” [0058], “One a probe data point has been map matched to a particular road link, according to some embodiments, the probe data point may be projected onto the road link. This projection may at least partially mitigate GPS or locationing error in the probe data point location. As locationing means often have error, probe data points may not fall directly on a road segment, such that map matching may help align the probe data points with an identified and mapped road link represented by a poly line.” [0059]), where a map matching operation is performed to produce a path on the mapped area that aligns with the path of the trajectory.
With respect to claim 15, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 14. The combination of Linder and Li teaches offline map matching of claim 14. Linder further teaches:
wherein the distance D is a hyperparameter defined in the master machine and communicated to the two or more worker machines prior to instructing the two or more worker machines to select road segments from the partitioned road network data; (“where the probe distance is comparable to tolerance T, as it is the predefined distance within which a probe point should be map-matched to a polyline. (“In this regard, the distance shown as 220 is greater than the tolerance T, and the spatial boundary separation distance S may be determined from the equation: RB2=T2+(S/2)2 as S=2(RB2− T2)1/2, where RB is the radius of the circular boundary region 210. As such, the probe data points that are within a perpendicular distance D shown as 220 of the road link 200 will be map matched to the road link. The probe data points will fall into one, or possibly two of the boundary regions 210.” [0052]), where the distance is based on the probe distance.
Linder does not teach master and worker machines, but Li teaches (“the observation state is a GPS coordinate acquired by the device, and the GPS point is centered, and the circle is drawn with a specified or dynamic radius, and all the roads in the circle are To make a vertical line, the intersection of the vertical line and the road is the possible actual position. The K-nearest nearest neighbor method can be used to estimate several possible actual states, and a true observation state to obtain the vehicle's trajectory sequence S.” (12), “The technology of the present invention can be deployed to one or more machines, and the same set of calculation results and map data can be shared between multiple machines, and can be split at any time. You can group multiple map matching sequences into one machine, or you can split a very large number of matching sequences onto multiple machines. At the same time, it can heat expand or reduce machine nodes, which is convenient for multiple calculation operations.” (21)), where a plurality of machines can be used. While Linder teaches a processor, Li teaches computation and data being split between multiple processors. Thus, it would have been obvious to a person of ordinary skill in the art where the plurality of machines includes a primary machine and worker machines in an attempt to provide an improved system or method, as a person with ordinary skill has good reason to pursue the known options within his or her technical grasp. In turn, because the product as claimed has the properties predicted by the prior art, it would have been obvious to make the system or product where there is a master machine and worker machines.
It would have been obvious to one of ordinary skill in the art before the effective filling date of the instant application to have combined Linder’s offline map matching with Li’s plurality of machines because (“You can group multiple map matching sequences into one machine, or you can split a very large number of matching sequences onto multiple machines. At the same time, it can heat expand or reduce machine nodes, which is convenient for multiple calculation operations.” See Li (21)).
With respect to claim 16, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 15. The combination of Linder and Li teaches offline map matching of claim 15. Linder further teaches:
wherein the distance D is set to be equal to match a maximum probe distance used when matching the raw trajectory data to the selected road segments by the two or more worker machines during the map matching operation; (“In order to ensure that the spatial area represented by the geometric shapes (polygons, circles, ellipses, etc.) captures probe data points that should be map matched to the associated road link, the spatial boundary separation distance (S) that defines the separation distance along the road link between neighboring vertices may be at least partially based on a map matching tolerance T, that is, the predefined distance within which a probe point should be map-matched to a polyline.” [0052]), where the probe distance is comparable to tolerance T, as it is the predefined distance within which a probe point should be map-matched to a polyline.
Linder does not teach master and worker machines, but Li teaches (“the observation state is a GPS coordinate acquired by the device, and the GPS point is centered, and the circle is drawn with a specified or dynamic radius, and all the roads in the circle are To make a vertical line, the intersection of the vertical line and the road is the possible actual position. The K-nearest nearest neighbor method can be used to estimate several possible actual states, and a true observation state to obtain the vehicle's trajectory sequence S.” (12), “The technology of the present invention can be deployed to one or more machines, and the same set of calculation results and map data can be shared between multiple machines, and can be split at any time. You can group multiple map matching sequences into one machine, or you can split a very large number of matching sequences onto multiple machines. At the same time, it can heat expand or reduce machine nodes, which is convenient for multiple calculation operations.” (21)), where a plurality of machines can be used. While Linder teaches a processor, Li teaches computation and data being split between multiple processors. Thus, it would have been obvious to a person of ordinary skill in the art where the plurality of machines includes a primary machine and worker machines in an attempt to provide an improved system or method, as a person with ordinary skill has good reason to pursue the known options within his or her technical grasp. In turn, because the product as claimed has the properties predicted by the prior art, it would have been obvious to make the system or product where there is a master machine and worker machines.
It would have been obvious to one of ordinary skill in the art before the effective filling date of the instant application to have combined Linder’s offline map matching with Li’s plurality of machines because (“You can group multiple map matching sequences into one machine, or you can split a very large number of matching sequences onto multiple machines. At the same time, it can heat expand or reduce machine nodes, which is convenient for multiple calculation operations.” See Li (21)).
With respect to claim 20, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 14. The combination of Linder and Li teaches offline map matching of claim 14. Li further teaches:
wherein instructing the master machine to distribute the trajectory segments and the partitioned road network data across the two or more worker machines and instructing the two or more worker machines to perform the map matching operation reduces a total time for executing an offline map matching process compared to a single-machine offline map matching operation. (“the observation state is a GPS coordinate acquired by the device, and the GPS point is centered, and the circle is drawn with a specified or dynamic radius, and all the roads in the circle are To make a vertical line, the intersection of the vertical line and the road is the possible actual position. The K-nearest nearest neighbor method can be used to estimate several possible actual states, and a true observation state to obtain the vehicle's trajectory sequence S.” (12), “The technology of the present invention can be deployed to one or more machines, and the same set of calculation results and map data can be shared between multiple machines, and can be split at any time. You can group multiple map matching sequences into one machine, or you can split a very large number of matching sequences onto multiple machines. At the same time, it can heat expand or reduce machine nodes, which is convenient for multiple calculation operations. 2、Match calculation time is low, matching efficiency is high. Compared with the map matching technology currently existing or used, this patent scheme is efficient and fast. For example, a vehicle trajectory data of 2000 GPS points is input into the system to calculate the match, which lasts for 6873 ms. Enter other ArcGIS-based GPS data map matching systems on the web, which lasted 26117ms. The efficiency and speed increase is nearly 4 times.” (21-23)), where a plurality of machines can be used and reduces a total time for executing an offline map matching process compared to a single-machine offline map matching operation. While Linder teaches a processor, Li teaches computation and data being split between multiple processors. Thus, it would have been obvious to a person of ordinary skill in the art where the plurality of machines includes a primary machine and worker machines in an attempt to provide an improved system or method, as a person with ordinary skill has good reason to pursue the known options within his or her technical grasp. In turn, because the product as claimed has the properties predicted by the prior art, it would have been obvious to make the system or product where there is a master machine and worker machines.
It would have been obvious to one of ordinary skill in the art before the effective filling date of the instant application to have combined Linder’s offline map matching with Li’s plurality of machines because (“You can group multiple map matching sequences into one machine, or you can split a very large number of matching sequences onto multiple machines. At the same time, it can heat expand or reduce machine nodes, which is convenient for multiple calculation operations.” See Li (21)).
Claim(s) 5 and 11 is/are rejected under 35 U.S.C. 103 as being unpatentable over Linder et al. (US 20190360818 A1) in view of Li (CN 109059939 A) and Cai et al. (US 20190204096 A1).
Regarding claims 5 and 11:
With respect to claim 5, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 1. The combination of Linder and Li teaches offline map matching of claim 1. Linder does not teach, but Cai teaches:
computing emission probabilities to determine how likely each of the raw trajectory data lies on a given road segment; (“The forward probability algorithm of the Hidden Markov Model uses a sequence of location signal data sampled at a given frequency and calculates an emission and transition probability between road segments from the signal data. The emission probability is determined based on the likelihood that, for a given candidate road (or road segment), the observed GPS signal would occur… The joint probability of the emission and transition probabilities are then used to calculate the total number of zero forward probability and the average forward probability, from which the system determines the accuracy of the map matching.” [0006])
computing transition probabilities to select a most probable path through the selected road segments; (“The forward probability algorithm of the Hidden Markov Model uses a sequence of location signal data sampled at a given frequency and calculates an emission and transition probability between road segments from the signal data… The transition probability is determined based on probability that transferring to a road segment candidate corresponding to a second observed location signal given the occurrence of the road segment candidate of the previous observed location signal.” [0006], “To determine the probability that each road segment is the most likely trajectory of the transport vehicle, the Hidden Markov Model determines an emission probability and a transition probability associated with each road segment or set of road segments. Since the road segments are based on the underlying map data (e.g., in selecting road segments 406, 414, 412 for location data 402), low-scoring metrics generated by this process may represent that the underlying map data that provided these road segments as candidates may be erroneous or out of date.” [0036]).
It would have been obvious to one of ordinary skill in the art before the effective filling date of the instant application to have combined Linder’s offline map matching with Cai’s probability metrics because “These metrics can be used to improve the map matching performance and the metrics of the downstream services. For example, the metrics can be used to determine the accuracy of map matching algorithms or map data used to generate the map matched route. In another example, because the unsupervised metric is based on map data, a repeated zero forward probability associated with a given area may indicate a flaw in the map data.” See Cai [0007]).
With respect to claim 11, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 9. The combination of Linder and Li teaches offline map matching of claim 9. Linder further teaches:
computing emission probabilities to determine how likely each of the trajectory data lies on a given road segment; (“The forward probability algorithm of the Hidden Markov Model uses a sequence of location signal data sampled at a given frequency and calculates an emission and transition probability between road segments from the signal data. The emission probability is determined based on the likelihood that, for a given candidate road (or road segment), the observed GPS signal would occur… The joint probability of the emission and transition probabilities are then used to calculate the total number of zero forward probability and the average forward probability, from which the system determines the accuracy of the map matching.” [0006])
computing transition probabilities to select a most probable path through the selected road segments; (“The forward probability algorithm of the Hidden Markov Model uses a sequence of location signal data sampled at a given frequency and calculates an emission and transition probability between road segments from the signal data… The transition probability is determined based on probability that transferring to a road segment candidate corresponding to a second observed location signal given the occurrence of the road segment candidate of the previous observed location signal.” [0006], “To determine the probability that each road segment is the most likely trajectory of the transport vehicle, the Hidden Markov Model determines an emission probability and a transition probability associated with each road segment or set of road segments. Since the road segments are based on the underlying map data (e.g., in selecting road segments 406, 414, 412 for location data 402), low-scoring metrics generated by this process may represent that the underlying map data that provided these road segments as candidates may be erroneous or out of date.” [0036]).
It would have been obvious to one of ordinary skill in the art before the effective filling date of the instant application to have combined Linder’s offline map matching with Cai’s probability metrics because “These metrics can be used to improve the map matching performance and the metrics of the downstream services. For example, the metrics can be used to determine the accuracy of map matching algorithms or map data used to generate the map matched route. In another example, because the unsupervised metric is based on map data, a repeated zero forward probability associated with a given area may indicate a flaw in the map data.” See Cai [0007]).
Claim(s) 17-19 is/are rejected under 35 U.S.C. 103 as being unpatentable over Linder et al. (US 20190360818 A1) in view of Li (CN 109059939 A) and Stahlin et al. (US 20110129122 A1).
Regarding claims 17-19:
With respect to claim 17, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 14. The combination of Linder and Li teaches offline map matching of claim 14. Linder does not teach, but Stahlin teaches:
wherein instructing the two or more worker machines to perform a map matching operation comprises using a single-host map matching algorithm; (“the selection of the relevant cartography elements by the apparatus can be used to subsequently perform simultaneous weighing up and assessment of the various cartography elements using the various modules or using various secondary computation units. In this case, said secondary computation units can be regarded as independent map matching algorithms which can operate simultaneously, in parallel and independently of one another.” [0021], “In other words, the secondary computation units and the methods used are designed such that respective specific physical units of the secondary computation unit are converted to a prescribed base unit, the same unit of measurement. Should algorithms be used for calculating the values, it is necessary for the algorithms to be selected such that the predefined unit of measurement is always obtained for each secondary computation unit used.” [0027]), which shows that different map matching algorithms and methods can be selected. Thus, it would have been obvious to a person of ordinary skill in the art to use a single-host map matching algorithm in an attempt to provide an improved system or method, as a person with ordinary skill has good reason to pursue the known options within his or her technical grasp. In turn, because the product as claimed has the properties predicted by the prior art, it would have been obvious to make the system or product where a single-host map matching algorithm is used.
It would have been obvious to one of ordinary skill in the art before the effective filling date of the instant application to have combined Linder’s offline map matching and Li’s plurality of machines with Stahlin’s map matching algorithms because (“The calculation of the values in the various secondary computation units in a common unit allows the subsequent direct comparison of values for the individual cartography elements. This allows various calculation methods to be combined and therefore provides more information for the decision about an alignment. This minimizes any possible error in the alignment.” See Stahlin [0027]).
With respect to claim 18, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 14. The combination of Linder and Li teaches offline map matching of claim 14. Linder does not teach, but Stahlin teaches:
wherein instructing the two or more working machines to perform a map matching operation comprises using a map matching algorithm selected by a user; (“the selection of the relevant cartography elements by the apparatus can be used to subsequently perform simultaneous weighing up and assessment of the various cartography elements using the various modules or using various secondary computation units. In this case, said secondary computation units can be regarded as independent map matching algorithms which can operate simultaneously, in parallel and independently of one another.” [0021], “In other words, the secondary computation units and the methods used are designed such that respective specific physical units of the secondary computation unit are converted to a prescribed base unit, the same unit of measurement. Should algorithms be used for calculating the values, it is necessary for the algorithms to be selected such that the predefined unit of measurement is always obtained for each secondary computation unit used.” [0027]), which shows that different map matching algorithms and methods can be selected.
It would have been obvious to one of ordinary skill in the art before the effective filling date of the instant application to have combined Linder’s offline map matching and Li’s plurality of machines with Stahlin’s map matching algorithms because (“The calculation of the values in the various secondary computation units in a common unit allows the subsequent direct comparison of values for the individual cartography elements. This allows various calculation methods to be combined and therefore provides more information for the decision about an alignment. This minimizes any possible error in the alignment.” See Stahlin [0027]).
With respect to claim 19, Linder in combination with Li, as shown in the rejection above, discloses the limitations of claim 14. The combination of Linder and Li teaches offline map matching of claim 14. Linder does not teach, but Stahlin teaches:
wherein instructing the two or more worker machines to perform a map matching operation comprises using a third-party map matching algorithm; (“the selection of the relevant cartography elements by the apparatus can be used to subsequently perform simultaneous weighing up and assessment of the various cartography elements using the various modules or using various secondary computation units. In this case, said secondary computation units can be regarded as independent map matching algorithms which can operate simultaneously, in parallel and independently of one another.” [0021], “In other words, the secondary computation units and the methods used are designed such that respective specific physical units of the secondary computation unit are converted to a prescribed base unit, the same unit of measurement. Should algorithms be used for calculating the values, it is necessary for the algorithms to be selected such that the predefined unit of measurement is always obtained for each secondary computation unit used.” [0027]), which shows that different map matching algorithms and methods can be selected. Thus, it would have been obvious to a person of ordinary skill in the art to use a third party map matching algorithm in an attempt to provide an improved system or method, as a person with ordinary skill has good reason to pursue the known options within his or her technical grasp. In turn, because the product as claimed has the properties predicted by the prior art, it would have been obvious to make the system or product where a third party map matching algorithm is used.
It would have been obvious to one of ordinary skill in the art before the effective filling date of the instant application to have combined Linder’s offline map matching and Li’s plurality of machines with Stahlin’s map matching algorithms because (“The calculation of the values in the various secondary computation units in a common unit allows the subsequent direct comparison of values for the individual cartography elements. This allows various calculation methods to be combined and therefore provides more information for the decision about an alignment. This minimizes any possible error in the alignment.” See Stahlin [0027]).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant’s disclosure.
Dong et al. (US 9835460 B2) is pertinent because “Referring now to FIG. 6, a representative hardware environment for practicing at least one embodiment of the invention is depicted. This schematic drawing illustrates a hardware configuration of an information handling/computer system in accordance with at least one embodiment of the invention. The system comprises at least one processor or central processing unit (CPU) 710. The CPUs 710 are interconnected with system bus 712 to various devices such as a random access memory (RAM) 714, read-only memory (ROM) 716, and an input/output (I/O) adapter 718.” (41), “Computer system/server 12 may be practiced in distributed cloud computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed cloud computing environment, program modules may be located in both local and remote computer system storage media including memory storage devices.” (62), “A virtual network constructor can construct a virtual network structure based on selected candidates (4); and, a most possible path searcher can perform a path search on the virtual network (5). In at least one embodiment, items (1) and (2) are performed offline and items (3)-(5) are performed online.” (22)), which pertains to using multiple machines.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Christine N Huynh whose telephone number is (571)272-9980. The examiner can normally be reached Monday - Friday 8 am - 4 pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Aniss Chad can be reached at (571)270-3832. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/CHRISTINE NGUYEN HUYNH/Examiner, Art Unit 3662
/ANISS CHAD/Supervisory Patent Examiner, Art Unit 3662
Prosecution Insights