Vectors similarity. Manhattan distance.
In my previous posts, I made an introduction to a vector similarity search, covered Euclidian distance and Cosine similarity, and covered the Jaccard Index in a separate post.
Now it is time to explain the Manhattan distance (also known as the L1 norm or taxicab distance).
Idea behind.
It’s named after the grid of streets in Manhattan which represent the X and Y axis. This kind of vector similarity is applicable in scenarios where movement occurs in a grid-like structure, and the emphasis is on horizontal and vertical paths. Its simplicity and efficiency make it a valuable distance metric in various fields, providing a practical measure of proximity or dissimilarity in constrained environments.
The essence of the distance is to calculate the distance between two N-dimensional points. It’s reflected in the next formula for two dimensions:
Visually it looks like this:
The multidimensional formula for two vectors p(p1, p2…pN) and q(q1, q2…qN) looks the next:
The bigger the result is the bigger the distance between two vectors is.
Example C# implementation.
static int ManhattanDistance(int[] vector1, int[] vector2) {
if (vector1.Length != vector2.Length) {
throw new ArgumentException("Vectors must have the same number of dimensions.");
}
int distance = 0;
for (int i = 0; i < vector1.Length; i++) {
distance += Math.Abs(vector1[i] - vector2[i]);
}
return distance;
}When to use the Manhattan Distance?
This type of vector similarity is applicable in various scenarios where you want to measure the distance or dissimilarity between two points in a grid-based system, especially when movement is constrained to horizontal and vertical paths.
For example, in Computer vision it can be used for edge detection and grid-based movements. In Machine learning, Manhattan distance is used for KNN search and clustering problems. Pathfinding Algorithms can be used in calculating the shortest path between two points. In the domain of Urban Planning, it can help to come up with an optimized layout of city streets, utility lines, and public transportation routes.
