How are you estimating that?
How will you move a known distance in a known direction over unknown surfaces?
If we assume letting the robot start at some predefined position, for example (0,0), and a predefined heading, for example pointing along X-axis, then for each movement operation, be it rotation or moving forward, an internal value is updated according to heuristics determined experimentally. This value indicates accumulated margin of error.
Thus, when stopping to make a scan of the environment, the information is stored in memory along with the margin of error at that point (and "scenery data").
Further movement increases this margin of error value. Rotation around its own axis will be particularly error-prone, and must be minimized.
Anyway, this is where the "scenery data" comes in, represented by the counters for different echo-distances recorded during the sweep. Using the estimated position along with the accumulated margin of error, together with "scenery data" for previous measurements made in the same general area, the hope is to be able to make the otherwise ever-increasing margin of error go down somewhat.
I have experimented with the "scenery data" collection and correlation algortihm for calculating a deviance factor between what the robot sees of its surroundings and previously collected information, and have been able to calculate a number which if smaller than 1.0 indicates a pretty good match, scenery-wise.
Memory consumption:
x-position: two bytes
y-position: two bytes
smallest-echo-radius: two bytes
accumulated-margin-of-errors: two bytes
scenery-data: four values x 4 bits = two bytes
Total: 10 bytes
Leaving room for other state, based on the 2K available for Uno, we can easily store 100 such measurements in the RAM of an Uno.
Added:
Perhaps I should add that when doing a sonar reading for a particular angle, I actually do multiple readings, and calculate average plus variance. If variance too big, the reading is ignored, continuing to next scan angle.
Also, the angles of which the scans are made are not important as such, the idea is just to scan the entire 360 degrees in a number of discrete positions. This means that the data collected are neutral with regards to orientation.