File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Dynamic dictionary matching and compressed suffix trees

TitleDynamic dictionary matching and compressed suffix trees
Authors
KeywordsMathematics computers
Issue Date2005
PublisherSociety for Industrial and Applied Mathematics.
Citation
Proceedings 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.
Persistent Identifierhttp://hdl.handle.net/10722/45528
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorHon, WKen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorSadakane, Ken_HK
dc.date.accessioned2007-10-30T06:28:31Z-
dc.date.available2007-10-30T06:28:31Z-
dc.date.issued2005en_HK
dc.identifier.citationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2005, p. 13-22en_HK
dc.identifier.issn1071-9040en_HK
dc.identifier.urihttp://hdl.handle.net/10722/45528-
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.en_HK
dc.format.extent951964 bytes-
dc.format.extent4181 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics.en_HK
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectMathematics computersen_HK
dc.titleDynamic dictionary matching and compressed suffix treesen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://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+treesen_HK
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.scopuseid_2-s2.0-20744440148en_HK
dc.identifier.hkuros102695-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-20744440148&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage13en_HK
dc.identifier.epage22en_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridHon, WK=7004282818en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridSadakane, K=7005716583en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats