Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/41725
Title: Compressed index for dynamic text
Authors: Hon, W.-K.
Lam, T.-W.
Sadakane, K.
Sung, W.-K. 
Yiu, S.-M.
Issue Date: 2004
Source: Hon, W.-K.,Lam, T.-W.,Sadakane, K.,Sung, W.-K.,Yiu, S.-M. (2004). Compressed index for dynamic text. Data Compression Conference Proceedings : 102-111. ScholarBank@NUS Repository.
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 + √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).
Source Title: Data Compression Conference Proceedings
URI: http://scholarbank.nus.edu.sg/handle/10635/41725
ISSN: 10680314
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

56
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.