Patent ID: 7574563
Filing Date: 2009-08-11
Classification: G06F

Abstract:
1. In a cache memory system comprised of a plurality of information fragments in which a information fragment may include another information fragment, a method for determining whether a set of inclusion relationships includes a cycle, comprising the steps of: examining the set of inclusion relationships to determine whether a depth of inclusions exceeds or equals a threshold; if the depth exceeds or equals the threshold, using graph traversal techniques to determine if a graph comprised of inclusion relationships includes a cycle by representing fragments by vertices in a directed graph, and inclusion relationships by directed edges in the graph; traversing a list of inclusion relationship using two pointers wherein a first pointer traverses one fragment at a time, and a second pointer traverses two fragments at a time such that if the two pointers meet in the graph, a cycle has been detected; if the depth is below the threshold, returning to the step of examining; and if using the graph traversal techniques, no cycle is determined, incrementing file threshold and returning to the step of examining.