TileHeat: a framework for tile selection

TY - GEN

T1 - TileHeat

T2 - 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

AU - Kefaloukos, Pimin Konstantin Balic

AU - Vaz Salles, Marcos António

AU - Zachariasen, Martin

N1 - Conference code: 20

PY - 2012

Y1 - 2012

N2 - Public geospatial services are now commonly available on the Web. These services often render maps to users by dividing the maps into tiles. Given that geospatial services experience significant user load, it is desirable to pre-compute tiles at a time of low load in order to increase overall performance. Based on our analysis of the request log of a public geospatial service provider, we observe that times of low load occur with a periodic pattern. In addition, our analysis shows that tile access patterns exhibit strong spatial skew. Based on these observations, we propose an adaptive strategy restricting the set of tiles that are pre-computed to fit the low load time window. Ideally, the restricted tile set should deliver performance comparable to the full tile set. To achieve this result, tiles should be selected based on their expected popularity. Our key observation is that the popularity of a tile can be estimated by analyzing the tiles that users have previously requested. Our adaptive strategy constructs heatmaps of previous requests and uses this information to decide which tiles to pre-compute. We examine two alternative heuristics, one of which exploits that nearby tiles have a high likelihood of having similar popularity. We evaluate our methods against a real production workload, and observe that the latter heuristic achieves a 25% increase in the hit ratio compared to current methods, without pre-computing a larger set of tiles.

AB - Public geospatial services are now commonly available on the Web. These services often render maps to users by dividing the maps into tiles. Given that geospatial services experience significant user load, it is desirable to pre-compute tiles at a time of low load in order to increase overall performance. Based on our analysis of the request log of a public geospatial service provider, we observe that times of low load occur with a periodic pattern. In addition, our analysis shows that tile access patterns exhibit strong spatial skew. Based on these observations, we propose an adaptive strategy restricting the set of tiles that are pre-computed to fit the low load time window. Ideally, the restricted tile set should deliver performance comparable to the full tile set. To achieve this result, tiles should be selected based on their expected popularity. Our key observation is that the popularity of a tile can be estimated by analyzing the tiles that users have previously requested. Our adaptive strategy constructs heatmaps of previous requests and uses this information to decide which tiles to pre-compute. We examine two alternative heuristics, one of which exploits that nearby tiles have a high likelihood of having similar popularity. We evaluate our methods against a real production workload, and observe that the latter heuristic achieves a 25% increase in the hit ratio compared to current methods, without pre-computing a larger set of tiles.

KW - geospatial services, heatmaps, predictive models, tile caching

U2 - 10.1145/2424321.2424366

DO - 10.1145/2424321.2424366

M3 - Article in proceedings

SN - 978-1-4503-1691-0

SP - 349

EP - 358

BT - Proceedings of the 20th International Conference on Advances in Geographic Information Systems

PB - Association for Computing Machinery

Y2 - 6 November 2012 through 9 November 2012

ER -