File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Compressed index for dynamic text
  • Basic View
  • Metadata View
  • XML View
TitleCompressed index for dynamic text
 
AuthorsHon, WK2
Lam, TW2
Sadakane, K1
Sung, WK3
Yiu, SM2
 
Issue Date2004
 
CitationData 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).
 
ISSN1068-0314
2013 SCImago Journal Rankings: 0.336
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorHon, WK
 
dc.contributor.authorLam, TW
 
dc.contributor.authorSadakane, K
 
dc.contributor.authorSung, WK
 
dc.contributor.authorYiu, SM
 
dc.date.accessioned2012-06-26T06:30:14Z
 
dc.date.available2012-06-26T06:30:14Z
 
dc.date.issued2004
 
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).
 
dc.description.naturelink_to_subscribed_fulltext
 
dc.identifier.citationData Compression Conference Proceedings, 2004, p. 102-111 [How to Cite?]
 
dc.identifier.epage111
 
dc.identifier.issn1068-0314
2013 SCImago Journal Rankings: 0.336
 
dc.identifier.scopuseid_2-s2.0-2642533893
 
dc.identifier.spage102
 
dc.identifier.urihttp://hdl.handle.net/10722/151868
 
dc.languageeng
 
dc.relation.ispartofData Compression Conference Proceedings
 
dc.relation.referencesReferences in Scopus
 
dc.titleCompressed index for dynamic text
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Hon, WK</contributor.author>
<contributor.author>Lam, TW</contributor.author>
<contributor.author>Sadakane, K</contributor.author>
<contributor.author>Sung, WK</contributor.author>
<contributor.author>Yiu, SM</contributor.author>
<date.accessioned>2012-06-26T06:30:14Z</date.accessioned>
<date.available>2012-06-26T06:30:14Z</date.available>
<date.issued>2004</date.issued>
<identifier.citation>Data Compression Conference Proceedings, 2004, p. 102-111</identifier.citation>
<identifier.issn>1068-0314</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/151868</identifier.uri>
<description.abstract>This 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 + &#8730;n) time. In this paper, we initiate the study of compressed index using only O(n log |&#931;|) bits of space, where &#931; denotes the alphabet. Our solution supports finding all occurrences of a pattern P in O(|P|log2 n(log&#949; n + log |&#931;E|) + occ log1+&#949; n) time, while insertion or deletion of a substring of length y can be done in O((y + &#8730;n) log 2+&#949;n) amortized time, where 0 &lt; &#949; &#8804; 1. The core part of our data structure is based on the recent work on Compressed Suffix Trees (CST) and Compressed Suffix Arrays (CSA).</description.abstract>
<language>eng</language>
<relation.ispartof>Data Compression Conference Proceedings</relation.ispartof>
<title>Compressed index for dynamic text</title>
<type>Conference_Paper</type>
<description.nature>link_to_subscribed_fulltext</description.nature>
<identifier.scopus>eid_2-s2.0-2642533893</identifier.scopus>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-2642533893&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.spage>102</identifier.spage>
<identifier.epage>111</identifier.epage>
</item>
Author Affiliations
  1. Kyushu University
  2. The University of Hong Kong
  3. National University of Singapore