More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries

Abstract : We consider the problem of representing, in a compressed format, a bit-vector $S$ of $m$ bits with $n$ $1$s, supporting the following operations, where $b \in \{ 0, 1 \}$: $rank_b(S,i)$ returns the number of occurrences of bit $b$ in the prefix $S\left[1..i\right]$; $select_b(S,i)$ returns the position of the $i$th occurrence of bit $b$ in $S$. Such a data structure is called \emph{fully indexable dictionary (FID)} [Raman et al.,2007], and is at least as powerful as predecessor data structures. Our focus is on space-efficient FIDs on the \textsc{ram} model with word size $\Theta(\lg m)$ and constant time for all operations, so that the time cost is independent of the input size. Given the bitstring $S$ to be encoded, having length $m$ and containing $n$ ones, the minimal amount of information that needs to be stored is $B(n,m) = \lceil \log {{m}\choose{n}} \rceil$. The state of the art in building a FID for $S$ is given in [Patrascu,2008] using $B(m,n)+O( m / ( (\log m/ t) ^t) ) + O(m^{3/4}) $ bits, to support the operations in $O(t)$ time. Here, we propose a parametric data structure exhibiting a time/space trade-off such that, for any real constants $0 < \delta \leq 1/2$, $0 < \eps \leq 1$, and integer $s > 0$, it uses \[ B(n,m) + O\left(n^{1+\delta} + n \left(\frac{m}{n^s}\right)^\eps\right) \] bits and performs all the operations in time $O(s\delta^{-1} + \eps^{-1})$. The improvement is twofold: our redundancy can be lowered parametrically and, fixing $s = O(1)$, we get a constant-time FID whose space is $B(n,m) + O(m^\eps/\poly{n})$ bits, for sufficiently large $m$. This is a significant improvement compared to the previous bounds for the general case.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.517-528, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [37 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00360601
Contributeur : Publications Loria <>
Soumis le : lundi 16 février 2009 - 10:55:05
Dernière modification le : lundi 16 février 2009 - 14:47:50
Document(s) archivé(s) le : mardi 8 juin 2010 - 22:15:30

Fichiers

grossi-hastewaste_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00360601, version 1
  • ARXIV : 0902.2648

Collections

Citation

Roberto Grossi, Alessio Orlandi, Rajeev Raman, S. Srinivasa Rao. More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.517-528, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00360601〉

Partager

Métriques

Consultations de la notice

64

Téléchargements de fichiers

188