5 ms·
It's disappointing to see a highly-upvoted comment from someone that didn't read the article. The article discusses explicitly why R-trees were not used: >Inst
by deminature 7y ago
It's disappointing to see a highly-upvoted comment from someone that didn't read the article. The article discusses explicitly why R-trees were not used:
>Instead of indexing the geofences using R-tree or the complicated S2, we chose a simpler route based on the observation that Uber’s business model is city-centric; the business rules and the geofences used to define them are typically associated with a city. This allows us to organize the geofences into a two-level hierarchy where the first level is the city geofences (geofences defining city boundaries), and the second level is the geofences within each city.
- icholy 7y agoR-tree will easily outperform that approach.
- xtomus 7y agoYou can either ship a 2 dimensional linear search approach today or ship an R tree based approach in 2 weeks time. I know which one in choosing if they both meet all of the requirements
- woeirua 7y agoI did read the article before posting. They don’t actually explain why they opted to not use an R-tree except to say that they think this organizational structure makes sense intuitively. Unfortunately, intuition here is wrong, and the link I posted specifically benchmarks their solution and shows that if they had done even basic benchmarking they would have seen this. Now there might be a valid argument for this approach if the geofences are changing constantly and reindexing the R-trees would take too long, but in the end they synchronize everything anyways, and the R-tree could easily be generated on another node, serialized and then unserialized asynchronously before swapping to an updated tree.