{
"@context": "http://schema.org",
"@type": "ScholarlyArticle",
"@id": "https://doi.org/10.4230/lipics.stacs.2009.1847",
"identifier": {
"@type": "PropertyValue",
"propertyID": "DOI",
"value": "https://doi.org/10.4230/lipics.stacs.2009.1847"
},
"url": "http://drops.dagstuhl.de/opus/volltexte/2009/1847/",
"additionalType": "ConferencePaper",
"name": "More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries",
"author": [
{
"name": "Roberto Grossi",
"givenName": "Roberto",
"familyName": "Grossi",
"@type": "Person"
},
{
"name": "Alessio Orlandi",
"givenName": "Alessio",
"familyName": "Orlandi",
"@type": "Person"
},
{
"name": "Rajeev Raman",
"givenName": "Rajeev",
"familyName": "Raman",
"@type": "Person"
},
{
"name": "S. Srinivasa Rao",
"givenName": "S. Srinivasa",
"familyName": "Rao",
"@type": "Person"
}
],
"editor": {
"name": "Marc Herbstritt",
"givenName": "Marc",
"familyName": "Herbstritt",
"contributorType": "Editor",
"@type": "Person"
},
"description": "We consider the problem of representing, in a compressed format, a bit-vector~$S$ of $m$ bits with $n$ $\\mathbf{1}$s, supporting the following operations, where $b \\in \\{ \\mathbf{0}, \\mathbf{1} \\}$:\n\\begin{itemize}\n\\item $\\mathtt{rank}_b(S,i)$ returns the number of occurrences of bit $b$ in the prefix $S\\left[1..i\\right]$;\n\\item $\\mathtt{select}_b(S,i)$ returns the position of the $i$th occurrence of bit $b$ in $S$.\n\\end{itemize}\nSuch a data structure is called \\emph{fully indexable dictionary (\\textsc{fid})} [Raman, Raman, and Rao, 2007], and is at least as powerful as predecessor data structures. Viewing $S$ as a set $X = \\{ x_1, x_2, \\ldots, x_n \\}$ of $n$ distinct integers drawn from a universe $[m] = \\{1, \\ldots, m\\}$, the predecessor of integer $y \\in [m]$ in $X$ is given by $\\ensuremath{\\mathtt{select}^{}_1}(S, \\ensuremath{\\mathtt{rank}_1}(S,y-1))$. {\\textsc{fid}}s have many applications in succinct and compressed data structures, as they are often involved in the construction of succinct representation for a variety of abstract data types.\n\nOur focus is on space-efficient {\\textsc{fid}}s 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.\n\nGiven 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 \\textsc{fid}\\ for~$S$ is given in~\\mbox{}[P\\v{a}tra\\c{s}cu, 2008] using $B(m,n)+O( m / ( (\\log m/ t) ^t) ) + O(m^{3/4}) $ bits, to support the operations in $O(t)$ time.\n\nHere, we propose a parametric data structure exhibiting a time/space trade-off such that, for any real constants $0 < \\delta \\leq 1/2$, $0 < \\varepsilon \\leq 1$, and integer $s > 0$, it uses\n\\[ B(n,m) + O\\left(n^{1+\\delta} + n \\left(\\frac{m}{n^s}\\right)^\\varepsilon\\right) \\]\nbits and performs all the operations in time $O(s\\delta^{-1} + \\varepsilon^{-1})$. The improvement is twofold: our redundancy can be lowered parametrically and, fixing $s = O(1)$, we get a constant-time \\textsc{fid}\\ whose space is $B(n,m) + O(m^\\varepsilon/\\mathrm{poly}(n))$ bits, for sufficiently large $m$. This is a significant improvement compared to the previous bounds for the general case.",
"keywords": "Computer Science, 000 Computer science, knowledge, general works",
"inLanguage": "eng",
"contentSize": "12 pages",
"encodingFormat": "application/pdf",
"datePublished": "2009",
"schemaVersion": "http://datacite.org/schema/kernel-2.1",
"publisher": {
"@type": "Organization",
"name": "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany"
},
"provider": {
"@type": "Organization",
"name": "datacite"
}
}