Dynamic and approximate pattern matching in 2D

Raphael Clifford, Allyx Fontaine, Tatiana Starikovskaia, Hjalte Wedel Vildhoj

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

338 Downloads (Pure)

Abstract

We consider dynamic and online variants of 2D pattern matching between an m x m pattern and an n x n 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 + E) 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 pre-processed 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 publicationString Processing and Information Retrieval
Subtitle of host publication23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings
EditorsShunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
PublisherSpringer Verlag
Pages133-144
Number of pages11
ISBN (Print)9783319460499
DOIs
Publication statusPublished - 2016
EventSPIRE 2016: 23rd International Symposium on String Processing and Information Retrieval - Beppu, Oita Prefecture, Beppu, Japan
Duration: 18 Oct 201620 Oct 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer-Verlag
Volume9954
ISSN (Print)0302-9743

Conference

ConferenceSPIRE 2016
CountryJapan
CityBeppu
Period18/10/1620/10/16

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

Cite this