geometrygeospatialquadtrees2

How would I use S2 in a Yelp or Uber service?


Let's say I have a list of restaurants and I have the location of a customer that's looking for restaurants that are nearby. How could I use S2?

From my understanding without S2, I would maintain my own Quad Tree that has all the restaurants and then I would take the latitude and longitude of my customer and query my Quad Tree to find the node and neighbor Quad Tree nodes.

How would S2 fit into this picture? Would it replace the need for me to maintain my own Quad Tree?

My understanding of S2 is that under the hood there's Quad Trees and Hilber space-filling curves which given a latitude and longitude can provide a 64 bit cell ID that identifies the node in the Quad Tree that the latitude and longitude belong to.


Solution

  • This article from Tinder is exactly what I was looking for.

    https://medium.com/tinder-engineering/geosharded-recommendations-part-1-sharding-approach-d5d54e0ec77a

    If you’re building a service that needs requires partitioning geo data, you would use S2 to give you a number encoding of specific locations or a range of number encodings for a specfic radius. You would maintain the partioning scheme yourself.