Compressed Persistent Index for Efficient Rank/Select Queries

摘要

We design compressed persistent indices that store a bit vector of size n and support a sequence of k bit-flip update operations, such that rank and select queries at any version can be supported efficiently. In particular, we present partially and fully persistent compressed indices for offline and online updates that support all operations in time polylog-arithmic in n and k. This improves upon the space or time complexities of straightforward approaches, when k = O(n/(log n)), which is common in biological applications. We also prove that any partially persistent index that occupies O((n + k) log(nk)) bits requires ω(1) time to support the rank query at a given version.