Fault Tolerant Suffix Trees  

作　　者：Iftikhar Ahmad 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 [4]Department of Electrical Engineering,University of Engineering and Technology,Peshawar,25120,Pakistan

出　　处：《Computers, Materials & Continua》2021年第1期157-164,共8页计算机、材料和连续体（英文）

摘　　要：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.Suffix 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.

关 键 词：Resilient data structures fault tolerant data structures suffix tree 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]