Vol.66, No.1, 2021, pp.157-164, doi:10.32604/cmc.2020.012946
OPEN ACCESS
ARTICLE
Fault Tolerant Suffix Trees
  • Iftikhar Ahmad1,*, Syed Zulfiqar Ali Shah1, Ambreen Shahnaz2, Sadeeq Jan1, Salma Noor2, Wajeeha Khalil1, Fazal Qudus Khan3, Muhammad Iftikhar Khan4
1 Department of Computer Science and Information Technology, University of Engineering and Technology, Peshawar, 25120, Pakistan
2 Department of Computer Science, Shaheed Benazir Bhutto Women University, Peshawar, 25000, Pakistan
3 Department of Information Technology, FCIT, King Abdulaziz University, Jeddah, Saudi Arabia
* Corresponding Author: Iftikhar Ahmad. Email: ia@uetpeshawar.edu.pk
Received 18 July 2020; Accepted 19 August 2020; Issue published 30 October 2020
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.
Keywords
Resilient data structures; fault tolerant data structures; suffix tree
Cite This Article
I. Ahmad, S. Zulfiqar, A. Shahnaz, S. Jan, S. Noor et al., "Fault tolerant suffix trees," Computers, Materials & Continua, vol. 66, no.1, pp. 157–164, 2021.
This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.