In this paper, we study the problem of localization using relative-state estimates. It is shown, that when the same exteroceptive sensor measurement is processed for the computation of two consecutive displacement estimates (both forward and backward in time) these estimates are correlated, and an analysis of the exact structure of the correlations is performed. This analysis is utilized in the design of data fusion algorithms, that correctly account for the existing correlations. We examine two cases: i) pose propagation based exclusively on inferred displacement measurements, and ii) the fusion of proprioceptive sensor information with relative-state measurements. For the latter case, an efficient EKF-based estimation algorithm is proposed, that extends the approach of . Extensive simulation and experimental results are presented, that verify the validity of the presented method.