With the growth of internet usage, many kinds of useful data are served in the internet. Geographic data such as a map is one of them. However since geographic data is usually very huge, it needs special treatment in serving. One useful technique is tiling. For example, a map is divided into smaller pieces called a tile, and served tile by tile. Since the client usually requests several tiles in sequence, it is beneficial to cache some of the popular tiles for future usage or prefetching ones that are not requested yet but are expected soon. We propose techniques for predicting the right tiles to prefetch. Our techniques are based on an observation that once a tile has been requested there is a strong tendency that neighboring tiles are requested in the next step. Which neighbor has the highest probability is the question we should answer. We propose two techniques. One is probability-based: we compute transition probabilities between tiles and prefetch the most probable neighbor. The other is previous-k-movement approach in which we monitor the previous k movements the client made before reaching the current tile and predict the next movement based on them. A graph called "Neighbor Selection Markov Chain" is used to help the prediction. We explain both methods, compare them, and show experimental results.
展开▼
