File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-642-03784-9_5
- Scopus: eid_2-s2.0-70350678834
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Succinct text indexing with wildcards
Title | Succinct text indexing with wildcards |
---|---|
Authors | |
Issue Date | 2009 |
Publisher | Springer 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? |
Abstract | A 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 Identifier | http://hdl.handle.net/10722/93255 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Tam, A | en_HK |
dc.contributor.author | Wu, E | en_HK |
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Yiu, SM | en_HK |
dc.date.accessioned | 2010-09-25T14:55:34Z | - |
dc.date.available | 2010-09-25T14:55:34Z | - |
dc.date.issued | 2009 | en_HK |
dc.identifier.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 | en_HK |
dc.identifier.issn | 0302-9743 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/93255 | - |
dc.description.abstract | A 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.language | eng | en_HK |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_HK |
dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | en_HK |
dc.title | Succinct text indexing with wildcards | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Wu, E:ewu1@hkucc.hku.hk | en_HK |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_HK |
dc.identifier.email | Yiu, SM:smyiu@cs.hku.hk | en_HK |
dc.identifier.authority | Wu, E=rp00193 | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.identifier.authority | Yiu, SM=rp00207 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/978-3-642-03784-9_5 | en_HK |
dc.identifier.scopus | eid_2-s2.0-70350678834 | en_HK |
dc.identifier.hkuros | 161350 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-70350678834&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 5721 LNCS | en_HK |
dc.identifier.spage | 39 | en_HK |
dc.identifier.epage | 50 | en_HK |
dc.publisher.place | Germany | en_HK |
dc.identifier.scopusauthorid | Tam, A=35318914400 | en_HK |
dc.identifier.scopusauthorid | Wu, E=7202128034 | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Yiu, SM=7003282240 | en_HK |
dc.identifier.issnl | 0302-9743 | - |