Open Access iconOpen Access

ARTICLE

crossmark

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: email

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

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


Cite This Article

I. Ahmad, S. Zulfiqar Ali Shah, A. Shahnaz, S. Jan, S. Noor et al., "Fault tolerant suffix trees," Computers, Materials & Continua, vol. 66, no.1, pp. 157–164, 2021.



cc 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.
  • 2998

    View

  • 1474

    Download

  • 0

    Like

Related articles

Share Link