Patent ID: 6963959

Claim:
A method for reorganizing data in a storage device for improved performance, the device storing data as data units, the method comprising the steps of: allocating a reorganization region; determining a plurality of most repeatedly requested sequences of units, the units in the sequences being requested sequentially, wherein determining includes: identifying an edge with a relatively large weight; Including the source unit and destination unit associated with the identified edge in a target sequence; Identifying subsequent edges originating from and terminating at the included units, each subsequent edge having a generally large weight; adding the units associated with the subsequent edges to the target sequence, wherein the target sequence is output when the largest of the weights associated with the identified edges falls below a threshold; and Outputting the target sequence as one of the most repeatedly requested sequences; copying the determined sequences into the reorganization region; and servicing requests for data using data in the reorganization region, wherein the data requests are represented as a graph having a plurality of vertices and edges, each vertex representing a data unit, each edge connecting a vertex representing a source data unit with a vertex representing a destination data unit, the edge being associated with a weight indicating a relative frequency of the destination unit being requested shortly after the source unit; and the most repeatedly requested sequences are determined using the graph.