using H3 to get the closest vehicles to a geolocation

I'm developing a system, where I have a list of 100000 geolocations and 10000 geolocations of cars that are moving, and every X seconds, the vehicle's location update occurs, that is, at the same time I can receive N vehicle location updates.

My problem is, every X seconds, the system needs to search for all vehicles that are close to a location L, currently, the system goes through the list of geolocations looking for all vehicles that are within the specific radius, and, applying some search filters in this process.

But, what I noticed is that the distance calculation system, which calculates the distance in a straight line, is what consumes the most time in this filtering process, and as there are several methods within the system that perform these searches, involving distance between the point L and N vehicles, within a radius, this process is becoming slower and slower, because, for each point L, I need to go through the entire list of vehicles.

So, I started looking for systems to index geolocations and that I can also search these indices, using rules for example, get all vehicles within a radius of N km from a geo-location X

H3 seems to be something interesting to me, but, I couldn't find it in their documentation, how can I do this, or, how to have this process of adding N vehicles on the map.

Solution

You can see a tutorial on how to use H3 for radius searches here: https://observablehq.com/@nrabinowitz/h3-radius-lookup

The basic steps are as follows:

Index all your data with H3. Depending on your system, you might keep the result in memory as a hashmap, or in a K/V store, where the H3 index is the key and the value is a list of vehicles in that cell.
To do a search, calculate a k-ring from the point of interest L. The size of the k-ring depends on the H3 resolution you are using for indexing and the radius you want to search.
Do a K/V lookup in your index for every cell in the k-ring, and append the results to some output array. If you care about the exact distance, rather than the approximate distance, you can make the k-ring larger than needed and filter by true distance at this time.

This should be much more efficient - your previous approach scaled with the number of vehicles, where this scales with the size of the k-ring, which is constant.

You'd still need to keep your vehicles indexed as they move. Roughly speaking, every time you get a new location for a vehicle, you need to check whether it's in a new cell, and if so, reindex it. That means you need to store the current cell per each vehicle, either on each vehicle record or in a separate index, as well as your index of vehicles per cell.