Share Your Search Results with Your Neighbours
Background
I was developing a mobile application that allows users to exchange objects. Users of this application can search, according to several criteria, the surrounding objects made a
vailable by other users. So far, nothing extraordinary.
When the user opens the application, it automatically loads the surrounding objects in the form of a list or a map.
The back-end must then return objects within a radius of 10 km from the user’s position. Other filters can also be applied.
As a back-end developer, I am always looking for a way to lighten the traffic load. So I wondered how to pool queries based on users’ locations.
Object lists are not customized for each user. Therefore, the result of the GET query /objects?lat=45.5575301&lng=-73.9916687 could be cached on a CDN with a simple header: cache-control: public, max-age=600
However, this cache would be ineffective because it is unlikely, if not impossible, for two users to have exactly the same position. The combination of latitude and longitude almost acts as a unique query identifier. This nullifies caching.
So my question was “How can I use the same position signature for nearby users”?
Approximation of the position
In the context of this application, it was acceptable for the position of the user performing the search to be inaccurate. Indeed, for two searches within a radius of 10 km, sorted by distance, with the central points being 500 meters apart, only the most distant results differ (except for a few variations in order).
In my case, these variations were negligible.
I was therefore looking for a solution to perform this position approximation.
Truncating the positions
The first solution that came to mind is simply to truncate the latitude and longitude values. You just had to define at which decimal you want to truncate: thousandth, ten-thousandth, hundred thousandth, etc. ?
Before sending the request to the back-end, the front-end would have to perform this truncation:
the URL /objects?lat=45.5575301&lng=-73.9916687 would then become /objects?lat=45.5575&lng=-73.9916, and the cache would be resistant to small position variations.
Issues
The first issue lies in the accuracy of the approximation. We want to have an approximation of 500 meters. A variation of 0.01 degrees of latitude corresponds to a distance of 1.11 km and a variation of 0.001 degrees of latitude corresponds to 111 meters. I could not choose the precision of the approximation. I would have to choose between two values, one too large and one too small.
The second issue is the deformation of the approximation zones along a meridian. Indeed, 0.01 degrees of longitude correspond to 1.11 km of distance at the equator, but this same variation corresponds to 786 meters at the Montreal latitude and 556 meters at the Oslo latitude.
The approximations are not homogeneous across the globe. At the latitude of the equator, I would obtain squares of 1.11 km on each side. But at the level of Oslo, I would get rectangles of 1.11 km by 556 meters.
Using an existing algorithm
The Geohash algorithm (http://geohash.org/) also truncates latitude and longitude.
In my use case, this would then lead to the same problems as the ones previously encountered.
Solution
I then came to write my own algorithm to cancel this shrinking effect along a meridian. Its goal is to decompose the globe into square areas while being able to precisely define the size of these squares. Every position contained in a square is magnetized to the center of the square.
This is like seeing the globe as a disco ball in which you can define the size of the mirrors.
Earth pixel algorithm
Working on the MEAN stack, I wrote this library in JavaScript. I named it EarthPixel: https://www.npmjs.com/package/earth-pixel
It is simple to use. First of all, you have to define the size of a square (a pixel).
A first method allows to encode a geographical position in a key, coding for the square containing this position.
A second method allows to decode this key into a geographical position: the center of the square.
The format of the key is 9c5f-75ba-40c9. The first part codes for precision, the second for latitude and the third for longitude.
Example of implementation
Encoding
On the front-end side, we capture the user’s position and then create the key of the corresponding pixel:
A slightly different position would have produced the same key:
Decoding
On the back-end side, this key is decoded like this:
Caching
For close positions, EarthPixel will produce identical keys and the query /objects?key=9c5f-75ba-40c9 can be cached efficiently.
Online test page
Here is a visual example to understand the cutting of the globe into squares: https://dl83b.csb.app/
Thanks for reading!
Edouard Demotes from Tractr
