20 Feb 2022, 18:28

Creating Unique Coordinate Keys

In a previous post, I examined creating a data structure for quickly getting a value based on a coordinate. For context, here a coordinate is meaning a longitude, latitude pair. This pair can often be found as an array ([0.1, 0.2] etc), and sometimes as a property on an object ({ lng: 0.1, lat: 0.2 }).

In this post, I want to dig a bit deeper and examine a new key creation approach that saves on memory and speed whilst also opening up new avenues for more simply implementing data structures such as Sets for coordinates.

Maps, Sets and Strict Equality

First a bit of background. In JavaScript two arrays are only said to be equal if they reference the same array, even if the values are the same. This means can’t use two identical coordinate arrays to exclusively associate to some piece of data. For example:

const map = new Map();
map.set([-0.118092, 51.509865], "a");
map.set([-0.118092, 51.509865], "b");

// For those familiar with JS Map and Set behaviour,
// the following may not be a suprise:

map.get([-0.118092, 51.509865]); // Returns undefined
map.size; // Return 2, as each array creates it's own entry

Now you might be able to see that in some use cases we might think of a coordinate as a unique key and not be concerned about object equality - we just care that the values match. In some languages, tuples of a set length with the same values can be considered equal, and this is the same logic we might want to apply here.

What about toString?

The second problem it gets around is perhaps how one might intuatively try to solve this which is to use toString:

const map = new Map();
const key = [-0.118092, 51.509865].toString();
map.set(key, "a");
map.set(key, "b");

map.get([-0.118092, 51.509865]); // Returns "b"
map.size; // Return 1, as each array creates it's own entry

This gets us closer to what we want and could have been one way to achieve what we wanted in the original blog post. However, unfortunately toString is a somewhat slow operation in JavaScript.

The approach in the original post gets around both of these issues by using nested Maps, so setting in the CoordinateMap creates a Map for the longitude value and then another nested one for the latitude value. This works, but in the worst case means you end up with two Maps for each coordinate. Understandably this could be viewed as excessive.

Is there a fast way to create a unique key?

I’ve been experimenting with a fast way to create a key - the logic works like this: in Mathematics, there is a concept of a pairing function that allows you to uniquely map two natural numbers to a single larger natural number. In our case, we can think of natural numbers as positive integers. This got me thinking, if we can encode our coordinates as positive integers we can use one of the pairing functions to create a single key. If we work on the assumption that we can pin the coordinates to a maximum precision, say a very generous 9 decimals, then thankfully we can fit the numbers into a single digit (JavaScripts maximum integer size is a whopping 9007199254740991 as specified by IEEE 754).

Using Szudzik’s Elegant pairing function we can achieve this doing the following:

export function pairCoordinate(
  longitude: number,
  latitude: number,
  factor = 10000000 // 9 digit precision
) {
  // Make longitude and latitude postive
  // Ensure they are integers
  const x = ((longitude + 180) * factor) | 0;
  const y = ((latitude + 90) * factor) | 0;

  // Szudzik pairing
  return x >= y ? x * x + x + y : y * y + x;
}

This approach for generating unique keys for a coordinate is about 45x faster than using toString. In a future post I will examine how we can reimplement at CoordinateMap and also look at implementing a CoordinateSet to quickly check for presence of a given coordinate.