File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Succinct index for dynamic dictionary matching
  • Basic View
  • Metadata View
  • XML View
TitleSuccinct index for dynamic dictionary matching
 
AuthorsHon, WK3
Lam, TW1
Shah, R4
Tam, SL1
Vitter, JS2
 
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/
 
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-1043 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-10631-6_104
 
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
 
ISSN0302-9743
2013 SCImago Journal Rankings: 0.310
 
DOIhttp://dx.doi.org/10.1007/978-3-642-10631-6_104
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorHon, WK
 
dc.contributor.authorLam, TW
 
dc.contributor.authorShah, R
 
dc.contributor.authorTam, SL
 
dc.contributor.authorVitter, JS
 
dc.date.accessioned2010-12-23T08:39:29Z
 
dc.date.available2010-12-23T08:39:29Z
 
dc.date.issued2009
 
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.
 
dc.description.naturelink_to_OA_fulltext
 
dc.descriptionLNCS v. 5878 is conference proceedings of ISAAC 2009
 
dc.descriptionSession 7 - C
 
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.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-1043 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-10631-6_104
 
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-10631-6_104
 
dc.identifier.epage1043
 
dc.identifier.hkuros177018
 
dc.identifier.issn0302-9743
2013 SCImago Journal Rankings: 0.310
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-75749102981
 
dc.identifier.spage1034
 
dc.identifier.urihttp://hdl.handle.net/10722/129583
 
dc.identifier.volume5878 LNCS
 
dc.languageeng
 
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
dc.publisher.placeGermany
 
dc.relation.ispartofLecture Notes in Computer Science
 
dc.relation.referencesReferences in Scopus
 
dc.rightsThe original publication is available at www.springerlink.com
 
dc.subjectAlphabet size
 
dc.subjectCompressed suffix array
 
dc.subjectDynamic dictionaries
 
dc.subjectFm-index
 
dc.subjectNew indices
 
dc.titleSuccinct index for dynamic dictionary matching
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Hon, WK</contributor.author>
<contributor.author>Lam, TW</contributor.author>
<contributor.author>Shah, R</contributor.author>
<contributor.author>Tam, SL</contributor.author>
<contributor.author>Vitter, JS</contributor.author>
<date.accessioned>2010-12-23T08:39:29Z</date.accessioned>
<date.available>2010-12-23T08:39:29Z</date.available>
<date.issued>2009</date.issued>
<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</identifier.citation>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/129583</identifier.uri>
<description>LNCS v. 5878 is conference proceedings of ISAAC 2009</description>
<description>Session 7 - C</description>
<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, &#8943;, 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 &#963;) bits where n is the total length of patterns and &#963; 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&#963;+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&#963;+logn) times, where occ is the number of occurrences. &#169; 2009 Springer-Verlag Berlin Heidelberg.</description.abstract>
<language>eng</language>
<publisher>Springer Verlag. The Journal&apos;s web site is located at http://springerlink.com/content/105633/</publisher>
<relation.ispartof>Lecture Notes in Computer Science</relation.ispartof>
<rights>The original publication is available at www.springerlink.com</rights>
<subject>Alphabet size</subject>
<subject>Compressed suffix array</subject>
<subject>Dynamic dictionaries</subject>
<subject>Fm-index</subject>
<subject>New indices</subject>
<title>Succinct index for dynamic dictionary matching</title>
<type>Conference_Paper</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=0302-9743&amp;volume=5878&amp;spage=1034&amp;epage=1043&amp;date=2009&amp;atitle=Succinct+index+for+dynamic+dictionary+matching</identifier.openurl>
<description.nature>link_to_OA_fulltext</description.nature>
<identifier.doi>10.1007/978-3-642-10631-6_104</identifier.doi>
<identifier.scopus>eid_2-s2.0-75749102981</identifier.scopus>
<identifier.hkuros>177018</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-75749102981&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>5878 LNCS</identifier.volume>
<identifier.spage>1034</identifier.spage>
<identifier.epage>1043</identifier.epage>
<publisher.place>Germany</publisher.place>
<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</description.other>
<bitstream.url>http://hub.hku.hk/bitstream/10722/129583/1/re01.htm</bitstream.url>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Texas A and M University
  3. National Tsing Hua University
  4. Louisiana State University