Browse/search for people

Publication - Dr Raphael Clifford

    Dynamic and approximate pattern matching in 2D

    Citation

    Clifford, R, Fontaine, A, Starikovskaia, T & Vildhoj, HW, 2016, ‘Dynamic and approximate pattern matching in 2D’. in: Shunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai (eds) String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. Springer Verlag, pp. 133-144

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

    Full details in the University publications repository