**Conference Paper:**Dynamic dictionary matching and compressed suffix trees

Title | Dynamic dictionary matching and compressed suffix trees |
---|---|

Authors | Chan, HL2 Hon, WK2 Lam, TW2 Sadakane, K1 |

Keywords | Mathematics computers |

Issue Date | 2005 |

Publisher | Society for Industrial and Applied Mathematics. |

Citation | Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2005, p. 13-22 [How to Cite?] |

Abstract | Recent breakthrough in compressed indexing data structures has reduced the space for indexing a text (or a collection of texts) of length n from O(n log n) bits to O(n) bits, while allowing very efficient pattern matching. Yet the compressed nature of such indices also makes them difficult to update dynamically. This paper presents the first O(n)-bit representation of a suffix tree for a dynamic collection of texts whose total length is n, which supports insertion and deletion of a text T in O(|T| log2 n) time, as well as all suffix tree traversal operations, including forward and backward suffix links. This work can be regarded as a generalization of the compressed representation of static texts. Our new suffix tree representation serves as a core part in a compact solution for the dynamic dictionary matching problem, i.e., providing an O(d)-bit data structure for a dynamic collection of patterns of total length d that can support the dictionary matching query efficiently. When compared with the O(d log d)-bit suffix tree based solution of Amir et al., the compact solution increases the query time by roughly a factor of log d only. In the study of the above results, we also derive the first O(n)-bit representation for maintaining n pairs of balanced parentheses in O(log n/log log n) time per operation, matching the time complexity of the previous O(n log n)-bit solution. |

ISSN | 1071-9040 |

References | References in Scopus |

DC Field | Value |
---|---|

dc.contributor.author | Chan, HL |

dc.contributor.author | Hon, WK |

dc.contributor.author | Lam, TW |

dc.contributor.author | Sadakane, K |

dc.date.accessioned | 2007-10-30T06:28:31Z |

dc.date.available | 2007-10-30T06:28:31Z |

dc.date.issued | 2005 |

dc.description.abstract | Recent breakthrough in compressed indexing data structures has reduced the space for indexing a text (or a collection of texts) of length n from O(n log n) bits to O(n) bits, while allowing very efficient pattern matching. Yet the compressed nature of such indices also makes them difficult to update dynamically. This paper presents the first O(n)-bit representation of a suffix tree for a dynamic collection of texts whose total length is n, which supports insertion and deletion of a text T in O(|T| log2 n) time, as well as all suffix tree traversal operations, including forward and backward suffix links. This work can be regarded as a generalization of the compressed representation of static texts. Our new suffix tree representation serves as a core part in a compact solution for the dynamic dictionary matching problem, i.e., providing an O(d)-bit data structure for a dynamic collection of patterns of total length d that can support the dictionary matching query efficiently. When compared with the O(d log d)-bit suffix tree based solution of Amir et al., the compact solution increases the query time by roughly a factor of log d only. In the study of the above results, we also derive the first O(n)-bit representation for maintaining n pairs of balanced parentheses in O(log n/log log n) time per operation, matching the time complexity of the previous O(n log n)-bit solution. |

dc.description.nature | published_or_final_version |

dc.format.extent | 951964 bytes |

dc.format.extent | 4181 bytes |

dc.format.mimetype | application/pdf |

dc.format.mimetype | text/plain |

dc.identifier.citation | Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2005, p. 13-22 [How to Cite?] |

dc.identifier.epage | 22 |

dc.identifier.hkuros | 102695 |

dc.identifier.issn | 1071-9040 |

dc.identifier.openurl | |

dc.identifier.scopus | eid_2-s2.0-20744440148 |

dc.identifier.spage | 13 |

dc.identifier.uri | http://hdl.handle.net/10722/45528 |

dc.language | eng |

dc.publisher | Society for Industrial and Applied Mathematics. |

dc.relation.ispartof | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |

dc.relation.references | References in Scopus |

dc.rights | Creative Commons: Attribution 3.0 Hong Kong License |

dc.subject | Mathematics computers |

dc.title | Dynamic dictionary matching and compressed suffix trees |

dc.type | Conference_Paper |

<?xml encoding="utf-8" version="1.0"?> <item><contributor.author>Chan, HL</contributor.author> <contributor.author>Hon, WK</contributor.author> <contributor.author>Lam, TW</contributor.author> <contributor.author>Sadakane, K</contributor.author> <date.accessioned>2007-10-30T06:28:31Z</date.accessioned> <date.available>2007-10-30T06:28:31Z</date.available> <date.issued>2005</date.issued> <identifier.citation>Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2005, p. 13-22</identifier.citation> <identifier.issn>1071-9040</identifier.issn> <identifier.uri>http://hdl.handle.net/10722/45528</identifier.uri> <description.abstract>Recent breakthrough in compressed indexing data structures has reduced the space for indexing a text (or a collection of texts) of length n from O(n log n) bits to O(n) bits, while allowing very efficient pattern matching. Yet the compressed nature of such indices also makes them difficult to update dynamically. This paper presents the first O(n)-bit representation of a suffix tree for a dynamic collection of texts whose total length is n, which supports insertion and deletion of a text T in O(|T| log2 n) time, as well as all suffix tree traversal operations, including forward and backward suffix links. This work can be regarded as a generalization of the compressed representation of static texts. Our new suffix tree representation serves as a core part in a compact solution for the dynamic dictionary matching problem, i.e., providing an O(d)-bit data structure for a dynamic collection of patterns of total length d that can support the dictionary matching query efficiently. When compared with the O(d log d)-bit suffix tree based solution of Amir et al., the compact solution increases the query time by roughly a factor of log d only. In the study of the above results, we also derive the first O(n)-bit representation for maintaining n pairs of balanced parentheses in O(log n/log log n) time per operation, matching the time complexity of the previous O(n log n)-bit solution.</description.abstract> <format.extent>951964 bytes</format.extent> <format.extent>4181 bytes</format.extent> <format.mimetype>application/pdf</format.mimetype> <format.mimetype>text/plain</format.mimetype> <language>eng</language> <publisher>Society for Industrial and Applied Mathematics.</publisher> <relation.ispartof>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</relation.ispartof> <rights>Creative Commons: Attribution 3.0 Hong Kong License</rights> <subject>Mathematics computers</subject> <title>Dynamic dictionary matching and compressed suffix trees</title> <type>Conference_Paper</type> <identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1071-9040&volume=&spage=13&epage=22&date=2005&atitle=Dynamic+dictionary+matching+and+compressed+suffix+trees</identifier.openurl> <description.nature>published_or_final_version</description.nature> <identifier.scopus>eid_2-s2.0-20744440148</identifier.scopus> <identifier.hkuros>102695</identifier.hkuros> <relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-20744440148&selection=ref&src=s&origin=recordpage</relation.references> <identifier.spage>13</identifier.spage> <identifier.epage>22</identifier.epage> <bitstream.url>http://hub.hku.hk/bitstream/10722/45528/1/102695.pdf</bitstream.url> </item>

Author Affiliations

- Kyushu University
- The University of Hong Kong