Projects per year
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 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).
 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 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 language  English 

Title of host publication  String Processing and Information Retrieval 
Subtitle of host publication  23rd International Symposium, SPIRE 2016, Beppu, Japan, October 1820, 2016, Proceedings 
Editors  Shunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai 
Publisher  Springer Verlag 
Pages  133144 
Number of pages  11 
ISBN (Print)  9783319460499 
DOIs  
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  SpringerVerlag 
Volume  9954 
ISSN (Print)  03029743 
Conference
Conference  SPIRE 2016 

Country  Japan 
City  Beppu 
Period  18/10/16 → 20/10/16 
Fingerprint Dive into the research topics of 'Dynamic and approximate pattern matching in 2D'. Together they form a unique fingerprint.
Projects
 1 Finished
Profiles

Dr Raphael Clifford
 Department of Computer Science  Reader in Algorithm Design
 Intelligent Systems Laboratory
 Theory and Algorithms
Person: Academic , Member, Group lead