File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: A linear size index for approximate pattern matching

TitleA linear size index for approximate pattern matching
Authors
Issue Date2006
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), 2006, v. 4009 LNCS, p. 49-59 How to Cite?
AbstractThis paper revisits the problem of indexing a text S[1.,n] to support searching substrings in S that match a given pattern P[1..m] with at most k errors. A naive solution either has a worst-case matching time complexity of Ω(m k) or requires Ω(n k) space. Devising a solution with better performance has been a challenge until Cole et al. [5] showed an O(nlog k n)-space index that can support k-error matching in O(m+occ+log k n log log n) time, where occ is the number of occurrences. Motivated by the indexing of DNA, we investigate in this paper the feasibility of devising a linear-size index that still has a time complexity linear in m. In particular, we give an O(n)-apace index that supports k-error matching in O(m + occ+ (log n) k(k+1) log log n) worst-case time. Furthermore, the index can be compressed from O(n) words into O(n) bits with a slight increase in the time complexity. © Springer-Verlag Berlin Heidelberg 2006.
Persistent Identifierhttp://hdl.handle.net/10722/93354
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorSung, WKen_HK
dc.contributor.authorTam, SLen_HK
dc.contributor.authorWong, SSen_HK
dc.date.accessioned2010-09-25T14:58:33Z-
dc.date.available2010-09-25T14:58:33Z-
dc.date.issued2006en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2006, v. 4009 LNCS, p. 49-59en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93354-
dc.description.abstractThis paper revisits the problem of indexing a text S[1.,n] to support searching substrings in S that match a given pattern P[1..m] with at most k errors. A naive solution either has a worst-case matching time complexity of Ω(m k) or requires Ω(n k) space. Devising a solution with better performance has been a challenge until Cole et al. [5] showed an O(nlog k n)-space index that can support k-error matching in O(m+occ+log k n log log n) time, where occ is the number of occurrences. Motivated by the indexing of DNA, we investigate in this paper the feasibility of devising a linear-size index that still has a time complexity linear in m. In particular, we give an O(n)-apace index that supports k-error matching in O(m + occ+ (log n) k(k+1) log log n) worst-case time. Furthermore, the index can be compressed from O(n) words into O(n) bits with a slight increase in the time complexity. © Springer-Verlag Berlin Heidelberg 2006.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.titleA linear size index for approximate pattern matchingen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-33746032583en_HK
dc.identifier.hkuros118591en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33746032583&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4009 LNCSen_HK
dc.identifier.spage49en_HK
dc.identifier.epage59en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridSung, WK=13310059700en_HK
dc.identifier.scopusauthoridTam, SL=14042926200en_HK
dc.identifier.scopusauthoridWong, SS=8439889300en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats