File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Succinct text indexing with wildcards

TitleSuccinct text indexing with wildcards
Authors
Issue Date2009
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2009, v. 5721 LNCS, p. 39-50 How to Cite?
AbstractA succinct text index uses space proportional to the text itself, say, two times n logσ for a text of n characters over an alphabet of size σ. In the past few years, there were several exciting results leading to succinct indexes that support efficient pattern matching. In this paper we present the first succinct index for a text that contains wildcards. The space complexity of our index is (3 + o(1))n logσ + O(ℓlogn) bits, where ℓ is the number of wildcard groups in the text. Such an index finds applications in indexing genomic sequences that contain single-nucleotide polymorphisms (SNP), which could be modeled as wildcards. In the course of deriving the above result, we also obtain an alternate succinct index of a set of d patterns for the purpose of dictionary matching. When compared with the succinct index in the literature, the new index doubles the size (precisely, from n logσ to 2 n logσ, where n is the total length of all patterns), yet it reduces the matching time to O(mlogσ + mlogd + occ), where m is the length of the query text. It is worth-mentioning that the time complexity no longer depends on the total dictionary size. © 2009 Springer.
Persistent Identifierhttp://hdl.handle.net/10722/93255
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorTam, Aen_HK
dc.contributor.authorWu, Een_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorYiu, SMen_HK
dc.date.accessioned2010-09-25T14:55:34Z-
dc.date.available2010-09-25T14:55:34Z-
dc.date.issued2009en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2009, v. 5721 LNCS, p. 39-50en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93255-
dc.description.abstractA succinct text index uses space proportional to the text itself, say, two times n logσ for a text of n characters over an alphabet of size σ. In the past few years, there were several exciting results leading to succinct indexes that support efficient pattern matching. In this paper we present the first succinct index for a text that contains wildcards. The space complexity of our index is (3 + o(1))n logσ + O(ℓlogn) bits, where ℓ is the number of wildcard groups in the text. Such an index finds applications in indexing genomic sequences that contain single-nucleotide polymorphisms (SNP), which could be modeled as wildcards. In the course of deriving the above result, we also obtain an alternate succinct index of a set of d patterns for the purpose of dictionary matching. When compared with the succinct index in the literature, the new index doubles the size (precisely, from n logσ to 2 n logσ, where n is the total length of all patterns), yet it reduces the matching time to O(mlogσ + mlogd + occ), where m is the length of the query text. It is worth-mentioning that the time complexity no longer depends on the total dictionary size. © 2009 Springer.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleSuccinct text indexing with wildcardsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailWu, E:ewu1@hkucc.hku.hken_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_HK
dc.identifier.authorityWu, E=rp00193en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityYiu, SM=rp00207en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-03784-9_5en_HK
dc.identifier.scopuseid_2-s2.0-70350678834en_HK
dc.identifier.hkuros161350en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-70350678834&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume5721 LNCSen_HK
dc.identifier.spage39en_HK
dc.identifier.epage50en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridTam, A=35318914400en_HK
dc.identifier.scopusauthoridWu, E=7202128034en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridYiu, SM=7003282240en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats