Patent ID: 7356805

Claim:
A method for analyzing reuse patterns of accesses of data by a program naming on a computing device, the computing device having a memory in which the data are stored and from which the data are accessed, the method comprising: (a) running the program on the computing device; (b) monitoring the accesses of the data by the program during step (a); and (c) determining a reuse distance for each datum from among the data accessed by the program during step (a), the reuse distance being a number of distinct data which are accessed between two accesses of the datum, wherein step (c) comprises: determining a last access time of each of the data; organizing a search tree from the last accesses, wherein the search tree comprises a node for each of the data, the node comprising the last access time and a weight of a sub-tree of the node; and compressing the search tree in accordance with a bounded relative error.