Practical Entropy-Compressed Rank/Select Dictionary

By Daisuke Okanohara, Kunihiko Sadakane. Workshop on Algorithm Engineering and Experimentation, 2006

329 citations recorded by the source corpus.

Rank/Select dictionaries are data structures for an ordered set S ⊂ {0,1, . . ., n − 1} to compute rank(x, S) (the number of elements in S that are no greater than x), and select(i, S) (the i-th smallest element in S), which are the fundamental components of succinct data structures of strings, trees, graphs, etc.. In these data structures, however, only asymptotic behavior has been considered and their performance for real data is not satisfactory. In this paper, we propose four novel Rank/Select dictionaries: esp, recrank, vcode and sdarray, each of which is small if the number of elements in S is small, and indeed close to nH0(S) (H0(S) ≤ 1 is the zero-th order empirical entropy of S) in practice. Furthermore, their query times are superior to those of existing structures. Experimental results reveal the characteristics of our data structures and also show that these data structures are superior to existing implementations, both in terms of size and query time.

Subfields: Artificial Intelligence, Computer Networks and Communications, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/c070cc937144c4490a27fe2467b1bbff5dc6b63f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Molecular Biology

Citations in the corpus

From Theory to Practice: Plug and Play with Succinct Data Structures (2013, methodology): “Choosing an Hkcompressed CSA for csa_full, a 2n+o(n)-bit solution for rminq and rmaxq, and a compressed BV for border [15], results in a total bit count bounded above”
Succinct nearest neighbor search (2011, methodology): “This can be explained because the sarray gives constant time access to the i-th element [15].”
Compressed full-text indexes (2007, background): “Most implementations of these solutions sacrifice some theoretical guarantees but work well in practice [Geary et al. 2004; Kim et al. 2005; González et al. 2005; Sadakane and Okanohara 2006].”