Detecting all repeated patterns in sequences using suffix arrays

Printer-friendly versionSend by email

Pattern detection is a topic of great interest for many sciences. Suffix trees and suffix arrays are the most commonly used data structures for this purpose. For such purposes we have created the novel algorithm ARPaD, which uses the suffix array under a new perspective. With the use of the recursive algorithm ARPaD over the actual suffix array we can perform a fast analysis of any kind of sequences and detect all repeated patterns in linear time complexity. By introducing Longest Expected Repeated Pattern concept we have managed also to reduce the required space capacity of our method to linear for random sequences without any kind of prior knowledge or analysis. Furthermore, the novel process of Moving LERP makes feasible the fast analysis of any kind and size of sequences in linear time and space complexity.

Date(s): 
Wed, 18/06/2014 - 14:00 - 16:00
Where: 
Main Lecture Room (IIT)
Location: 
IIT, NCSR "Demokritos"

© 2018 - Institute of Informatics and Telecommunications | National Centre for Scientific Research "Demokritos"