7 ms·
I actually needed this at work once! We needed to fuzz peoples address in a mapped view for analytics, without revealing PII. It ended up never being shipped, b
by frankfrank13 3y ago
I actually needed this at work once! We needed to fuzz peoples address in a mapped view for analytics, without revealing PII. It ended up never being shipped, but we needed to fuzz geographic data and the thinking was like:
1. Truncate your lat longs to some arbitrary decimal place (this is very very stupid, you end up with grid lines [1])
2. The above method ^^ but everyone tries basically doing like random angle + random length along angle, which doesn't generate uniform results in a circle as the article mentions[2]. So then you try generating points in a box that encloses your circle, and rejecting anything outside the circle, but that smells bad. So you do some googling and find method 6 listed in the article (Good! and Fast!)
3. Realize that fuzzing points is stupid, what you really want is to view points in aggregate anyways, so you try heat maps
[1]: Ok you always end up with grid lines, but truncating to like 1-6 decimal places produces very obvious grid lines to the human eye
[2]: Try this in pyplot! You'll see right away with ~100 points its not uniform in the way you expect
- bagels 3y agoI needed something related, n roughly evenly distributed points on the surface of a sphere. Ended up using a Fibonacci spiral. https://extremelearning.com.au/how-to-evenly-distribute-points-on-a-sphere-more-effectively-than-the-canonical-fibonacci-lattice/ https://extremelearning.com.au/how-to-evenly-distribute-poin...
- milleramp 3y agoHey me too, very interesting problem. I also used this method as well. https://www.sciencedirect.com/science/article/abs/pii/S0010465518301292 https://www.sciencedirect.com/science/article/abs/pii/S00104...
- alanbernstein 3y agoForce directed layout is my favorite for this.
- fjkdlsjflkds 3y ago...but then the algorithmic complexity goes from O(N) to O(N^2), or at least O(N log N), since points have to interact with each other. (N denotes the number of points you need to generate)
- alanbernstein 3y agoI confess I've never used this in a situation where time complexity was at all relevant. For one thing, it is possible that a result only needs to be computed once for each N (and per shape, since this approach works on a wider range of shapes than just spheres).
- bagels 3y agoNeat. My n was on the order of thousands, so that would have taken a while, but it could have been cached.
- bee_rider 3y agoThe rejection method smells pretty good to me, in the sense that it should be pretty obvious to anybody with, like, middle school level math I think (right?). It might fail for higher dimensions, but lots of programs only run on a 3D sphere of a planet, haha!
- contravariant 3y agoFail is an understatement, the ratio between the two volumes is basically (n/2)!(4/pi)^(n/2). Which is also the expected number of tries you'll need. The time doesn't merely grow exponentially it grows faster than exponential. I don't actually know of any useful algorithms with worse asymptomatic behaviour.
- zeroonetwothree 3y agoI doubt that the number of dimensions is the parameter that grows. It’s going to be constant for 99.99% of cases.
- ianferrel 3y agoSure, but for the most-used real-world geometry, n = 2 or 3. So how fast it grows really doesn't matter. Most maps are 2-dimensional and this is fine.
- ls612 3y agoMaybe n=4 if you have a timestamp as another dimension.
- alanbernstein 3y agoDo your timestamps occupy a hypersphere?
- ls612 3y agoA 1-dimensional hypersphere is a line segment so sure.
- chpatrick 3y agoWhat if someone lives in a really remote location so they're the only ones in the heat map cell?
- nighthawk454 3y agoI should think after defining a uniform distribution of points, you could cluster them as needed to form larger lower-resolution chunks according to population size. Binning everyone in that region to say the central most point. Which could then be adaptive as the populations change.
- xyzzy_plugh 3y agoThis is the correct answer. You need an aggregation threshold that restricts precision when population count is too low. In this case, the cell size needs to increase until there are at least N users.
- nick7376182 3y agoAssign everyone a random offset, that doesn't change, that is large enough to obscure the address with some reasonable radius but small enough to not drastically skew the heat map at a lower zoom level
- frankfrank13 3y agoAnother user here mentioned Uber's h3, which is actually what I used. You end up being able to anonymize over arbitrarily large geographic areas using something like a tile, rather than a point
- esafak 3y agoI'd just have used Uber's hexagonal tiling library. https://www.uber.com/blog/h3/ https://www.uber.com/blog/h3/
- frankfrank13 3y agoThis is what I landed on! It actually works very very well for aggregate data.
- longhaul 3y agoLong time ago, I had the same problem while ray tracing using Monte Carlo techniques. Using Mersenne Twister fixed the clustering and grid like randomization. https://en.m.wikipedia.org/wiki/Mersenne_Twister https://en.m.wikipedia.org/wiki/Mersenne_Twister