System performance of mobile client is very important in mobile environment. Frequently accessed data items are cached to improve performance. Cache replacement technique is used to find appropriate data items for eviction from cache. Selection of suitable cache replacement strategy is very important as cache size is limited. Available policies do not take into account the movement patterns of the client. Here, we propose a new cache replacement policy for location dependent data in mobile environment. We use hidden markov model as a location prediction tool and then huge data is clustered as per location and type of data. This makes the policy adaptive to client’s movement pattern unlike earlier policies that consider the directional / non-directional data distance only. Simulation results show that the proposed policy significantly improves the system performance in comparison to previous schemes in terms of cache hit ratio.