A caching mechanism for a directory service having a backing store. According to the invention, directory search results are cached over a given data capture period, with the information then being used by a data analysis routine to generate a data access history for the user for a particular application. That history is then used to generate a recommended pre-fetch time, a filter key for the pre-fetch, and a preferred cache replacement policy (e.g., static or LRU). Based on that information, a control routine pre-fetches and populates the cache with information that is expected to be needed by the user as a result of that access history.