Patent ID: 7165147

Claim:
A system prefetching and replacing pages in storage, said storage retaining a plurality of pages, each of said pages comprising a plurality of nodes grouped into one or more regions, said system comprising: (a) a memory management system storing a variable set of pages in memory; (b) a prefetcher recognizing access patterns and usage and prefetching pages among said plurality of pages that fit said access patterns and usage; and (c) a page replacer working in conjunction with said memory management system, and during a traversal, weighting said variable set of pages to identify a subset to be retained and a remainder to be replaced, said subset including pages having a high probability of being revisited and said remainder replaced with a page corresponding to said traversal, and said weighting based upon identifying pivot pages defining traversals that are not strictly parent-to-child or child-to-parent and one or more of the following numerical values associated with each page in said variable set of pages: number of children, number of parents, and region statistics.