Dynamic and approximate pattern matching in 2D

Raphaël Clifford, Allyx Fontaine, Tatiana Starikovskaya, Hjalte Wedel Vildhøj

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

458 Downloads (Pure)

Abstract

We consider dynamic and online variants of 2D pattern matching between an mXm pattern and an nXn text. All the algorithms we give are randomised and give correct outputs with at least constant probability.
- For dynamic 2D exact matching where updates change individual symbols in the text, we show updates can be performed in O(log2 n) time and queries in O(log2 m) time.
- We then consider a model where an update is a new 2D pattern and a query is a location in the text. For this setting we show that Hamming distance queries can be answered in O(log m + H) time, where H is the relevant Hamming distance.
- Extending this work to allow approximation, we give an efficient algorithm which returns a (1+ε) approximation of the Hamming distance at a given location in O(ε−2 log2 m log log n) time.

Finally, we consider a different setting inspired by previous work on locality sensitive hashing (LSH). Given a threshold k and after building the 2D text index and receiving a 2D query pattern, we must output a location where the Hamming distance is at most (1 + ε)k as long as there exists a location where the Hamming distance is at most k.
- For our LSH inspired 2D indexing problem, the text can be preprocessed in O(n2(4/3+1/(1+ε)) log3 n) time into a data structure of size O(n2(1+1/(1+ε))) with query time O(n2(1/(1+ε))m2).
Original languageEnglish
Title of host publicationProceedings of the 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016)
EditorsShunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
PublisherSpringer
Publication date2016
Pages133-144
ISBN (Print)978-3-319-46048-2
ISBN (Electronic) 978-3-319-46049-9
DOIs
Publication statusPublished - 2016
Event23rd International Symposium on String Processing and Information Retrieval - Beppu, Japan
Duration: 18 Oct 201620 Oct 2016
Conference number: 23
https://sites.google.com/site/spire2016jp/

Conference

Conference23rd International Symposium on String Processing and Information Retrieval
Number23
Country/TerritoryJapan
CityBeppu
Period18/10/201620/10/2016
Internet address
SeriesLecture Notes in Computer Science
Volume9954
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Dynamic and approximate pattern matching in 2D'. Together they form a unique fingerprint.

Cite this