Unwinding Uber’s Most Efficient Service

Illustration by Champa Lo
circa 2013

Geofencing Time Complexity Analysis

via bigocheatsheet.com
q := Point Query
C := Number of cities
V := Number of vertices that define a city boundary
n := Number of fence polygons in a city
v := Number of vertices in a fence polygon

Brute Force

Brute() -> O(Cnv)

Augmented Brute Force

Uber() -> O(CV) + O(nv)

RTree

via wikipedia.org
M := Maximum number of children
Rtree() -> O(logM(Cn)) + O(v)

QuadTree

Bing Maps QuadKeys

S2

Upper East Side covers from s2map.com
T := Features with cell label
QTree() -> O(T) + O(v)

Comparison

q := Point Query
C := Number of cities
V := Number of vertices that define a city boundary
n := Number of fence polygons in a city
v := Number of vertices in a fence polygon
Brute() -> O(Cnv)
Uber() -> O(CV) + O(nv)
Rtree() -> O(logM(Cn)) + O(v)
Qtree() -> O(T) + O(v)

Estimating

NYC Neighborhoods
C := 100 // cities
V := 100 // vertices in city
n := 100 // polygons in city
v := 100 // vertices in polygon
M := 50 // rtree parameter
T := 4 // polygons per cell
Brute() -> 1 * 10^6
Uber() -> 2 * 10^4
Rtree() -> 2.3 * 10^2
Qtree() -> 4 * 10^2

Thinking inside the box

BruteBox() -> O(Cn) + O(v)              -> 1 * 10^4
UberBox() -> O(C) + O(V) + O(n) + O(v) -> 4 * 10^2

Benchmarking Geofencing Algorithms

En garde!
type GeoFence interface {
Add(f *geo.Feature)
Get(c geo.Coordinate) []*geo.Feature
}
func BenchmarkFence(b *testing.B) {
fence := geofence.NewFence()
for _, tract := range tracts {
fence.Add(tract)
}
b.ResetTimer()
for n := 0; n < b.N; n++ {
result = fence.Get(museums["old whitney"])
}
}
interactive

Winding it back up

Adios!

--

--

http://buckhx.com

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store