Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2011.05.023
Title: Succinct data structures for searchable partial sums with optimal worst-case performance
Authors: Hon, W.-K.
Sadakane, K.
Sung, W.-K. 
Issue Date: 2011
Source: Hon, W.-K., Sadakane, K., Sung, W.-K. (2011). Succinct data structures for searchable partial sums with optimal worst-case performance. Theoretical Computer Science 412 (39) : 5176-5186. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2011.05.023
Abstract: The notion of succinct indexes can be dated back from the debut of Jacobson's thesis (1988) [14], and has triggered many results in the last decade. In traditional indexing, some given data are preprocessed so as to support online queries (and updates) on the data as efficiently as possible. When succinctness is involved, we are restricted to index the data using only an informationtheoretically minimum number of bits. This paper concerns the succinct indexing schemes for a well-studied problem called Searchable Partial Sums (SPS). In SPS, an array A of n non-negative k-bit integers is preprocessed so as to support online sum and search queries, and possibly update operation of individual entry. A succinct indexing scheme would allow only kn+o(kn) bits to represent the array A. The only known result is that when k=1 (in this case, it is known as the Dynamic Bit Array Problem), we can support both queries in O(log bn) time and update in O(b) amortized time for any b with lgnlglgn≤b≤n. This paper shows that even for k=O(lglgn), we can index A succinctly such that both query and update operations can be supported using the same time complexities. Moreover, the time for update becomes the worst-case time. Furthermore, the tradeoff between the query times and the update time is optimal as implied by Patracu and Demaine's lower bound result (2006) [24]. In general when k=O(lgU), we show a lower bound of Ω(lgnlglgn) time for the search query irrespective of the update time. This gives a tighter lower bound as compared to that of Patracu and Demaine's, which is a consequence of the requirement of succinctness. On the other hand, we give a succinct index that can support sum in O(log bn) time, search in O(τlog bn) time, and update in O(b) time, where τ=minlglgnlglgUlglglgU,lgnlglgn. The query times are optimal when b= n. This paper also extends the Searchable Partial Sums with insert and delete operations, and provides a succinct data structure for some cases. © 2011 Elsevier B.V. All rights reserved.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/39117
ISSN: 03043975
DOI: 10.1016/j.tcs.2011.05.023
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

7
checked on Jan 17, 2018

WEB OF SCIENCETM
Citations

7
checked on Dec 13, 2017

Page view(s)

99
checked on Jan 14, 2018

Google ScholarTM

Check

Altmetric


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