Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39852
Title: Succinct data structures for Searchable Partial Sums
Authors: Hon, W.-K.
Sadakane, K.
Sung, W.-K. 
Issue Date: 2003
Source: Hon, W.-K.,Sadakane, K.,Sung, W.-K. (2003). Succinct data structures for Searchable Partial Sums. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2906 : 505-516. ScholarBank@NUS Repository.
Abstract: The Searchable Partial Sums is a data structure problem that maintains a sequence of n non-negative k-bit integers; in addition, it allows us to modify the entries by the update operation, while supporting two types of queries: sum and search. Recently, researchers focus on the succinct representation of the data structure in kn + o(kn) bits. They study the tradeoff in time between the query and the update operations, under the word RAM with word size O(lg U) bits. For the special case where k = 1 (which is known as Dynamic Bit Vector problem), Raman et al. showed that both queries can be supported in O(logb n) time, while update requires O(b) amortized time for any b with lg n/lg lg n ≤ b ≤ n. This paper generalizes the study and shows that even for k = O(lg lg n), both query and update operations can be maintained using the same time complexities. Also, the time for update becomes worst-case time. For the general case when k = O(lg U), we show a lower bound of Ω (√lg n/lg lg n) time for the search query. On the other hand, we propose a data structure that supports sum in O(logb n) time, search in O(τ logb cn) time, and update in O(b) time, where τ denotes the value of min {lg lg n lg lg U/lg lg lg U, √lg n/lg lg n}. When b = n∈, our data structure achieves optimal time bounds. This paper also extends the Searchable Partial Sums with insert and delete operations, and provides succinct data structure for some cases. © Springer-Verlag Berlin Heidelberg 2003.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/39852
ISSN: 03029743
Appears in Collections:Staff Publications

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

Page view(s)

62
checked on Dec 15, 2017

Google ScholarTM

Check


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