File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Compressed index for a dynamic collection of texts

TitleCompressed index for a dynamic collection of texts
Authors
Chan, HLHon, WKLam, TW
Issue Date2004
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), 2004, v. 3109, p. 445-456 How to Cite?
AbstractLet T be a string with n characters over an alphabet of bounded size. The recent breakthrough on compressed indexing allows us to build an index for T in optimal space (i.e., O(n) bits), while supporting very efficient pattern matching [2, 4]. This paper extends the work on optimal-space indexing to a dynamic collection of texts. Precisely, we give a compressed index using O(n) bits where n is the total length of texts, such that searching for a pattern P takes O(|P| log n + occ log2 n) time where occ is the number of occurrences, and inserting or deleting a text T takes O(|T| log n) time. © Springer-Verlag 2004.
Persistent Identifierhttp://hdl.handle.net/10722/93422
ISSN
0302-9743
2020 SCImago Journal Rankings: 0.249
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorHon, WKen_HK
dc.contributor.authorLam, TWen_HK
dc.date.accessioned2010-09-25T15:00:41Z-
dc.date.available2010-09-25T15:00:41Z-
dc.date.issued2004en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3109, p. 445-456en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93422-
dc.description.abstractLet T be a string with n characters over an alphabet of bounded size. The recent breakthrough on compressed indexing allows us to build an index for T in optimal space (i.e., O(n) bits), while supporting very efficient pattern matching [2, 4]. This paper extends the work on optimal-space indexing to a dynamic collection of texts. Precisely, we give a compressed index using O(n) bits where n is the total length of texts, such that searching for a pattern P takes O(|P| log n + occ log2 n) time where occ is the number of occurrences, and inserting or deleting a text T takes O(|T| log n) time. © Springer-Verlag 2004.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.titleCompressed index for a dynamic collection of textsen_HK
dc.typeArticleen_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-35048868341en_HK
dc.identifier.hkuros107889en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-35048868341&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3109en_HK
dc.identifier.spage445en_HK
dc.identifier.epage456en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridHon, WK=7004282818en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats