A large data file in the internet such as a map is served in small pieces, called tiles. To improve the service speed for such data, we can prefetch future tiles while the current one is being displayed. Traditional prefetching techniques examine the transition probabilities among the tiles to predict the next tile to be requested. However, when the tile space is very huge, and a large portion of it is accessed with even distribution, it is very costly to monitor all those tiles. In this paper, we propose a technique that captures the regularity in the tile request pattern by using an NSMC (Neighbor Selection Markov Chain) and predicts future tile requests based on it. The required regularity to use our technique is that the next tile to be requested is dependent on previous k movements (or requests) in the tile space. Map shows such regularity in a sense. Electronic books show a strong such regularity. We show how to build an NSMC and measure its prediction capability through experimentations.
展开▼
