A few months ago, we started developing a new version of the smartmove app. In doing so, we not only wanted to adapt the user experience to modern mobile design standards, but also completely revise the technical basis. At the heart of this new app is a full-screen map that shows relevant points of interest (POIs), such as rental car parking spaces. These POIs are static data, meaning that they are not moving and are fixed in their positions. Nevertheless, loading this data turned out to be more difficult than originally thought. Together, in this blog post, we will look at how we managed to avoid major performance problems by using simple tricks. We will see how an initial implementation could be implemented quickly and easily without the aid of complex algorithmic solutions.
Status Quo and Insidious Traps
As already described, in the new version of the smartmove app, we wanted to offer users a prominently placed map with the most important POIs. The underlying data is aggregated within the backend infrastructure and made available to the app via a RESTful API (we provide a rough overview of this backend at the end of the blog post). As you can see, from the perspective of the new smartmove app, the biggest challenge is loading and caching the data locally. Nonetheless, you can fall into bigger traps if you're not careful. This could lead to performance problems or even complex and hard-to-maintain code.
First, it wouldn't be a good idea to load all POIs at once, as this would result in very long loading times. Users of the app are usually only interested in those POIs that are in the current field of view of the map. As a result, loading all POIs spread across the world would unnecessarily require and block a large amount of hardware resources. Not only in the app itself, but also in the backend's network infrastructure.
Second, dividing the POIs into smaller packages to counteract the previous problem could lead to another problem: The same POI could now be loaded several times from the backend; in other words, a POI is loaded that the smartmove app already has in its cache. This would imply that every received packet would have to be compared with all POIs in the cache. A suitable deduplication algorithm would have to be designed, which would therefore of course tie up hardware resources.
Recently, cached POI information may expire. Therefore, a mechanism should be created which makes it possible to record the age of cached information in order to then mark it as expired. In combination with the potential duplication mentioned above, this could result in complex cache management.
As indicated above, we wanted to find a simple solution that would avoid all these problems without further ado, rather than solve them. Come to the next section to see Hotsource's solution.
The solution and how it works
At the beginning of the blog post, I promised a simple solution that would allow us to load geolocations in the new smartmove app and avoid the problem areas mentioned above: We create a grid across the world!
Looking more closely at the coordinate system that spans the globe, we can see that each position can be described by a combination of longitude and latitude. So when this coordinate system is projected onto a 2-dimensional plane (Web Mercator Projection), we get a square that can be cut into a grid.
Despite its simplicity, this solution step is the most essential. Note that the grid spans the entire globus projection without any cells in the grid intersecting. In addition, the width of the grid can be divided by the cell width (and vice versa for their heights), meaning that the cells of the grid, projected back onto the globe, fit together perfectly along the seams. In the end, only one thing is needed to understand Hotsource's solution: The cells represent the packages into which the POIs are divided. For example, look at the second figure. The dashed rectangle represents the field of view of the map and the highlighted grid cells are the cells that are in the field of view. Now we load the POIs within each highlighted grid cell. As a result, the first two pitfalls mentioned in the previous section are simply avoided: Not all POIs are loaded at once (only the necessary ones in the visible area) nor are POIs loaded twice, as grid cells do not overlap. If the map is now moved, we only have to load the POIs from those cells that migrate into the visible area.
The most important aspect of this solution concept is therefore that the grid is placed absolutely on the globe and not relative to the field of vision.
Now you're probably wondering how the grid cell size was set. In addition to the obvious restrictions (the grid width must be divisible by the cell width), there are a number of useful cell sizes. For example, larger cells are helpful when the map is zoomed out further, as the number of backend requests is lower) and vice versa. However, since the map's zoom levels were limited to a reasonable range in the new SmartMove app, we opted for a fixed cell size. If necessary, a dynamic solution can be implemented here in the future.
Another improvement is the app-side caching of loaded POIs. In an effort for simplicity, we decided to use a simple 2-dimensional array that has the same dimensions as the grid on the globe projection. Even though this requires a bit more memory (the entire array is initialized right at the start), it allows very fast cache access. Whenever we receive the POIs of a grid cell, we store them in the associated array cell. If the user later pushes the same grid cell back into the field of view, we can check the array for cached data in a constant amount of time. If they are available, we can directly render pins on the map, otherwise we simply load the POIs from the backend. In addition, a timestamp can simply be added to each array cell so that the cache can be invalidated based on the age of the data. This avoids the last stumbling block from the previous section.
A glimpse behind the curtain
It has already become clear that the revised SmartMove app from Hotsource loads geolocations within rectangular frames.
In the backend, we have therefore used a MongoDB scheme for our POIs, which allows us to save geolocations in GeoJSON format. This format is suitable for storing geographic data structures (GeoJSON Objects). A point on Earth is represented as a GeoJsonPoint.
MongoDB uses geographic indexes to efficiently answer the necessary geographic queries. In this specific case, we use a “GEO_2DSPHERE” index, which is well suited for querying locations on a sphere, i.e. the Earth's surface. In Spring, this can be easily implemented:
@GeoSpatialIndexed (type = GeoSpatialIndexType.geo_2DSphere) private GeoJSONPoint location;
When a query arrives, the backend constructs a so-called “MongoDB $GeoWithin Aggregation Pipeline” based on the desired coordinates. This can then be used to query all geolocations within the specified area (in this case a rectangle). Using two coordinates at opposite corners of the rectangle, we can construct the query as follows:
Criteria GeoCriteria = criteria.Where (“address.location”) .within (new Box (
new GeoJsonPoint (minLongitude, minLatitude),
new GeoJsonPoint (maxLongitude, maxLatitude)
));
We have a few benefits with this approach:
Precision and flexibility: The “MongoDB $GeoWithin Aggregation Pipeline” creates precise queries using our grid cells, which accordingly take into account the curved surface of the globe.
Scalability and Speed: The Combination of Geographic Indexes, Grid Queries, and Dynamic Field of View Updates in the App creates an efficient infrastructure that is easy to scale, even with large data sets and simultaneous queries from multiple users.
Efficiency: By only loading the data that is really necessary for each specific user, we reduce data consumption and use our resources sparingly.
It is therefore clear that even difficult problems can be solved elegantly with clever design. Instead of solving the problem areas described, we simply avoided them. In this way, we quickly offer our users added value.
