Opportunistic data structures for range queries |
| |
Authors: | Chung Keung Poon Wai Keung Yiu |
| |
Affiliation: | (1) Department of Computer Science, City University of Hong Kong, Hong Kong |
| |
Abstract: | In this paper, we study the problem of supporting range sum queries on a compressed sequence of values. For a sequence of n k-bit integers, k ≤ O(log n), our data structures require asymptotically the same amount of storage as the compressed sequence if compressed using the Lempel-Ziv algorithm. The basic structure supports range sum queries in O(log n) time. With an increase by a constant factor in the storage complexity, the query time can be improved to O(log log n + k). The work described in this paper is fully supported by a grant from the Research Grant Council of the Hong Kong Special Administrative Region, China (CityU 1071/02E). A preliminary version has appeared in 11th International Conference in Computing and Combinatorics (COCOON'05). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|