Source author record

Alfredo Viola

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Information Theory math.AC math.CO math.IT

Catalog footprint

Research overview

4works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Robin Hood Hashing really has constant average search cost and variance in full tables

Thirty years ago, the Robin Hood collision resolution strategy was introduced for open addressing hash tables, and a recurrence equation was found for the distribution of its search cost. Although this recurrence could not be solved analytically, it allowed for numerical computations that, remarkably, suggested that the variance of the search cost approached a value of $1.883$ when the table was full. Furthermore, by using a non-standard mean-centered search algorithm, this would imply that searches could be performed in expected constant time even in a full table. In spite of the time elapsed since these observations were made, no progress has been made in proving them. In this paper we introduce a technique to work around the intractability of the recurrence equation by solving instead an associated differential equation. While this does not provide an exact solution, it is sufficiently powerful to prove a bound for the variance, and thus obtain a proof that the variance of Robin Hood is bounded by a small constant for load factors arbitrarily close to 1. As a corollary, this proves that the mean-centered search algorithm runs in expected constant time. We also use this technique to study the performance of Robin Hood hash tables under a long sequence of insertions and deletions, where deletions are implemented by marking elements as deleted. We prove that, in this case, the variance is bounded by $1/(1-α)+O(1)$ , where $α$ is the load factor. To model the behavior of these hash tables, we use a unified approach that can be applied also to study the First-Come-First-Served and Last-Come-First-Served collision resolution disciplines, both with and without deletions.

preprint2014arXiv

A unified approach to linear probing hashing with buckets

We give a unified analysis of linear probing hashing with a general bucket size. We use both a combinatorial approach, giving exact formulas for generating functions, and a probabilistic approach, giving simple derivations of asymptotic results. Both approaches complement nicely, and give a good insight in the relation between linear probing and random walks. A key methodological contribution, at the core of Analytic Combinatorics, is the use of the symbolic method (based on q-calculus) to directly derive the generating functions to analyze.

preprint2013arXiv

Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields

We present counting methods for some special classes of multivariate polynomials over a finite field, namely the reducible ones, the s-powerful ones (divisible by the s-th power of a nonconstant polynomial), and the relatively irreducible ones (irreducible but reducible over an extension field). One approach employs generating functions, another one uses a combinatorial method. They yield exact formulas and approximations with relative errors that essentially decrease exponentially in the input size.

preprint2013arXiv

Optimal prefix codes for pairs of geometrically-distributed random variables

Optimal prefix codes are studied for pairs of independent, integer-valued symbols emitted by a source with a geometric probability distribution of parameter $q$ , $0{<}q{<}1$ . By encoding pairs of symbols, it is possible to reduce the redundancy penalty of symbol-by-symbol encoding, while preserving the simplicity of the encoding and decoding procedures typical of Golomb codes and their variants. It is shown that optimal codes for these so-called two-dimensional geometric distributions are \emph{singular}, in the sense that a prefix code that is optimal for one value of the parameter $q$ cannot be optimal for any other value of $q$ . This is in sharp contrast to the one-dimensional case, where codes are optimal for positive-length intervals of the parameter $q$ . Thus, in the two-dimensional case, it is infeasible to give a compact characterization of optimal codes for all values of the parameter $q$ , as was done in the one-dimensional case. Instead, optimal codes are characterized for a discrete sequence of values of $q$ that provide good coverage of the unit interval. Specifically, optimal prefix codes are described for $q=2^{-1/k}$ ( $k\ge 1$ ), covering the range $q\ge 1/2$ , and $q=2^{-k}$ ( $k>1$ ), covering the range $q<1/2$ . The described codes produce the expected reduction in redundancy with respect to the one-dimensional case, while maintaining low complexity coding operations.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.