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).
- 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 language | English |
---|---|
Title of host publication | Proceedings of the 23rd International Symposium on String Processing and Information Retrieval (SPIRE 2016) |
Editors | Shunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai |
Publisher | Springer |
Publication date | 2016 |
Pages | 133-144 |
ISBN (Print) | 978-3-319-46048-2 |
ISBN (Electronic) | 978-3-319-46049-9 |
DOIs | |
Publication status | Published - 2016 |
Event | 23rd International Symposium on String Processing and Information Retrieval - Beppu, Japan Duration: 18 Oct 2016 → 20 Oct 2016 Conference number: 23 https://sites.google.com/site/spire2016jp/ |
Conference
Conference | 23rd International Symposium on String Processing and Information Retrieval |
---|---|
Number | 23 |
Country/Territory | Japan |
City | Beppu |
Period | 18/10/2016 → 20/10/2016 |
Internet address |
Series | Lecture Notes in Computer Science |
---|---|
Volume | 9954 |
ISSN | 0302-9743 |