Dynamic and approximate pattern matching in 2D

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

doi:10.1007/978-3-319-46049-9_13

Dynamic and approximate pattern matching in 2D

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

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

1 Citation (Scopus)

490 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 language	English
Title of host publication	String Processing and Information Retrieval
Subtitle of host publication	23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings
Editors	Shunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
Publisher	Springer Verlag
Pages	133-144
Number of pages	11
ISBN (Print)	9783319460499
DOIs	https://doi.org/10.1007/978-3-319-46049-9_13
Publication status	Published - 2016
Event	SPIRE 2016: 23rd International Symposium on String Processing and Information Retrieval - Beppu, Oita Prefecture, Beppu, Japan Duration: 18 Oct 2016 → 20 Oct 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer-Verlag
Volume	9954
ISSN (Print)	0302-9743

Conference

Conference	SPIRE 2016
Country/Territory	Japan
City	Beppu
Period	18/10/16 → 20/10/16

Access to Document

10.1007/978-3-319-46049-9_13

Full-text PDF (accepted author manuscript)
This is the accepted author manuscript (AAM). The final published version (version of record) is available online via Springer at http://link.springer.com/chapter/10.1007%2F978-3-319-46049-9_13. Please refer to any applicable terms of use of the publisher.
Accepted author manuscript, 310 KB

Handle.net

Persistent link

Next generation pattern matching
Clifford, R. (Principal Investigator)
1/01/13 → 14/01/19
Project: Research

Dr Raphael Clifford
- Raphael.Cliffordbristol.acuk
- School of Computer Science - Reader in Algorithm Design
- Intelligent Systems Laboratory
- Algorithms and Complexity
Person: Academic , Member, Group lead

Cite this

Clifford, R., Fontaine, A., Starikovskaia, T., & Wedel Vildhoj, H. (2016). Dynamic and approximate pattern matching in 2D. In S. Inenaga, K. Sadakane, & T. Sakai (Eds.), String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings (pp. 133-144). (Lecture Notes in Computer Science; Vol. 9954). Springer Verlag. https://doi.org/10.1007/978-3-319-46049-9_13

Clifford, Raphael ; Fontaine, Allyx ; Starikovskaia, Tatiana et al. / Dynamic and approximate pattern matching in 2D. String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. editor / Shunsuke Inenaga ; Kunihiko Sadakane ; Tetsuya Sakai. Springer Verlag, 2016. pp. 133-144 (Lecture Notes in Computer Science).

@inproceedings{dc98f578c58b4b6a9a8e30af3c2ff747,

title = "Dynamic and approximate pattern matching in 2D",

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 thereexists 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 sizeO(n2(1+1=(1+{"}))) with query time O(n2(1=(1+{"}))m2).",

author = "Raphael Clifford and Allyx Fontaine and Tatiana Starikovskaia and {Wedel Vildhoj}, Hjalte",

year = "2016",

doi = "10.1007/978-3-319-46049-9_13",

language = "English",

isbn = "9783319460499",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "133--144",

editor = "Shunsuke Inenaga and Kunihiko Sadakane and Tetsuya Sakai",

booktitle = "String Processing and Information Retrieval",

address = "Germany",

note = "SPIRE 2016 : 23rd International Symposium on String Processing and Information Retrieval ; Conference date: 18-10-2016 Through 20-10-2016",

}

Clifford, R, Fontaine, A, Starikovskaia, T & Wedel Vildhoj, H 2016, Dynamic and approximate pattern matching in 2D. in S Inenaga, K Sadakane & T Sakai (eds), String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. Lecture Notes in Computer Science, vol. 9954, Springer Verlag, pp. 133-144, SPIRE 2016, Beppu, Japan, 18/10/16. https://doi.org/10.1007/978-3-319-46049-9_13

Dynamic and approximate pattern matching in 2D. / Clifford, Raphael; Fontaine, Allyx; Starikovskaia, Tatiana et al.
String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. ed. / Shunsuke Inenaga; Kunihiko Sadakane; Tetsuya Sakai. Springer Verlag, 2016. p. 133-144 (Lecture Notes in Computer Science; Vol. 9954).

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

TY - GEN

T1 - Dynamic and approximate pattern matching in 2D

AU - Clifford, Raphael

AU - Fontaine, Allyx

AU - Starikovskaia, Tatiana

AU - Wedel Vildhoj, Hjalte

PY - 2016

Y1 - 2016

N2 - 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 thereexists 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 sizeO(n2(1+1=(1+"))) with query time O(n2(1=(1+"))m2).

AB - 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 thereexists 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 sizeO(n2(1+1=(1+"))) with query time O(n2(1=(1+"))m2).

U2 - 10.1007/978-3-319-46049-9_13

DO - 10.1007/978-3-319-46049-9_13

M3 - Conference Contribution (Conference Proceeding)

SN - 9783319460499

T3 - Lecture Notes in Computer Science

SP - 133

EP - 144

BT - String Processing and Information Retrieval

A2 - Inenaga, Shunsuke

A2 - Sadakane, Kunihiko

A2 - Sakai, Tetsuya

PB - Springer Verlag

T2 - SPIRE 2016

Y2 - 18 October 2016 through 20 October 2016

ER -

Clifford R, Fontaine A, Starikovskaia T, Wedel Vildhoj H. Dynamic and approximate pattern matching in 2D. In Inenaga S, Sadakane K, Sakai T, editors, String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. Springer Verlag. 2016. p. 133-144. (Lecture Notes in Computer Science). Epub 2016 Oct 18. doi: 10.1007/978-3-319-46049-9_13

Dynamic and approximate pattern matching in 2D

Abstract

Publication series

Conference

Access to Document

Handle.net

Fingerprint

Projects

Next generation pattern matching

Profiles

Dr Raphael Clifford

Cite this