1. A method, comprising: recording observations of data accesses from a cache; dynamically building a prediction model to predict future access patterns based on the recorded observations of data accesses, wherein the prediction model dynamically builds a dictionary of pattern prefixes based on the recorded observations of data accesses; analyzing observations of current data accesses from the cache to predict future access patterns by performing a partial pattern match using the dictionary of pattern prefixes, wherein the observations of data accesses are represented as a tree data structure that includes a plurality of nodes with each node representing a cumulative distinct key count, wherein the partial pattern match predicts one or more suffixes representing the predicted future access patterns; monitoring the plurality of nodes for a current key count of zero, wherein recording the observations of data accesses includes identifying a data access pattern associated with a key associated with the current key count of zero; upon determining that the data accesses are associated with insertion of data into the cache within a time interval of recording the observations of the data accesses, exempting eviction of the inserted data; and evicting data from the cache based on the predicted future access patterns.