News for hackers. Stuff that matters.
Re:How We Built Uber’s Highest Query per Second Service Usin... by openasocket on Tuesday March 01, 2016 @05:53PM (#11206784)
FYI, searching the R-tree also has runtime complexity of O(N) in the worst case. I believe there is some R-tree variant which actually provides asymptotically better performance than the naive case, but it is very complicated and tends to perform worse on average in practice.

Source: just spent two months implementing R-trees in Rust

Re:How We Built Uber’s Highest Query per Second Service Usin... by rosshemsley on Tuesday March 01, 2016 @07:07PM (#11207219)
Yes, but the O(N) is generally only for pathological inputs.

Geo data is generally nicely distributed. R-tree (or similar) is the correct solution here.

Re:How We Built Uber’s Highest Query per Second Service Usin... by urschrei on Tuesday March 01, 2016 @06:49PM (#11207124)
Was just looking for an implementation last week. Is it public?
Re:How We Built Uber’s Highest Query per Second Service Usin... by openasocket on Tuesday March 01, 2016 @07:05PM (#11207212)
Not yet, but it will probably be open sourced sometime soon.