File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Dynamic dictionary matching and compressed suffix trees
  • Basic View
  • Metadata View
  • XML View
TitleDynamic dictionary matching and compressed suffix trees
 
AuthorsChan, HL2
Hon, WK2
Lam, TW2
Sadakane, K1
 
KeywordsMathematics computers
 
Issue Date2005
 
PublisherSociety for Industrial and Applied Mathematics.
 
CitationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2005, p. 13-22 [How to Cite?]
 
AbstractRecent 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.
 
ISSN1071-9040
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorChan, HL
 
dc.contributor.authorHon, WK
 
dc.contributor.authorLam, TW
 
dc.contributor.authorSadakane, K
 
dc.date.accessioned2007-10-30T06:28:31Z
 
dc.date.available2007-10-30T06:28:31Z
 
dc.date.issued2005
 
dc.description.abstractRecent 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.naturepublished_or_final_version
 
dc.format.extent951964 bytes
 
dc.format.extent4181 bytes
 
dc.format.mimetypeapplication/pdf
 
dc.format.mimetypetext/plain
 
dc.identifier.citationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2005, p. 13-22 [How to Cite?]
 
dc.identifier.epage22
 
dc.identifier.hkuros102695
 
dc.identifier.issn1071-9040
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-20744440148
 
dc.identifier.spage13
 
dc.identifier.urihttp://hdl.handle.net/10722/45528
 
dc.languageeng
 
dc.publisherSociety for Industrial and Applied Mathematics.
 
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
 
dc.relation.referencesReferences in Scopus
 
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License
 
dc.subjectMathematics computers
 
dc.titleDynamic dictionary matching and compressed suffix trees
 
dc.typeConference_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&amp;issn=1071-9040&amp;volume=&amp;spage=13&amp;epage=22&amp;date=2005&amp;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&amp;selection=ref&amp;src=s&amp;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
  1. Kyushu University
  2. The University of Hong Kong