File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Succinct index for dynamic dictionary matching

TitleSuccinct index for dynamic dictionary matching
Authors
KeywordsAlphabet size
Compressed suffix array
Dynamic dictionaries
Fm-index
New indices
Issue Date2009
PublisherSpringer 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?
AbstractIn 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.
DescriptionLNCS v. 5878 is conference proceedings of ISAAC 2009
Session 7 - C
Persistent Identifierhttp://hdl.handle.net/10722/129583
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorHon, WKen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorShah, Ren_HK
dc.contributor.authorTam, SLen_HK
dc.contributor.authorVitter, JSen_HK
dc.date.accessioned2010-12-23T08:39:29Z-
dc.date.available2010-12-23T08:39:29Z-
dc.date.issued2009en_HK
dc.identifier.citationThe 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-1043en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/129583-
dc.descriptionLNCS v. 5878 is conference proceedings of ISAAC 2009-
dc.descriptionSession 7 - C-
dc.description.abstractIn 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.en_HK
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.rightsThe original publication is available at www.springerlink.comen_US
dc.subjectAlphabet size-
dc.subjectCompressed suffix array-
dc.subjectDynamic dictionaries-
dc.subjectFm-index-
dc.subjectNew indices-
dc.titleSuccinct index for dynamic dictionary matchingen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0302-9743&volume=5878&spage=1034&epage=1043&date=2009&atitle=Succinct+index+for+dynamic+dictionary+matchingen_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_OA_fulltext-
dc.identifier.doi10.1007/978-3-642-10631-6_104en_HK
dc.identifier.scopuseid_2-s2.0-75749102981en_HK
dc.identifier.hkuros177018en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-75749102981&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume5878 LNCSen_HK
dc.identifier.spage1034en_HK
dc.identifier.epage1043en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 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.scopusauthoridHon, WK=7004282818en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridShah, R=35365088300en_HK
dc.identifier.scopusauthoridTam, SL=14042926200en_HK
dc.identifier.scopusauthoridVitter, JS=7005508549en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats