Succinct Data Structures

Abstract

A suffix array stores the lexicographic order of all suffixes of a given string. For example, the suffix array for 'dog' is [1,3,2], because the suffixes of 'dog' are 'dog', 'g' and 'og', in this lexicographic order. The suffix array is a very space economical data structure (it takes only 4n bytes for a string of length n) and can be constructed extremely fast (the theoretical time complexity is O(n), although other algorithms exist that have a better practical performance). The suffix array can be used for various tasks in the field of string matching. One important application is to find the number of matches (sometimes also their positions) of a given query string. With an additional array (the LCP-array) the suffix array has been shown to be almost equivalent to the well-known suffix tree.

Our research is focused on applications of suffix- and LCP-arrays in data mining. More precisely, we use them to extract all frequent strings from a given (positive) database of strings. We further use the same data structures to exclude all strings that are also frequent in a different (negative) database of strings. The biological relevance of this task can be seen in the following example: suppose a genetic disease is conjectured to be caused by a defect on the X-chromosome, but it is unknown where and how this failure occurs. One can then collect the genetic sequences of the X-chromosome of 1000 ill patients in the positive database, and likewise the genetic sequences of 1000 healthy persons in the negative database. Then all patterns that occur frequently (or always) in the positive database and not too often (or never) in the negative database are potential indicators for the genetic defect under consideration.

Several interesting theoretical and practical problems arise when working in this field, including external memory construction and processing of suffix- and LCP-arrays, specialized solutions for range-minimum-queries (RMQs) in LCP-arrays, etc. Our work is situated on the borderline between algorithmics and data mining and tries to integrate solutions from one of these fields in the other.

Software

Linear Frequent String Miner and Emerging Substring Miner (PKDD'06)
(last update: 2007/01/04) [C++ source package]
New Representation of RMQ Information (CPM'06)
(last update: 2007/02/01) [C++ source package]
Succinct Representation of RMQ Information (ESCAPE'07)
(last update: 2007/03/16) [C++ source package]
Suffix Arrays on Words (CPM'07)
(last update: 2007/03/30) [C++ source package]

Publications

Benjamin Albrecht, Volker Heun, Space Efficient Modifications to Structator - a Fast Index-Based Search Tool for RNA Sequence-Structure Patterns, Proceedings of the 11th International Symposium on Experimental Algorithms (SEA 2012) (Ralf Klasing, ed.), Springer Verlag, vol. 7276, Bordeaux, France, June 7-9, 2012, pp. 27-38, 2012.

Johannes Fischer, Volker Heun, Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays, SIAM Journal on Computing, vol. 40, no. 2, pp. 465-492, 2011.

Johannes Fischer, Volker Heun, Finding Range Minima in the Middle: Approximations and Applications, Mathematics in Computer Science, vol. 3, no. 1, pp. 17-30, 2010.

Johannes Fischer, Volker Heun, Range Median of Minima Queries, Super-Cartesian Trees, and Text Indexing, Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA’08) (Mirka Miller, Koichi Wada, eds.), College Publications, vol. 12, September 13-15, 2008, Nagoya, Japan, pp. 239-252, 2010.

BiBTex

Johannes Fischer, Volker Heun, Range Median of Minima Queries, Super-Cartesian Trees, and Text Indexing, Local Proceedings of the 19th International Workshop on Combinatorial Algorithms (IWOCA’08) (Mirka Miller, Koichi Wada, eds.), Nagoya, Japan, September 13-15, 2008, pp. 239-252, 2008.

BiBTex

Johannes Fischer, Volker Heun, Horst Martin Stühler, Practical Entropy-Bounded Schemes for O(1)-Range Minimum Queries, Proceedings of the 2008 Data Compression Conference (DCC’08) (J.A. Storer, M.W. Marcellin, eds.), IEEE Computer Society, Snowbird, Utah, U.S.A., March 25-27, 2008, pp. 272-281, 2008.

Johannes Fischer, Volker Heun, A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array, Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE’07) (Bo Chen, Mike Paterson, Guochuan Zhang, eds.), Springer-Verlag, vol. 4614, Hangzhou, China, April 7-9, 2007, pp. 459-470, 2007.

Paolo Ferragina, Johannes Fischer, Suffix Arrays on Words, Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM’07) (Bin Ma, Kaizhong Zhang, eds.), Springer-Verlag, vol. 4580, London, Ontario, July 9-11, 2007, pp. 328-339, 2007.

Amihood Amir, Johannes Fischer, Moshe Lewenstein, Two-Dimensional Range Minimum Queries, Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM’07), (Bin Ma, Kaizhong Zhang, eds.), Springer-Verlag, vol. 4580, London, Ontario, July 9-11, 2007, pp. 286-294, 2007.

Johannes Fischer, Volker Heun, Stefan Kramer, Optimal String Mining Under Frequency Constraints, Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD’06) (J. Fürnkranz, T. Scheffer, M. Spiliopoulou, eds.), Springer-Verlag, vol. 4213, Berlin, Germany, September 18-22, 2006, pp. 139-150, 2006.

Johannes Fischer, Volker Heun, Theoretical and Practical Improvements on the RMQ-Problem with Applications to LCA and LCE, Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching (CPM’06) (Moshe Lewenstein, Gabriel Valiente, eds.), Springer-Verlag, vol. 4009, Barcelona, Spain, July 5-7, 2006, pp. 36-48, 2006.

Johannes Fischer, Volker Heun, Stefan Kramer, Fast Frequent String Mining Using Suffix Arrays, Proceedings of the 5th IEEE International Conference on Data Mining (ICDM’05), IEEE Computer Society, Houston, TX, USA, November 27-30, 2005, pp. 609-612, 2005.

Johannes Fischer, Volker Heun, Stefan Kramer, Fast Frequent String Mining Using Suffix Arrays, TUM-I0512, Institut für Informatik der Technischen Universität München, no. TUM-I0512, 2005.

Annabelle Teresa Klarl, Konstruktion und Anwendung von Affixarrays, Bachelor Thesis, LFE Bioinformatik, LMU München, 2008.

BiBTex

Johannes Fischer, Data Structures for Efficient String Algorithms, PhD Thesis, LMU München, 2007.

Horst Martin Stühler, Practical Performance of Preprocessing Schemes for Range Minimum Queries, Diploma Thesis, LFE Bioinformatik, LMU München, 2007.

BiBTex

Sebastian Bauer, Vergleich und Visualisierung von Algorithmen zur Konstruktion von Suffix-Arrays anhand sehr langer Texte, Bachelor Thesis, LFE Bioinformatik, LMU München, 2006.