@Article{cmc.2020.012946,
AUTHOR = {Iftikhar Ahmad, Syed Zulfiqar Ali Shah, Ambreen Shahnaz, Sadeeq Jan, Salma Noor, Wajeeha Khalil, Fazal Qudus Khan, Muhammad Iftikhar Khan},
TITLE = {Fault Tolerant Suffix Trees},
JOURNAL = {Computers, Materials \& Continua},
VOLUME = {66},
YEAR = {2021},
NUMBER = {1},
PAGES = {157--164},
URL = {http://www.techscience.com/cmc/v66n1/40438},
ISSN = {1546-2226},
ABSTRACT = {Classical algorithms and data structures assume that the underlying
memory is reliable, and the data remain safe during or after processing. However,
the assumption is perilous as several studies have shown that large and inexpensive memories are vulnerable to bit flips. Thus, the correctness of output of a classical algorithm can be threatened by a few memory faults. Fault tolerant data
structures and resilient algorithms are developed to tolerate a limited number of
faults and provide a correct output based on the uncorrupted part of the data. Suf-
fix tree is one of the important data structures that has widespread applications
including substring search, super string problem and data compression. The fault
tolerant version of the suffix tree presented in the literature uses complex techniques of encodable and decodable error-correcting codes, blocked data structures
and fault-resistant tries. In this work, we use the natural approach of data replication to develop a fault tolerant suffix tree based on the faulty memory random
access machine model. The proposed data structure stores copies of the indices
to sustain memory faults injected by an adversary. We develop a resilient version
of the Ukkonen’s algorithm for constructing the fault tolerant suffix tree and
derive an upper bound on the number of corrupt suffixes.},
DOI = {10.32604/cmc.2020.012946}
}