SERIAL AND PARALLEL METHODS FOR I/O EFFICIENT SUFFIX TREE CONSTRUCTION

摘要

System and method for suffix tree creation for large input data/text streams. The methodology leverages the structure of suffix trees to build a suffix tree by simultaneously tiling accesses to both the input string as well as the partially constructed suffix tree. The end result enables the indexing of very large input strings and at the same time maintain a bounded working set size and a fixed memory footprint. The method is employed for serial processing. Further, a scalable parallel suffix tree construction is realized that is suitable for implementation on parallel distributed memory systems that use effective collective communication and in-network caching. The methodology is also applied for suffix link recovery in both serial and parallel implementations.