4 ms·

Map cells are the best solution available for 90% of locations, but they don't help with the 10% that's close to map borders. If an user randomly jumps between

by est31 6y ago

Map cells are the best solution available for 90% of locations, but they don't help with the 10% that's close to map borders. If an user randomly jumps between two map cells you know they live at the boundary. Generally there is often noise in GPS signals so it's likely that person will jump around. Furthermore, if a person uses multiple services, and each service has its own cell layout, you can check all services a user is member of and then find the intersection. Ideally services would standardize to one single cell layout. So Apple's idea of doing this cell partitioning at the OS level is really good. I think the boundary concern can be resolved by some inertia system, so a person doesn't switch cells unless they are deeply enough in the new cell, at which point they won't switch back unless they have moved back deeply enough.

deleted 6y ago
[deleted]
godelski 6y ago
I'm just spitballing here, but couldn't this be resolved by using coarse sampling and a moving average? As in infrequently sampling locations. I guess you could get fancier and adjust this with the speed at which the user is moving. I'd also imagine that just using low precision GPS would help add ambiguity so a person can't be exactly located. Of course, there's a relevant xkcd[0]. In the "neighborhood" seems like the most precision you'd want for something like this (of course you could expose this to the user), but I'm also not even interested in this feature so there's a bias. [0] https://xkcd.com/2170/ https://xkcd.com/2170/
sudosysgen 6y ago
Maybe overlapping regions would be a fix?
- est31 6y ago
  I believe so yes. An inertia system or overlapping system are two ways to describe the same thing :).
  - sudhirj 6y ago
    Huh? Not the way I understood it. Inertia implies the world is divided into cells numbered 1 to N, and people don’t move from X to X + 1 unless they report, say 5, consecutive times from X + 1. Overlapping systems remap the cells 1,2,3 to 1; 2,3,4 to 2 and so on. So if someone oscillated between new no. 1 and new no. 2, you’d still have no of knowing whether they were in old style cells no 2 or 3.
    - e_proxus 6y ago
      Inertia would just reduce the frequency of the jumps, not eliminate them completely. E.g. if you randomly get the new cell 6 times in a row you'll still oscillate, just slower.
      - antigluk 6y ago
        It should be hysteresis, to jump to another cell you have to be pass some threshold of distance from it's border. This way if you live on the border you will just stick to some of cells.
    - est31 6y ago
      > Not the way I understood it. Inertia implies the world is divided into cells numbered 1 to N, and people don’t move from X to X + 1 unless they report, say 5, consecutive times from X + 1. Overlapping systems remap the cells 1,2,3 to 1; 2,3,4 to 2 and so on. So if someone oscillated between new no. 1 and new no. 2, you’d still have no of knowing whether they were in old style cells no 2 or 3. Hmm yeah I meant overlapping cells then, not inertia based ones.
    - quietbritishjim 6y ago
      Inertia could well be understood to mean what you described as "overlapping". That's how I understood their comment and it appears that's how they intended it. It makes sense given the literal meaning of interia, relating to resistence to physically move an object. I don't get why you think it necessarily implies the frequency thing.
  - 6y ago
wilg 6y ago
Apple's solution to this seems pretty good, here's a snippet of the transcript from a WWDC 2020 talk: > It might be tempting to think that reduced accuracy locations are simply your true location with some noise added in. > But that is not the case. Simply adding some random noise on top of the user's true location is actually not that secure against someone who might wish to disambiguate the true location. Instead it's better to think of what happens under the hood as a quantization of sorts. Let me explain further. > Let's look at an example area. Consider different users going on a drive in the vicinity of El Paso, Texas and Juarez, Mexico. Note that this is near an international boundary, with the US being in the northern half of the map, and Mexico being in the southern half, bordered by this pink line you see here. The true position of the user is represented by the cars while the reported position, that is to say what an app would see if it had reduced accuracy, will be shown by a circle. Again as I mentioned earlier in this presentation, these reported locations will contain the user's true location. > As these users drive down Interstate 10 the location snaps to within different quantize regions of varying sizes. Both the red and yellow users are going to be quantized or "snapped" into the same regions as they drive along the road. > But the amount of snapping will vary. In denser urban areas, this amount of quantization can be a couple of kilometers, but in less dense places like rural areas, it can be 10 kilometers or a bit more. A typical value for this quantization radius is around five kilometers. Note that despite the cars continuously driving along the road the region to which the true position quantities will not continuously update. This is because Reduced Accuracy locations are recomputed about 4 times per hour. So depending on exactly how fast these cars are moving there might be some lag between quantized snaps. The actual semantics of the quantization are intended to replicate what the user would expect to hear if they were to ask for an approximate answer to the question "Where am I"? We tried to ensure that the resultant reduced accuracy location is still going to be somewhere that the user actually expects to be. We use a location we have for you to place your approximate location on the appropriate side of the border here. > Again though remember that the center point does not represent the location of the user. It only represents the center of a region where they approximately are. Approximate location snapping however might put you in a neighboring city especially if there are cities close together. To reiterate the bit about quantization around borders, let's see what happens to someone driving on the other side of the border in Juarez and what they might expect to see. > Note that the blue car is quantized into regions whose centers are on the Mexican side of the border. https://developer.apple.com/videos/play/wwdc2020/10660/ https://developer.apple.com/videos/play/wwdc2020/10660/

