13 Tracking of Moving Objects with Accuracy Guarantees
293
13.4 Modifying the Road Network Representation
Recall that with segment-based tracking, the predicted position of an object moves at
constant speed along a segment drawn from the underlying representation of the road
network until it reaches the end of the segment, at which time the predicted position
remains at the end of the segment. The experimental study reported in Sect. 13.3
indicates that the numbers of updates in segment-based tracking are closely correlated with the numbers of segment changes. This motivates attempts to modify the
underlying road network representation so that less segment changes occur.
We proceed to cover several modifications of the road network representation.
The main idea is to connect road segments in such a way that moving objects would
have to change segments as few times as possible as they travel in the road network.
We first describe three modification approaches and then report on experimental studies with these approaches.
13.4.1 Modification Approaches
The general idea of the road network modification is to iterate through all segments
in the road network to be modified according to some specified ordering. During each
iteration, the modification algorithm orders all available segments and then tries to
extend the topmost, or current, segment with other segments. To do this, the algorithm identifies all the existing segments that start or end at the start or end of the
current segment and extends the current segment with the most attractive of such segment(s) according to some other specified ordering. A current segment that has been
extended is considered in the next iteration, but the segment(s) that were used for the
extension are disregarded. A current segment that has not been extended becomes
part of the final result and is not considered any further. Several different ordering
strategies can be considered. Details on the modification approaches beyond what is
reported next are given elsewhere [5].
Street code-based Approach
As described at the end of Sect. 13.2.2, a named street (e.g. “Main Street”) is represented by many segments, and the segments have street codes that identify the named
street that they represent part of.
The ordering in the street code-based (SSC) approach exploits the availability
of street codes for the segments. The idea is to give priority to connecting polylines
with the same street code. In this way, longer road segments are constructed that tend
to correspond to parts of the same street. In cases where there are several candidates
with the same street code, priority is given to the shortest polyline. This strategy
reduces the probability that unconnected polylines will be short.
Tail Disconnection Approach
The SSC does not distinguish between main roads and side streets. The observation that motivates the tail disconnection approach (TSC) is that moving objects can
293
13.4 Modifying the Road Network Representation
Recall that with segment-based tracking, the predicted position of an object moves at
constant speed along a segment drawn from the underlying representation of the road
network until it reaches the end of the segment, at which time the predicted position
remains at the end of the segment. The experimental study reported in Sect. 13.3
indicates that the numbers of updates in segment-based tracking are closely correlated with the numbers of segment changes. This motivates attempts to modify the
underlying road network representation so that less segment changes occur.
We proceed to cover several modifications of the road network representation.
The main idea is to connect road segments in such a way that moving objects would
have to change segments as few times as possible as they travel in the road network.
We first describe three modification approaches and then report on experimental studies with these approaches.
13.4.1 Modification Approaches
The general idea of the road network modification is to iterate through all segments
in the road network to be modified according to some specified ordering. During each
iteration, the modification algorithm orders all available segments and then tries to
extend the topmost, or current, segment with other segments. To do this, the algorithm identifies all the existing segments that start or end at the start or end of the
current segment and extends the current segment with the most attractive of such segment(s) according to some other specified ordering. A current segment that has been
extended is considered in the next iteration, but the segment(s) that were used for the
extension are disregarded. A current segment that has not been extended becomes
part of the final result and is not considered any further. Several different ordering
strategies can be considered. Details on the modification approaches beyond what is
reported next are given elsewhere [5].
Street code-based Approach
As described at the end of Sect. 13.2.2, a named street (e.g. “Main Street”) is represented by many segments, and the segments have street codes that identify the named
street that they represent part of.
The ordering in the street code-based (SSC) approach exploits the availability
of street codes for the segments. The idea is to give priority to connecting polylines
with the same street code. In this way, longer road segments are constructed that tend
to correspond to parts of the same street. In cases where there are several candidates
with the same street code, priority is given to the shortest polyline. This strategy
reduces the probability that unconnected polylines will be short.
Tail Disconnection Approach
The SSC does not distinguish between main roads and side streets. The observation that motivates the tail disconnection approach (TSC) is that moving objects can