Geosharded Recommendations with Hilbert Curve at Tinder
tech.gotinder.com
Geosharded Recommendations with Hilbert Curve at Tinder
1–10 of 47 posts
Re: Geosharded Recommendations with Hilbert Curve at Tinder
#2How big of a problem is the fact that shards constructed this way don't like crossing the "big" boundaries in the S2 curve? Especially if a high-usage location happens to straddle one of those boundaries (like, IIRC, Toronto)?
Re: Geosharded Recommendations with Hilbert Curve at Tinder
#3How big of a problem is the fact that shards constructed this way don't like crossing the "big" boundaries in the S2 curve? Especially if a high-usage location happens to straddle one of those boundaries (like, IIRC, Toronto)?
You can compute which shard to use and if you’re in a border region you just use all shards that overlap with your 100km radius.
Re: Geosharded Recommendations with Hilbert Curve at Tinder
#4a bit off-topic, it's funny you use all this fancy technology behind the scenes and your iOS app is buggy, slow and always problems with login and notifications which do not update.
TLDR; Awful
Re: Geosharded Recommendations with Hilbert Curve at Tinder
#5Using a Hilbert Curve for indexing is a pretty standard approach for geospatial queries. Nothing new here...
However, using a Hilbert Curve for sharding doesn't seem like the best approach. You can partition by anything you like, it doesn't have to be arbitrary points along your index. Using 1-dimension to shard 2D data isn't optimal.
For example, construct a heatmap of your 'load score' and shard based on that, in two dimensions. Then use an S2 curve to index inside that shard.
Re: Geosharded Recommendations with Hilbert Curve at Tinder
#6a bit off-topic, it's funny you use all this fancy technology behind the scenes and your iOS app is buggy, slow and always problems with login and notifications which do not update. TLDR; Awful
[deleted]
Re: Geosharded Recommendations with Hilbert Curve at Tinder
#7Using a Hilbert Curve for indexing is a pretty standard approach for geospatial queries. Nothing new here... However, using a Hilbert Curve for sharding doesn't seem like the best approach. You can partition by anything you like, it doesn't have to be arbitrary points along your index. Using 1-dimension to shard 2D data isn't optimal. For example, construct a heatmap of your 'load score' and shard based on that, in t…
Thanks for the suggestion and there are definitely room for optimization.
In the original design we did consider approach similar to the "heatmap approach" you mentioned, it would reduce the shard movement for people who commutes in the city.
Later we figured that simply sharding along on the Hilbert Curve already give what we need, and the shard move is unavoidable, we would explain more details around the shard move in future blog.
Re: Geosharded Recommendations with Hilbert Curve at Tinder
#8When implementing similar algorithms on a load-balancing reverse proxy cache-friendliness and lockless reads and updates in the "load scores" can be way more important than optimizing for CPU cycles.
Another option would be to map coords into very small 2D tiles and than look up "tile -> shard number" with a simple, large, array. A variable number of tiles would land into the same shard. Fast and lockless reads and writes. I wonder if it could be faster.
Re: Geosharded Recommendations with Hilbert Curve at Tinder
#9Using a Hilbert Curve for indexing is a pretty standard approach for geospatial queries. Nothing new here... However, using a Hilbert Curve for sharding doesn't seem like the best approach. You can partition by anything you like, it doesn't have to be arbitrary points along your index. Using 1-dimension to shard 2D data isn't optimal. For example, construct a heatmap of your 'load score' and shard based on that, in t…
However, using a Hilbert Curve for sharding doesn't seem like the best approach.
Yes, that's also what I thought. Searching for "same size k-means" yields a simple postprocessing step to even out the clusters produced by the usual k-means algorithm.
EDIT: k-means is adapted directly here: https://elki-project.github.io/tutorial/same-size_k_means
Re: Geosharded Recommendations with Hilbert Curve at Tinder
#10Using a Hilbert Curve for indexing is a pretty standard approach for geospatial queries. Nothing new here... However, using a Hilbert Curve for sharding doesn't seem like the best approach. You can partition by anything you like, it doesn't have to be arbitrary points along your index. Using 1-dimension to shard 2D data isn't optimal. For example, construct a heatmap of your 'load score' and shard based on that, in t…
> using a Hilbert Curve for sharding doesn't seem like the best approach. You can partition by anything you like, it doesn't have to be arbitrary points along your index. Using 1-dimension to shard 2D data isn't optimal.
If you want to shard by proximity (items close in space are likely to be in the same shard, then the transform to 1d is the way to go, why wouldn't it be? What is your definition of "optimal"?
Sharding by proximity or by something else depends on the relative frequency of queries by location or something else. If you shard by location, then a query to one location goes (ususally) to one shard. That should scale better. Otherwise, each location-based query goes to each shard.