Open Access

ARTICLE

Fault Tolerant Suffix Trees

by Iftikhar Ahmad^1,*, Syed Zulfiqar Ali Shah¹, Ambreen Shahnaz², Sadeeq Jan¹, Salma Noor², Wajeeha Khalil¹, Fazal Qudus Khan³, Muhammad Iftikhar Khan⁴

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:

Computers, Materials & Continua 2021, 66(1), 157-164. https://doi.org/10.32604/cmc.2020.012946

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

---