Behavior-driven Tile Caching in Web GIS Applications

Abstract

Tile-based Web GIS is an increasingly popular way of displaying maps online, where the map view consists of square images called tiles. In a typical setting, a majority of the tiles on a tile server remains unused over large amounts of time. The setting of the study is the company Kartena. Investigations are performed which tells if the number of cached tiles at the company Kartena can be reduced while still keeping an acceptable cache hit ratio. The goal is to create an algorithm which gives as good cache hit ratios as possible, meaning that as many accesses as possible are cached server-side. By identifying typical navigation behavior of web map users, optimizations can be made on the server. By identifying and only rendering a small subset of the total amount of tiles in advance, storage requirements as well as rendering times go down. Two studies related to the problem are identified. Quinn and Gahegan use heuristics and heat maps to create a predictive model, and Garcia et al. use past usage statistics to predict future usage. Using the mentioned studies as well as heat maps and statistical analysis, an algorithm is created which - given a number of tile access logs and a set of domain-specific heuristics - provides a recommendation of which tiles that are suitable for caching. An experiment is performed by examining real usage of the applications and see how well the new model would perform in terms of cache-hit ratio. Depending on the amount of training data used, the experiment indicates that hit ratios of 95% and upwards are possible. The results suggest that the algorithm can be used to realize an on-demand caching solution at Kartena. The resulting algorithm can also be used to reduce storage costs and rendering times in similar settings.