Conference Paper: Succinct index for dynamic dictionary matching
File Download
Links for fulltext
(May Require Subscription)
(May Require Subscription)
- Publisher Website: 10.1007/978-3-642-10631-6_104
- Scopus: eid_2-s2.0-75749102981
- Find via
Supplementary
-
Citations:
-
Appears in Collections:
| Title | Succinct index for dynamic dictionary matching |
|---|---|
| Authors | Hon, WK3 Lam, TW1 Shah, R4 Tam, SL1 Vitter, JS2 |
| Keywords | Alphabet size Compressed suffix array Dynamic dictionaries Fm-index New indices |
| Issue Date | 2009 |
| Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| Citation | The 20th International Symposium on Algorithms and Computation (ISAAC 2009), Hawaii, 16-18 December 2009. In Lecture Notes in Computer Science, 2009, v. 5878, p. 1034-1043 [How to Cite?] DOI: http://dx.doi.org/10.1007/978-3-642-10631-6_104 |
| Abstract | In this paper we revisit the dynamic dictionary matching problem, which asks for an index for a set of patterns P 1, P 2, ⋯, P k that can support the following query and update operations efficiently. Given a query text T, we want to find all the occurrences of of these patterns; furthermore, as the set of patterns may change over time, we also want to insert or delete a pattern. The major contribution of this paper is the first succinct index for dynamic dictionary matching. Prior to our work, the most compact index is given by Chan et al. (2007), which is based on the compressed suffix arrays (Grossi and Vitter (2005) and Sadakane (2003)) and the FM-index (Ferragina and Manzini (2005)), and it requires O(n σ) bits where n is the total length of patterns and σ is the alphabet size. We develop a dynamic succinct index using a different (and simpler) paradigm based on suffix sampling. The new index not only improves the space complexity to (1+o(1))n logσ+O(klogn) bits, but also the time complexity of the query and update operations. Specifically, the query and update operations respectively take O(|T|logn+occ) and O(|P|logσ+logn) times, where occ is the number of occurrences. © 2009 Springer-Verlag Berlin Heidelberg. |
| Description | LNCS v. 5878 is conference proceedings of ISAAC 2009 Session 7 - C |
| ISSN | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| DOI | http://dx.doi.org/10.1007/978-3-642-10631-6_104 |
| References | References in Scopus |
| dc.contributor.author | Hon, WK |
|---|---|
| dc.contributor.author | Lam, TW |
| dc.contributor.author | Shah, R |
| dc.contributor.author | Tam, SL |
| dc.contributor.author | Vitter, JS |
| dc.date.accessioned | 2010-12-23T08:39:29Z |
| dc.date.available | 2010-12-23T08:39:29Z |
| dc.date.issued | 2009 |
| dc.description.abstract | In this paper we revisit the dynamic dictionary matching problem, which asks for an index for a set of patterns P 1, P 2, ⋯, P k that can support the following query and update operations efficiently. Given a query text T, we want to find all the occurrences of of these patterns; furthermore, as the set of patterns may change over time, we also want to insert or delete a pattern. The major contribution of this paper is the first succinct index for dynamic dictionary matching. Prior to our work, the most compact index is given by Chan et al. (2007), which is based on the compressed suffix arrays (Grossi and Vitter (2005) and Sadakane (2003)) and the FM-index (Ferragina and Manzini (2005)), and it requires O(n σ) bits where n is the total length of patterns and σ is the alphabet size. We develop a dynamic succinct index using a different (and simpler) paradigm based on suffix sampling. The new index not only improves the space complexity to (1+o(1))n logσ+O(klogn) bits, but also the time complexity of the query and update operations. Specifically, the query and update operations respectively take O(|T|logn+occ) and O(|P|logσ+logn) times, where occ is the number of occurrences. © 2009 Springer-Verlag Berlin Heidelberg. |
| dc.description.nature | link_to_OA_fulltext |
| dc.description | LNCS v. 5878 is conference proceedings of ISAAC 2009 |
| dc.description | Session 7 - C |
| dc.description.other | The 20th International Symposium on Algorithms and Computation (ISAAC 2009), Hawaii, 16-18 December 2009. In Lecture Notes in Computer Science, 2009, v. 5878, p. 1034-1043 |
| dc.identifier.citation | The 20th International Symposium on Algorithms and Computation (ISAAC 2009), Hawaii, 16-18 December 2009. In Lecture Notes in Computer Science, 2009, v. 5878, p. 1034-1043 [How to Cite?] DOI: http://dx.doi.org/10.1007/978-3-642-10631-6_104 |
| dc.identifier.doi | http://dx.doi.org/10.1007/978-3-642-10631-6_104 |
| dc.identifier.epage | 1043 |
| dc.identifier.hkuros | 177018 |
| dc.identifier.issn | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| dc.identifier.openurl | |
| dc.identifier.scopus | eid_2-s2.0-75749102981 |
| dc.identifier.spage | 1034 |
| dc.identifier.uri | http://hdl.handle.net/10722/129583 |
| dc.identifier.volume | 5878 LNCS |
| dc.language | eng |
| dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| dc.publisher.place | Germany |
| dc.relation.ispartof | Lecture Notes in Computer Science |
| dc.relation.references | References in Scopus |
| dc.rights | The original publication is available at www.springerlink.com |
| dc.subject | Alphabet size |
| dc.subject | Compressed suffix array |
| dc.subject | Dynamic dictionaries |
| dc.subject | Fm-index |
| dc.subject | New indices |
| dc.title | Succinct index for dynamic dictionary matching |
| dc.type | Conference_Paper |
Author Affiliations
- The University of Hong Kong
- Texas A and M University
- National Tsing Hua University
- Louisiana State University