by est31 6y ago

deleted 6y ago

[deleted]

godelski 6y ago

I'm just spitballing here, but couldn't this be resolved by using coarse sampling and a moving average? As in infrequently sampling locations. I guess you could get fancier and adjust this with the speed at which the user is moving. I'd also imagine that just using low precision GPS would help add ambiguity so a person can't be exactly located. Of course, there's a relevant xkcd[0]. In the "neighborhood" seems like the most precision you'd want for something like this (of course you could expose this to the user), but I'm also not even interested in this feature so there's a bias. [0] https://xkcd.com/2170/ https://xkcd.com/2170/

sudosysgen 6y ago

Maybe overlapping regions would be a fix?

est31 6y ago
I believe so yes. An inertia system or overlapping system are two ways to describe the same thing :).
- sudhirj 6y ago
  Huh? Not the way I understood it. Inertia implies the world is divided into cells numbered 1 to N, and people don’t move from X to X + 1 unless they report, say 5, consecutive times from X + 1. Overlapping systems remap the cells 1,2,3 to 1; 2,3,4 to 2 and so on. So if someone oscillated between new no. 1 and new no. 2, you’d still have no of knowing whether they were in old style cells no 2 or 3.
  - e_proxus 6y ago
    Inertia would just reduce the frequency of the jumps, not eliminate them completely. E.g. if you randomly get the new cell 6 times in a row you'll still oscillate, just slower.
    - antigluk 6y ago
      It should be hysteresis, to jump to another cell you have to be pass some threshold of distance from it's border. This way if you live on the border you will just stick to some of cells.
  - est31 6y ago
    > Not the way I understood it. Inertia implies the world is divided into cells numbered 1 to N, and people don’t move from X to X + 1 unless they report, say 5, consecutive times from X + 1. Overlapping systems remap the cells 1,2,3 to 1; 2,3,4 to 2 and so on. So if someone oscillated between new no. 1 and new no. 2, you’d still have no of knowing whether they were in old style cells no 2 or 3. Hmm yeah I meant overlapping cells then, not inertia based ones.
  - quietbritishjim 6y ago
    Inertia could well be understood to mean what you described as "overlapping". That's how I understood their comment and it appears that's how they intended it. It makes sense given the literal meaning of interia, relating to resistence to physically move an object. I don't get why you think it necessarily implies the frequency thing.
- 6y ago

wilg 6y ago

Apple's solution to this seems pretty good, here's a snippet of the transcript from a WWDC 2020 talk: > It might be tempting to think that reduced accuracy locations are simply your true location with some noise added in. > But that is not the case. Simply adding some random noise on top of the user's true location is actually not that secure against someone who might wish to disambiguate the true location. Instead it's better to think of what happens under the hood as a quantization of sorts. Let me explain further. > Let's look at an example area. Consider different users going on a drive in the vicinity of El Paso, Texas and Juarez, Mexico. Note that this is near an international boundary, with the US being in the northern half of the map, and Mexico being in the southern half, bordered by this pink line you see here. The true position of the user is represented by the cars while the reported position, that is to say what an app would see if it had reduced accuracy, will be shown by a circle. Again as I mentioned earlier in this presentation, these reported locations will contain the user's true location. > As these users drive down Interstate 10 the location snaps to within different quantize regions of varying sizes. Both the red and yellow users are going to be quantized or "snapped" into the same regions as they drive along the road. > But the amount of snapping will vary. In denser urban areas, this amount of quantization can be a couple of kilometers, but in less dense places like rural areas, it can be 10 kilometers or a bit more. A typical value for this quantization radius is around five kilometers. Note that despite the cars continuously driving along the road the region to which the true position quantities will not continuously update. This is because Reduced Accuracy locations are recomputed about 4 times per hour. So depending on exactly how fast these cars are moving there might be some lag between quantized snaps. The actual semantics of the quantization are intended to replicate what the user would expect to hear if they were to ask for an approximate answer to the question "Where am I"? We tried to ensure that the resultant reduced accuracy location is still going to be somewhere that the user actually expects to be. We use a location we have for you to place your approximate location on the appropriate side of the border here. > Again though remember that the center point does not represent the location of the user. It only represents the center of a region where they approximately are. Approximate location snapping however might put you in a neighboring city especially if there are cities close together. To reiterate the bit about quantization around borders, let's see what happens to someone driving on the other side of the border in Juarez and what they might expect to see. > Note that the blue car is quantized into regions whose centers are on the Mexican side of the border. https://developer.apple.com/videos/play/wwdc2020/10660/ https://developer.apple.com/videos/play/wwdc2020/10660/