Location fuzzing

Hey all,

I got a question from Doug a little while ago about location fuzzing,  
and thought the whole group might be interested in the response.

The current approach we're taking in GEOPRIV is described in this  
document:
<http://tools.ietf.org/html/draft-ietf-geopriv-policy-21>
Geodetic fuzzing is in Section 6.5.2 ...
<http://tools.ietf.org/html/draft-ietf-geopriv-policy-21#section-6.5.2>
... and fuzzing of civic addresses is in Section 6.5.1:
<http://tools.ietf.org/html/draft-ietf-geopriv-policy-21#section-6.5.1>

These techniques start from a slightly different place than the W3C  
Geolocation API:
-- Geodetic location is given by a shape (e.g., point, circle,  
ellipse, polygon, arc-band), rather than a single point with a radius
-- Civic location is given by an RFC 5139 address structure

The geodetic fuzzing algorithm take two inputs:
1. A shape representing the user's estimated location, and
2. A "fuzzing radius" F in meters
 From these, you generate the fuzzed result in the following way:   
First, you choose a random "baseline circle" that  (1) has a radius at  
least F, and (2) covers the input shape (the user's location).  The  
shape you return is then any shape that contains the baseline circle.   
If there are multiple requests for the user's location, then the  
return shape may be varied (as long as it still contains the baseline  
circle).  If the user moves outside the baseline circle, then you  
choose a new random baseline circle.   Example here:
<http://geopriv.dreamhosters.com/fuzz.pdf>

This algorithm guarantees that all an observer gets by averaging/ 
intersecting is the baseline circle, which has the minimum required  
uncertainty.  If the target is moving, then you can add enough jitter  
to obscure this to some extent, and you don't run into boundary issues  
(like you do with "rounding" or "fixed grid" approaches).

This kind of maps on the the "point+uncertainty" construct that's in  
the current Geolocation API spec, if you make the mental equivalence  
"point+uncertainty = circle".  In this analogy, the center of the  
baseline circle is a random fixed offset from the real location, and  
the returned points will cluster roughly around the baseline circle  
(with uncertainty values big enough to cover the baseline circle.

The civic fuzzing works by restricting the set of civic address  
elements that are returned to a predefined set.  The draft defines six  
levels (full, building, city, region, country, none); for example, the  
region level includes the "country" element as well as the "A1", "A2",  
and "A3" hierarchical elements.

Hope this helps,
--Richard