The Comparative Analysis Of Distributed Suffix Trees And Traditional Data Management Methods.

Abstract

This article provides a comprehensive review of various methods for implementing suffix trees, comparing them with traditional data representation techniques such as prefix trees and the Burrows-Wheeler transformation (BWT). The reviewed methods include the naive approach, the Ukkonen algorithm, and the Partition and Write Only Top Down (PWOTD) algorithm. Among the methods discussed, the PWOTD algorithm emerges as the most effective for implementing suffix trees. By employing suffix splitting, this approach significantly reduces the main memory requirements for constructing a suffix tree, enabling the creation of independent subtrees entirely in main memory. Despite the increased computational costs associated with partitioning, the PWOTD algorithm offers substantial reductions in space requirements for suffixes and temporary arrays, as well as the tree array. Comparative analysis reveals that suffix trees outperform other methods by efficiently storing and presenting all suffixes of a given string in a compact and accessible format. Moreover, suffix trees support dynamic updates with logarithmic time complexity, facilitating the addition or removal of rows from the original dataset without necessitating complete reconstruction, unlike prefix trees. In summary, this article highlights the effectiveness of the PWOTD algorithm in implementing suffix trees and underscores the advantages of suffix trees over traditional data representation methods. The versatility, efficiency, and dynamic capabilities of suffix trees make them indispensable for a wide range of string processing tasks across various domains, including bioinformatics, text indexing, and natural language processing.