File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Compressed index for dynamic text

TitleCompressed index for dynamic text
Authors
Issue Date2004
Citation
Data Compression Conference Proceedings, 2004, p. 102-111 How to Cite?
AbstractThis paper investigates how to index a text which is subject to updates. The best solution in the literature is based on suffix tree using O(n log n) bits of storage, where n is the length of the text. It supports finding all occurrences of a pattern P in O(|P| + occ) time, where occ is the number of occurrences. Each text update consists of inserting or deleting a substring of length y and can be supported in O(y + √n) time. In this paper, we initiate the study of compressed index using only O(n log |Σ|) bits of space, where Σ denotes the alphabet. Our solution supports finding all occurrences of a pattern P in O(|P|log2 n(logε n + log |ΣE|) + occ log1+ε n) time, while insertion or deletion of a substring of length y can be done in O((y + √n) log 2+εn) amortized time, where 0 < ε ≤ 1. The core part of our data structure is based on the recent work on Compressed Suffix Trees (CST) and Compressed Suffix Arrays (CSA).
Persistent Identifierhttp://hdl.handle.net/10722/151868
ISSN
2023 SCImago Journal Rankings: 0.371
References

 

DC FieldValueLanguage
dc.contributor.authorHon, WKen_US
dc.contributor.authorLam, TWen_US
dc.contributor.authorSadakane, Ken_US
dc.contributor.authorSung, WKen_US
dc.contributor.authorYiu, SMen_US
dc.date.accessioned2012-06-26T06:30:14Z-
dc.date.available2012-06-26T06:30:14Z-
dc.date.issued2004en_US
dc.identifier.citationData Compression Conference Proceedings, 2004, p. 102-111en_US
dc.identifier.issn1068-0314en_US
dc.identifier.urihttp://hdl.handle.net/10722/151868-
dc.description.abstractThis paper investigates how to index a text which is subject to updates. The best solution in the literature is based on suffix tree using O(n log n) bits of storage, where n is the length of the text. It supports finding all occurrences of a pattern P in O(|P| + occ) time, where occ is the number of occurrences. Each text update consists of inserting or deleting a substring of length y and can be supported in O(y + √n) time. In this paper, we initiate the study of compressed index using only O(n log |Σ|) bits of space, where Σ denotes the alphabet. Our solution supports finding all occurrences of a pattern P in O(|P|log2 n(logε n + log |ΣE|) + occ log1+ε n) time, while insertion or deletion of a substring of length y can be done in O((y + √n) log 2+εn) amortized time, where 0 < ε ≤ 1. The core part of our data structure is based on the recent work on Compressed Suffix Trees (CST) and Compressed Suffix Arrays (CSA).en_US
dc.languageengen_US
dc.relation.ispartofData Compression Conference Proceedingsen_US
dc.titleCompressed index for dynamic texten_US
dc.typeConference_Paperen_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.identifier.authorityYiu, SM=rp00207en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-2642533893en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-2642533893&selection=ref&src=s&origin=recordpageen_US
dc.identifier.spage102en_US
dc.identifier.epage111en_US
dc.identifier.scopusauthoridHon, WK=7004282818en_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.scopusauthoridSadakane, K=7005716583en_US
dc.identifier.scopusauthoridSung, WK=13310059700en_US
dc.identifier.scopusauthoridYiu, SM=7003282240en_US
dc.identifier.issnl1068-0314-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats