On-line pattern matching on similar texts

Abstract : Pattern matching on a set of similar texts has received much attention, especially recently, mainly due to its application in cataloguing human genetic variation. In particular, many different algorithms have been proposed for the off-line version of this problem; that is, constructing a compressed index for a set of similar texts in order to answer pattern matching queries efficiently. However, the on-line, more fundamental, version of this problem is a rather undeveloped topic. Solutions to the on-line version can be beneficial for a number of reasons; for instance, efficient on-line solutions can be used in combination with partial indexes as practical trade-offs. We make here an attempt to close this gap via proposing two efficient algorithms for this problem. Notably, one of the algorithms requires time linear in the size of the texts' representation, for short patterns. Furthermore, experimental results confirm our theoretical findings in practical terms.
Type de document :
Communication dans un congrès
28th Annual Symposium on Combinatorial Pattern Matching (CPM'17), 2017, Varsovie, Poland. pp.7 - 8, 〈10.4230/LIPIcs.CPM.2017.07〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01526650
Contributeur : Marie-France Sagot <>
Soumis le : mardi 23 mai 2017 - 12:30:28
Dernière modification le : jeudi 15 juin 2017 - 09:09:27
Document(s) archivé(s) le : vendredi 25 août 2017 - 00:57:33

Fichier

CPM17.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Roberto Grossi, Costas Iliopoulos, Chang Liu, Nadia Pisanti, Solon Pissis, et al.. On-line pattern matching on similar texts. 28th Annual Symposium on Combinatorial Pattern Matching (CPM'17), 2017, Varsovie, Poland. pp.7 - 8, 〈10.4230/LIPIcs.CPM.2017.07〉. 〈hal-01526650〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

86