Succinct indexable dictionaries with applications to encoding k-ary trees and multisets
By R. Raman, Venkatesh Raman, S. Rao. ACM-SIAM Symposium on Discrete Algorithms, 2002
461 citations recorded by the source corpus.
View Paper: https://www.semanticscholar.org/paper/9de0d710d69e5ae38bb1b2b996c3ddd490298e21
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Gonzalo Navarro
- Paolo Ferragina
- Eric Sadit Tellez
- Edgar Chávez
- Veli Mäkinen
- Daisuke Okanohara
- Kunihiko Sadakane
- Giovanni Manzini
Citations in the corpus
- Practical Entropy-Compressed Rank/Select Dictionary (2006, methodology): “Many data structures have been proposed for Rank/Select dictionaries, most of which support the queries in constant time on word RAM [7, 13, 16, 19, 21] using n + o( n ) bits or nH 0 ( S ) + o( n ) bits ( H 0 ( S ) ≤ 1 is the zero-th order empirical entropy of S ).”
- From Theory to Practice: Plug and Play with Succinct Data Structures (2013, methodology): “The total size is then |CSA(T )|+ |WT(D)| = nHk(T )+ nH0(D), using compressed BVs for wtd [17].”
- Succinct nearest neighbor search (2011, methodology): “Nevertheless there is room for improvement by compressing the index using indexed bitmaps, with a very small speed penalty for set union and intersection computations [15, 11, 20].”
- Indexing compressed text (2005, methodology): “These “second generation” compressed indexes make use of new algorithmic tools such as succinct dictionaries [Raman et al. 2002], wavelet trees [Grossi et al.”
- High-order entropy-compressed text indexes (2003, methodology): “Letting t be the number of elements stored (the number of ls in the bitvector), we can replace the bitvector supporting rank and select with the constant-time indexable dictionaries developed by Raman, Raman, and Rao [17], requiring rig (?)]”
- Compressed full-text indexes (2007, methodology): “More Sophisticated nH0-Bit Solutions We explain now how to improve the representation of the previous section for compressible sequences, so as to obtain complete representations requiring nH0(B) +o(n) bits of space [Raman et al. 2002]. log n We cut B into blocks of .xed length t = 2 .”