Brief review on optimal suffix data structures

Publications

Brief review on optimal suffix data structures

Year : 2017

Publisher : Springer Verlagservice@springer.de

Source Title : Advances in Intelligent Systems and Computing

Document Type :

Abstract

Suffix tree is a fundamental data structure in the area of combinatorial pattern matching. It has many elegant applications in almost all areas of data mining. This is an efficient data structure for finding solutions in these areas but occupying good amount of space is the major disadvantage of it. Optimizing this data structure has been an active area of research ever since this data structure has been introduced. Presenting major works on optimization of suffix tree is the matter of this article. Optimization in terms of space required to store the suffix tree or time complexity associated with the construction of the tree or performing operation like searching on the tree are major attraction for researcher over the years. In this article, we have presented different forms of this data structure and comparison between them have been studied. A comparative study on different algorithms of these data structures which turns out to be optimized versions of suffix tree in terms of space and time or both required to construct the tree or the time required to perform a search operation on the tree have been presented.