How many of you like to eat, play, and most importantly, drink? (Hopefully, everyone!)
I helped create an app called LocALL. It gives 50,000 recommendations for short trips to eat, play, and drink and support local businesses in Austin. We can extend our app to cover ~400 metropolitan cities in the US and create 20 million recommendations. (Big data and machine learning!)
At the heart of our solution is math. We used spherical geometry and probability to create simple, fast recommendations.
1. Problem statement
Given a set of places to eat, places to play, and places to drink, select 1 of each so that the travel distance is small.
We can make several such recommendations. Hence, come up with a way to choose better recommendations more often.
2. Spherical geometry
Imagine that the three places form the vertices of a triangle. Then, the perimeter would tell us how close the places are to each other. We can also compare different triangles (i.e. recommendations). The question is, how should we measure the distance between two vertices to calculate the perimeter?
A metric is a function that satisfies certain properties and lets us describe the distance between two items in a set. For example, we can use the Euclidean distance,
to describe the distance between points and .
The problem is, the Euclidean distance underestimates the actual distance between two points due to obstacles, such as buildings, water, street turns, and traffic. It also doesn’t match our reality well, since the triangle formed by the Euclidean distance is flat, while the surface of our Earth is curved.
Luckily, we have a branch in geometry dedicated to spheres. The spherical distance, like the Euclidean distance, finds the distance of the shortest path between two points along a sphere. Intuitively, we see that,
i.e. the spherical distance predicts the actual distance better.
The haversine formula,
calculates the spherical distance given the latitude and longitude of each point, and the radius of the Earth. This formula is perfect for our application, as Google APIs use latitudes and longitudes.
When two points are close relative to (e.g. they are in the same city), we can use the Taylor approximation to simplify the formula:
Finally, we use the spherical perimeter to measure the closeness of three places:
We will consider the spherical perimeter to be a metric (of three items), because it is a sum of metrics.
We want to display recommendations with a low metric more often, but still give those with a high metric a fighting chance.
Consider a monotonically decreasing function,
The function models the likelihood of an event given its metric. The lower the metric, the higher the likelihood.
Given a set of recommendations, we can now select ones with a lower metric more often. Set the probability of choosing the -th recommendation to be,
Using spherical geometry and probability, we created simple, fast recommendations for places to eat, play, and drink that are close to each other. Our method is easy to understand and implement—we just need latitudes and longitudes!—but it ignores physical obstacles and opening hours. We will include these constraints in the future.
You can find the code in its entirety here: