File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Compressed indexes for approximate string matching

TitleCompressed indexes for approximate string matching
Authors
KeywordsApproximate String Matching
Compressed Index
Issue Date2006
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Proceedings of the 14th Annual European Symposium on Algorithms (ESA), Zurich, Switzerland, 11-13 September, 2006. In Lecture Notes In Computer Science, 2006, v. 4168 LNCS, p. 208-219 How to Cite?
AbstractWe revisit the problem of indexing a string 5[1.n] to support searching all substrings in S that match a given pattern P[1.m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m k) time for searching. Motivated by the indexing of DNA sequences, we investigate space efficient indexes that occupy only O(n) space. For k = 1, we give an index to support matching in O(m+occ+lognloglogn) time. The previously best solution achieving this time complexity requires an index of size O(n log n). This new index can be used to improve existing indexes for k ≥ 2 errors. Among others, it can support matching with k = 2 errors in O(m log n log log n + occ) time. © Springer-Verlag Berlin Heidelberg 2006.
Persistent Identifierhttp://hdl.handle.net/10722/92634
ISBN
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References
Grants

 

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-17T10:52:33Z-
dc.date.available2010-09-17T10:52:33Z-
dc.date.issued2006en_HK
dc.identifier.citationProceedings of the 14th Annual European Symposium on Algorithms (ESA), Zurich, Switzerland, 11-13 September, 2006. In Lecture Notes In Computer Science, 2006, v. 4168 LNCS, p. 208-219en_HK
dc.identifier.isbn3540388753-
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/92634-
dc.description.abstractWe revisit the problem of indexing a string 5[1.n] to support searching all substrings in S that match a given pattern P[1.m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m k) time for searching. Motivated by the indexing of DNA sequences, we investigate space efficient indexes that occupy only O(n) space. For k = 1, we give an index to support matching in O(m+occ+lognloglogn) time. The previously best solution achieving this time complexity requires an index of size O(n log n). This new index can be used to improve existing indexes for k ≥ 2 errors. Among others, it can support matching with k = 2 errors in O(m log n log log n + occ) time. © 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.relation.ispartofAnnual European Symposium on Algorithms (ESA)-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectApproximate String Matchingen_HK
dc.subjectCompressed Indexen_HK
dc.titleCompressed indexes for approximate string 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.naturepostprint-
dc.identifier.doi10.1007/11841036_21-
dc.identifier.scopuseid_2-s2.0-33750719108en_HK
dc.identifier.hkuros163536-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33750719108&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4168 LNCSen_HK
dc.identifier.issue2en_HK
dc.identifier.spage208en_HK
dc.identifier.epage219en_HK
dc.identifier.eissn1432-0541-
dc.publisher.placeGermanyen_HK
dc.description.otherProceedings of the 14th Annual European Symposium on Algorithms (ESA), Zurich, Switzerland, 11-13 September, 2006. In Lecture Notes In Computer Science, 2006, v. 4168 LNCS, p. 208-219-
dc.relation.projectCompressed indexes for approximate string matching, with applications to biological sequences-
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.customcontrol.immutablecsl 141017-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats