4 ms·

This is a very inefficient implementation. Really, just poor quality work overall, as anyone with even a basic understanding of spatial indexing would know that

This is a very inefficient implementation. Really, just poor quality work overall, as anyone with even a basic understanding of spatial indexing would know that an R-tree would be many times faster, as illustrated here: https://medium.com/@buckhx/unwinding-uber-s-most-efficient-service-406413c5871d https://medium.com/@buckhx/unwinding-uber-s-most-efficient-s...

not_a_cop75 7y ago
So am I to understand this shows a little bit about why Uber is not the center of excellence it needs to be?
thejigisup 7y ago
clearly the most efficient solution is to pontificate about other people's implementations while never having done anything of the sort at that scale yourself.
- jzoch 7y ago
  While he was a bit rude I wouldnt assume he hasn't built something at this sort of scale.
  - thejigisup 7y ago
    nah i think its a pretty fair assumption
    - woeirua 7y ago
      Let's just ignore the fact that in this case scale has nothing to do with the actual efficiency of the algorithm they implemented. As the link I posted mentioned, had they used a more efficient algorithm they could have used far fewer resources, or used the same resources to scale up further, with much faster response times overall.
    - forgottenpass 7y ago
      99% of people building at "scale" are borrowing bragging rights from a large company they happen to be employed by and/or tools they use while doing zero novel work unique to the size of their deployment. To say that these paper tigers are above the bikeshedding of all the plebs is quintessential software echochamber.
      - dang 7y ago
        "Don't be snarky." "Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html We've had to ask you to stop doing precisely this in the past: https://news.ycombinator.com/item?id=19884138 https://news.ycombinator.com/item?id=19884138 https://news.ycombinator.com/item?id=13587522 https://news.ycombinator.com/item?id=13587522 Unfortunately, you've continued to post like this frequently. If you keep doing that we're going to have to ban you, so could you please review the guidelines and fix this?
  - pc86 7y ago
    The vast majority of programmers haven't built something at this sort of scale, so while it's very possible that he has, odds are that he hasn't.
- benburleson 7y ago
  For future internet-searchers that stumble upon this, it might be helpful to point out that better solutions exist..
  - rutenspitz 7y ago
    It would be even more helpful to point out that the article talked about all of this.
buckhx 7y ago
Thanks for the shout out. If anyone has questions or comments feel free to reach out. Also I'm looking for work so if anyone is interested snag my email from my profile.
_virtu 7y ago
I'm currently implementing an rtree in elm. Does anyone have good references about rtrees that they like?
- mateo411 7y ago
  I think this is the first paper on R Trees. http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf
winrid 7y ago
I've used RTrees for this too (In Java) and they're great. Hundreds of thousands of queries a second per cpu core on millions of data points.
jorblumesea 7y ago
It's funny because had you tried to brute force any of their interview questions (spatial or not) it would have been instant rejection. Often feels like algo analysis is an exercise to get a job and not something engineers actually do, even when required.
- woeirua 7y ago
  The entire line of argument would have been immediately rejected in a phone screening or an on-site interview at any of the major companies, and even many lesser companies that deal with spatial data. Anyone doing spatial queries and not using existing spatial data structures had better have a really good reason for not doing so.
deleted 7y ago
[deleted]
dang 7y ago
This comment is unacceptable on Hacker News, and I'd like to explain in detail why. Please don't think I'm picking on you personally; we all react like this sometimes. Rather, I want to drive this point home to the community. It's important for discussion quality here! ----- Please omit swipes like "Really, just poor quality work" and "anyone with even a basic understanding" from your posts to HN. It's great to add relevant information, such as an applicable data structure and a link to a good article on the same topic. But it's not great to put others and their work down, and HN has at least two guidelines that ask you not to: When disagreeing, please reply to the argument instead of calling names. "That is idiotic; 1 + 1 is 2, not 3" can be shortened to "1 + 1 is 2, not 3." Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something. Actually, a third guideline is relevant too: Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. The strongest plausible interpretation is not that the engineers lacked a basic understanding of relevant CS—or, for that matter, how to use a search engine, since R-trees would pop up nearly any place you searched about this stuff. The strongest plausible interpretation is that they had some other reason for choosing the implementation they did. For example, perhaps it was efficient enough and they were smartly choosing not to build something more complicated than needed. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html Edit: and it turns out that the article explains why they didn't use R-trees.
- 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 ago
paggle 7y ago
If you follow American football, your comment reads quite a bit like "Tom Brady has terrible throwing mechanics." Ultimately, it might be right, in some purely academic sense, but in a more relevant sense, good throwing mechanics are those that win you games, and good software implementations are those that meet the business requirements.

not_a_cop75 7y ago

So am I to understand this shows a little bit about why Uber is not the center of excellence it needs to be?

thejigisup 7y ago

clearly the most efficient solution is to pontificate about other people's implementations while never having done anything of the sort at that scale yourself.

jzoch 7y ago
While he was a bit rude I wouldnt assume he hasn't built something at this sort of scale.
- thejigisup 7y ago
  nah i think its a pretty fair assumption
  - woeirua 7y ago
    Let's just ignore the fact that in this case scale has nothing to do with the actual efficiency of the algorithm they implemented. As the link I posted mentioned, had they used a more efficient algorithm they could have used far fewer resources, or used the same resources to scale up further, with much faster response times overall.
  - forgottenpass 7y ago
    99% of people building at "scale" are borrowing bragging rights from a large company they happen to be employed by and/or tools they use while doing zero novel work unique to the size of their deployment. To say that these paper tigers are above the bikeshedding of all the plebs is quintessential software echochamber.
    - dang 7y ago
      "Don't be snarky." "Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html We've had to ask you to stop doing precisely this in the past: https://news.ycombinator.com/item?id=19884138 https://news.ycombinator.com/item?id=19884138 https://news.ycombinator.com/item?id=13587522 https://news.ycombinator.com/item?id=13587522 Unfortunately, you've continued to post like this frequently. If you keep doing that we're going to have to ban you, so could you please review the guidelines and fix this?
- pc86 7y ago
  The vast majority of programmers haven't built something at this sort of scale, so while it's very possible that he has, odds are that he hasn't.
benburleson 7y ago
For future internet-searchers that stumble upon this, it might be helpful to point out that better solutions exist..
- rutenspitz 7y ago
  It would be even more helpful to point out that the article talked about all of this.

buckhx 7y ago

Thanks for the shout out. If anyone has questions or comments feel free to reach out. Also I'm looking for work so if anyone is interested snag my email from my profile.

_virtu 7y ago

I'm currently implementing an rtree in elm. Does anyone have good references about rtrees that they like?

mateo411 7y ago
I think this is the first paper on R Trees. http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf

winrid 7y ago

I've used RTrees for this too (In Java) and they're great. Hundreds of thousands of queries a second per cpu core on millions of data points.

jorblumesea 7y ago

It's funny because had you tried to brute force any of their interview questions (spatial or not) it would have been instant rejection. Often feels like algo analysis is an exercise to get a job and not something engineers actually do, even when required.

woeirua 7y ago
The entire line of argument would have been immediately rejected in a phone screening or an on-site interview at any of the major companies, and even many lesser companies that deal with spatial data. Anyone doing spatial queries and not using existing spatial data structures had better have a really good reason for not doing so.

deleted 7y ago

[deleted]

dang 7y ago

This comment is unacceptable on Hacker News, and I'd like to explain in detail why. Please don't think I'm picking on you personally; we all react like this sometimes. Rather, I want to drive this point home to the community. It's important for discussion quality here! ----- Please omit swipes like "Really, just poor quality work" and "anyone with even a basic understanding" from your posts to HN. It's great to add relevant information, such as an applicable data structure and a link to a good article on the same topic. But it's not great to put others and their work down, and HN has at least two guidelines that ask you not to: When disagreeing, please reply to the argument instead of calling names. "That is idiotic; 1 + 1 is 2, not 3" can be shortened to "1 + 1 is 2, not 3." Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something. Actually, a third guideline is relevant too: Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. The strongest plausible interpretation is not that the engineers lacked a basic understanding of relevant CS—or, for that matter, how to use a search engine, since R-trees would pop up nearly any place you searched about this stuff. The strongest plausible interpretation is that they had some other reason for choosing the implementation they did. For example, perhaps it was efficient enough and they were smartly choosing not to build something more complicated than needed. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html Edit: and it turns out that the article explains why they didn't use R-trees.

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 ago

paggle 7y ago

If you follow American football, your comment reads quite a bit like "Tom Brady has terrible throwing mechanics." Ultimately, it might be right, in some purely academic sense, but in a more relevant sense, good throwing mechanics are those that win you games, and good software implementations are those that meet the business requirements.