String Algorithms
The group develops and analyzes efficient algorithms for information retrieval. Our perspective is algorithm engineering. We consider both exact and approximate string searching as well as indexing methods. Also algorithms for data compression and computational biology are studied.
Slides: nutshell (pptx, pdf), highlights (pdf)
Members
Present staff
- Prof. Jorma Tarhio (leader)
- Dr. Kerttu Pollari-Malmi
- M.Sc. Sukhpal Ghuman
- Fernando Fiori
- Waltteri Pakalén
Alumni
- Dr. Tamanna Chhabra
- Dr. Elena Czeizler
- Dr. Travis Gagie
- Dr. Emanuele Giaquinta
- M.Sc. Tommi Hirvola
- Prof. Jan Holub
- M.Sc. Petri Kalsi
- Dr. Kalle Karhu
- Prof. Sami Khuri
- Mr. Petteri Kiiskinen
- M.Sc. Juho Mäkinen
- Dr. Hannu Peltola
- M.Sc. Jussi Rautio
- Dr. Leena Salmela
Projects
- Indexed and Approximate Search of Multiple Patterns (IASMP) (Academy of Finland, 2010-2014)
- Algorithms for Genomic Search Problems (Academy of Finland, 2006-08)
Publications (recent)
S. Ghuman, J. Tarhio: Jumbled matching with SIMD. In: PSC '16, 15th Prague Stringology Conference, 2016.
T. Chhabra, S. Faro, M. O. Külekci, J. Tarhio: Engineering order-preserving pattern matching with SIMD parallelism. Software: Practice and Experience, 2016.
T. Chhabra, J. Tarhio: A filtration method for order-preserving matching. Information Processing Letters 116, 2 (2016), 71–74.
E. Giaquinta: Run-length encoded nondeterministic KMP and suffix automata. In: Proc. CIAA '15, Implementation and Application of Automata, 20th International Conference, Lecture Notes in Computer Science 9223, Springer 2015, 102–113.
T. Chhabra, E. Giaquinta, J. Tarhio: Filtration algorithms for approximate order-preserving matching. In: Proc. SPIRE '15, String Processing and Information Retrieval, 22nd International Symposium, Lecture Notes in Computer Science 9309, Springer 2015, 177–187.
T. Chhabra, S. Ghuman, J. Tarhio: Tuning algorithms for jumbled matching. In: Proc. PSC '15, 14th Prague Stringology Conference, 2015, 36–46.
T. Chhabra, M. O. Kulekci, J. Tarhio: Alternative algorithms for order-preserving matching. In: Proc. PSC '15, 14th Prague Stringology Conference, 2015, 57–66.
T. Flouri, E. Giaquinta, K. Kobert, E. Ukkonen: Longest common substrings with k mismatches Information Processing Letters 115, 6-8 (2015), 643–647.
E. Giaquinta, A. Mishra, L. Pozzi: Maximum convex subgraphs under I/O constraint for automatic identification of custom instructions IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 34, 3 (2015), 483-494.
Courses
String Algorithms. (Last time: Spring 2016.)