On-line pattern matching on similar texts

Roberto Grossi; Costas S. Iliopoulos; Chang Liu; Nadia Pisanti; Solon P. Pissis; Ahmad Retha; Giovanna Rosone; Fatima Vayani; Luca Versari

doi:10.4230/LIPIcs.CPM.2017.9

On-line pattern matching on similar texts

Roberto Grossi, Costas S. Iliopoulos, Chang Liu, Nadia Pisanti, Solon P. Pissis, Ahmad Retha, Giovanna Rosone, Fatima Vayani, Luca Versari

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017
Editors	Jakub Radoszewski, Juha Karkkainen, Jakub Radoszewski, Wojciech Rytter
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959770392
DOIs	https://doi.org/10.4230/LIPIcs.CPM.2017.9
Publication status	Published - 1 Jul 2017
Externally published	Yes
Event	28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017 - Warsaw, Poland Duration: 4 Jul 2017 → 6 Jul 2017

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	78
ISSN (Print)	1868-8969

Conference

Conference	28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017
Country/Territory	Poland
City	Warsaw
Period	4/07/17 → 6/07/17

Funding

Roberto Grossi, Nadia Pisanti, and Giovanna Rosone are partially supported by the project UniPi PRA-2017-44 ("Advanced computational methodologies for the analysis of biomedical data"). Costas S. Iliopoulos is partially supported by the Onassis Foundation. Ahmad Retha is supported by the Graduate Teaching Scholarship scheme of the Department of Informatics at King's College London. Giovanna Rosone is partially supported by the project MIUR-SIR CMACBioSeq ("Combinatorial methods for analysis and compression of biological sequences") grant n. RBSI146R5L. Fatima Vayani is supported by an EPSRC Grant (Doctoral Training Grant #EP/M506357/1).

Keywords

Degenerate strings
Elastic-degenerate strings
On-line algorithms
Pattern matching
String algorithms

Access to Document

10.4230/LIPIcs.CPM.2017.9

Persistent URL (handle)

Persistent link

Cite this

Grossi, R., Iliopoulos, C. S., Liu, C., Pisanti, N., Pissis, S. P., Retha, A., Rosone, G., Vayani, F., & Versari, L. (2017). On-line pattern matching on similar texts. In J. Radoszewski, J. Karkkainen, J. Radoszewski, & W. Rytter (Eds.), 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017 Article 9 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 78). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CPM.2017.9

Grossi, Roberto ; Iliopoulos, Costas S. ; Liu, Chang et al. / On-line pattern matching on similar texts. 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017. editor / Jakub Radoszewski ; Juha Karkkainen ; Jakub Radoszewski ; Wojciech Rytter. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{c6ca97069a144dc6a2716cd1e5cd82ff,

title = "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.",

keywords = "Degenerate strings, Elastic-degenerate strings, On-line algorithms, Pattern matching, String algorithms",

author = "Roberto Grossi and Iliopoulos, {Costas S.} and Chang Liu and Nadia Pisanti and Pissis, {Solon P.} and Ahmad Retha and Giovanna Rosone and Fatima Vayani and Luca Versari",

year = "2017",

month = jul,

day = "1",

doi = "10.4230/LIPIcs.CPM.2017.9",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Jakub Radoszewski and Juha Karkkainen and Jakub Radoszewski and Wojciech Rytter",

booktitle = "28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017",

note = "28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017 ; Conference date: 04-07-2017 Through 06-07-2017",

}

Grossi, R, Iliopoulos, CS, Liu, C, Pisanti, N, Pissis, SP, Retha, A, Rosone, G, Vayani, F & Versari, L 2017, On-line pattern matching on similar texts. in J Radoszewski, J Karkkainen, J Radoszewski & W Rytter (eds), 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017., 9, Leibniz International Proceedings in Informatics, LIPIcs, vol. 78, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, Warsaw, Poland, 4/07/17. https://doi.org/10.4230/LIPIcs.CPM.2017.9

On-line pattern matching on similar texts. / Grossi, Roberto; Iliopoulos, Costas S.; Liu, Chang et al.
28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017. ed. / Jakub Radoszewski; Juha Karkkainen; Jakub Radoszewski; Wojciech Rytter. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. 9 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 78).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On-line pattern matching on similar texts

AU - Grossi, Roberto

AU - Iliopoulos, Costas S.

AU - Liu, Chang

AU - Pisanti, Nadia

AU - Pissis, Solon P.

AU - Retha, Ahmad

AU - Rosone, Giovanna

AU - Vayani, Fatima

AU - Versari, Luca

PY - 2017/7/1

Y1 - 2017/7/1

N2 - 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.

AB - 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.

KW - Degenerate strings

KW - Elastic-degenerate strings

KW - On-line algorithms

KW - Pattern matching

KW - String algorithms

UR - http://www.scopus.com/inward/record.url?scp=85027269941&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027269941&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.CPM.2017.9

DO - 10.4230/LIPIcs.CPM.2017.9

M3 - Conference contribution

AN - SCOPUS:85027269941

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017

A2 - Radoszewski, Jakub

A2 - Karkkainen, Juha

A2 - Radoszewski, Jakub

A2 - Rytter, Wojciech

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017

Y2 - 4 July 2017 through 6 July 2017

ER -

Grossi R, Iliopoulos CS, Liu C, Pisanti N, Pissis SP, Retha A et al. On-line pattern matching on similar texts. In Radoszewski J, Karkkainen J, Radoszewski J, Rytter W, editors, 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2017. 9. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.CPM.2017.9

On-line pattern matching on similar texts

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this