Please use this identifier to cite or link to this item:
|Title:||Succinct data structures for searchable partial sums with optimal worst-case performance|
|Citation:||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) , 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) . 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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jul 10, 2018
WEB OF SCIENCETM
checked on Jun 27, 2018
checked on Jul 7, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.