Conference Paper: Dynamic dictionary matching and compressed suffix trees

File Download

102695.pdf

Links for fulltext
(May Require Subscription)

Scopus: eid_2-s2.0-20744440148
Find via

Supplementary

Citations:
- Scopus:
- Web of Science:
- PubMed Central:
Item Statistics (The Hub)
Appears in Collections:
- Computer Science: Conference papers

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&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

Kyushu University
The University of Hong Kong