File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Space efficient indexes for string matching with don't cares

TitleSpace efficient indexes for string matching with don't cares
Authors
Issue Date2007
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), 2007, v. 4835 LNCS, p. 846-857 How to Cite?
Abstract
Given a text T of length n, the classical indexing problem for pattern matching is to build an index for T so that for any query pattern P, we can report efficiently all occurrences of P in T. Cole et al (2004) extended this problem to allow don't care characters (wildcards) in the text and pattern, and they gave the first index that supports efficient pattern matching. The space complexity of this index is linear in n (text length) but exponential in terms of the number of wildcards. Motivated by bioinformatics applications, we investigate indexes whose size depends on n only. In the literature, space efficient indexes for wildcard matching are known only for the special case when wildcards appear only in the pattern (Iliopoulos and Rahman, 2007); the space required is O(n). Not much has been heard for the case when wildcards appear in the text only, or in both the text and pattern. In this paper we give an O(n) space index to support efficient wildcard matching in all three cases. Our solution to the pattern-only case improves the matching time of the previous work tremendously in practice. In addition, our solution can be extended to handle optional wildcards, each of which can match zero or one character. © Springer-Verlag Berlin Heidelberg 2007.
Persistent Identifierhttp://hdl.handle.net/10722/93219
ISSN
2013 SCImago Journal Rankings: 0.310
References

 

Author Affiliations
  1. The University of Hong Kong
  2. National University of Singapore
DC FieldValueLanguage
dc.contributor.authorLam, TWen_HK
dc.contributor.authorSung, WKen_HK
dc.contributor.authorTam, SLen_HK
dc.contributor.authorYiu, SMen_HK
dc.date.accessioned2010-09-25T14:54:30Z-
dc.date.available2010-09-25T14:54:30Z-
dc.date.issued2007en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4835 LNCS, p. 846-857en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93219-
dc.description.abstractGiven a text T of length n, the classical indexing problem for pattern matching is to build an index for T so that for any query pattern P, we can report efficiently all occurrences of P in T. Cole et al (2004) extended this problem to allow don't care characters (wildcards) in the text and pattern, and they gave the first index that supports efficient pattern matching. The space complexity of this index is linear in n (text length) but exponential in terms of the number of wildcards. Motivated by bioinformatics applications, we investigate indexes whose size depends on n only. In the literature, space efficient indexes for wildcard matching are known only for the special case when wildcards appear only in the pattern (Iliopoulos and Rahman, 2007); the space required is O(n). Not much has been heard for the case when wildcards appear in the text only, or in both the text and pattern. In this paper we give an O(n) space index to support efficient wildcard matching in all three cases. Our solution to the pattern-only case improves the matching time of the previous work tremendously in practice. In addition, our solution can be extended to handle optional wildcards, each of which can match zero or one character. © Springer-Verlag Berlin Heidelberg 2007.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.titleSpace efficient indexes for string matching with don't caresen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityYiu, SM=rp00207en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-38149062674en_HK
dc.identifier.hkuros146739en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-38149062674&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4835 LNCSen_HK
dc.identifier.spage846en_HK
dc.identifier.epage857en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridSung, WK=13310059700en_HK
dc.identifier.scopusauthoridTam, SL=14042926200en_HK
dc.identifier.scopusauthoridYiu, SM=7003282240en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats