Serial and parallel methods for I/O efficient suffix tree construction

A method for building a suffix tree for a string of text or data of size n, said method implemented in a parallel computing system comprising a plurality of processor devices, each processor device having an associated memory storage unit, said method comprising:

• allocating, at each corresponding processor device, a fixed amount of memory within an associated memory storage for storing a string cache, said string cache adapted to store an output sub-tree of the suffix tree and a portion of the input string during suffix tree building, wherein the length n of said input string exceeds the allocated fixed memory amount;
• collectively reading said string into said associated allocated memory storage, wherein a processor device of said plurality receives a sub-string portion of said string,
• constructing a set of prefixes (P) for said string, each prefix corresponding to a suffix sub-tree such that, when independently constructed, the corresponding suffix sub-tree does not exceed said fixed amount of associated memory storage at a processor;
• assigning prefixes (p) of said set (P) to said processors;
• building, at each processor device of said plurality, a suffix sub-tree (Tp) for each prefix (p) of said constructed prefix set in said fixed memory amount utilizing a constructor method, said constructor method including:
• partitioning said string into a plurality of equal sized sub-string blocks of size B, and iteratively building a fixed portion of the output suffix sub-tree, wherein during each iteration i, where 0<i<n/B:
• accessing a sub-string block i;
• inserting each suffix starting with the prefix p into the suffix tree such that the input string references from the edges in the partially constructed suffix sub-tree lie in the ith block;
• and
• iteratively accessing each remaining equal sized sub-string block j>i of said plurality, one sub-string block at a time, to process suffixes in each block starting with said prefix (p) that have a string index in said equal sized block i and inserting those suffixes in said tree
• such that during suffix sub-tree building at each iteration, said equal sized sub-string blocks being referenced by said partially constructed suffix sub-tree, and said suffixes being inserted into the sub-tree are maintained within said fixed memory amount and reused;
• and,
• merging said suffix sub-trees to form said suffix tree.

A system for building a suffix tree for a string of text or data of size n, the system comprising:

• a memory;
• a processor coupled to said memory, said processor running program instructions for performing a method comprising:
• providing a processing device having an associated memory storage device,
• allocating a fixed amount of memory within said associated memory storage device for storing an output sub-tree of the suffix tree and a portion of the input string during suffix tree building, wherein the length n of said input string exceeds the allocated fixed memory amount;
• constructing a set of prefixes (p) for said input string;
• building a suffix sub-tree (Tp) for each prefix (p) of said constructed prefix set in said fixed memory amount utilizing a constructor method, said constructor method including:
• partitioning said string into sub-string blocks of size B, and iteratively building a fixed portion of the output suffix sub-tree, wherein during each iteration i, where 0<i<n/B:
• accessing a sub-string block i;
• inserting each suffix starting with the prefix p into the suffix tree such that the input string references from the edges in the partially constructed suffix sub-tree lie in the ith block;
• and
• iteratively accessing each remaining equal sized sub-string block j>i of said plurality, one sub-string block at a time, to process suffixes in each block starting with said prefix (p) that have a string index in said equal sized block i and inserting those suffixes in said tree
• such that during suffix sub-tree building at each iteration, said equal sized sub-string blocks being referenced by said partially constructed suffix sub-tree, and said suffixes being inserted into the sub-tree are maintained within said fixed memory amount and reused;
• and,
• merging said suffix sub-trees to form said suffix tree.

A system for building a suffix tree for a string of text or data of size n comprising:

• a plurality of processor devices, each processor device having an associated memory coupled therewith, each said processor running program instructions for performing a method comprising:
• allocating, at each corresponding processor device, a fixed amount of memory within an associated memory storage for storing a string cache, said string cache adapted to store an output sub-tree of the suffix tree and a portion of the input string during suffix tree building, wherein the length n of said input string exceeds the allocated fixed memory amount;
• collectively reading said string into said associated allocated memory storage, wherein a processor device of said plurality receives a sub-string portion of said string,
• constructing a set of prefixes (P) for said string, each prefix corresponding to a suffix sub-tree such that, when independently constructed, the corresponding suffix sub-tree does not exceed said fixed amount of associated memory storage at a processor;
• assigning prefixes (p) of said set (P) to said processors wherein each processor device includes a list of prefixes to be processed in an iteration;
• building, at each processor device of said plurality, a suffix sub-tree (Tp) for each prefix (p) of said constructed prefix set in said fixed memory amount utilizing a constructor method, said constructor method including:
• partitioning said string into sub-string blocks of size B, and iteratively building a fixed portion of the output suffix sub-tree, wherein during each iteration i, where 0<i<n/B:
• accessing a sub-string block i;
• inserting each suffix starting with the prefix p into the suffix tree such that the input string references from the edges in the partially constructed suffix sub-tree lie in the ith block;
• and
• iteratively accessing each remaining equal sized sub-string block j>i of said plurality, one sub-string block at a time, to process suffixes in each block starting with said prefix (p) that have a string index in said equal sized block i and inserting those suffixes in said tree
• such that during suffix sub-tree building at each iteration, said equal sized sub-string blocks being referenced by said partially constructed suffix sub-tree, and said suffixes being inserted into the sub-tree are maintained within said fixed memory amount and reused;
• and,
• merging said suffix sub-trees to form said suffix tree.