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

Question

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.

Answer 1

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.

Answer 2

The way you normally do it in S2 is through existing S2 API classes, e.g. here I would use S2ClosestPointQuery.

Internally the query class builds an internal index (in this case - using S2 cells of the restaurants), and when you want to find all points nearby a customer it computes the range of cells on S2's Hilbert curve that are within the given distance from the search location (in this case - customer location), and looks for those cells in the index.