This paper starts with a discussion of the open challenges in the SLAM problem. In our opinion they can be grouped in two main and distinct areas: convergence of the built map and computation requirement for real world application. To deal with the previous problems, a solution in the stochastic map framework based on the concept of the relative map is proposed. The idea consists in introducing a map state, which only contains quantities invariant under shift and rotation and to carry out the estimation of this relative map in an optimal way. This is a possible way in order to have a decoupling between the robot motion and the landmark estimation and therefore not to rely the landmark estimation on the unmodeled error sources of the robot motion. Moreover, the proposed solution scales linearly with the number of landmark allowing real-time application. Experimental results, carried out on a real platform, show the better performance of this method with respect to the joint vehicle-landmark approach (absolute map fflter) when the odometry is affected by undetected systematic errors or by large or unmodeled non-systematic errors.