Search for: All records

In a widely-cited 1985 result, Yao showed that any greedy open-addressed hash table, when filled to $$1 - \epsilon$$ full, must incur an amortized expected query time of at least $$\Omega(\log \epsilon^{-1})$$. To overcome this lower bound, prior work has focused on modifying the setup of the insertion algorithm, by either reordering items or placing items non-greedily. We show that, in fact, no such modifications are necessary: by simply decoupling the greedy query algorithm from the greedy insertion algorithm, it is possible to get an amortized expected query time of $O(1).$ The same relaxation also lets us bypass a barrier for worst-case expected query time, bringing the bound down to $$O(\log \epsilon^{-1})$$. Finally, we show how to achieve both of these query bounds while also achieving near-optimal insertion times, for both solutions that do and solutions that do not know the parameter $$\epsilon$$ beforehand. 

One of the most basic problems in dynamic graph algorithms is to maintain a maximal matching as edges are inserted and deleted over time. In a line of work started by Baswana, Gupta and Sen, and then completed by Solomon, it was shown how to solve this problem in amortized expected time $O(1)$ per update. (Interestingly, achieving worst-case expected $O(1)$ remains open.) Recent work by Behnezhad et al.~suggests that very simple alternative algorithm may also perform well: simply maintain a randomized greedy matching. They show that this solution can be used to achieve $$O(\log^4 n)$$ expected time per update. In this paper, we show that the randomized greedy solution is even much more efficient than Behnezhad et al.'s result might seem to suggest, achieving an expected time bound of $$O((\log \log n)^2)$$ per update. This new bound is within a quadratic factor of tight, since one of the $$\log \log n$$ factors unavoidably comes from the algorithm's use of Van Emde Boas trees. Our result comes with several consequences. We obtain a nearly exponential time improvement for the problem of maintaining a history-independent dynamic maximal matching; a nearly exponential time improvement for the problem of maintaining a dynamic maximal matching with \emph{worst-case} expected time guarantees; and a polynomial improvement for the problem of maintaining a dynamic maximal matching with \emph{high-probability} time guarantees. Our result on history independence is of special interest given the major push in the data-structures community in recent years to study history independence as a privacy guarantee for data structures. 

We show how to construct a dynamic ordered dictionary, supporting insert/delete/rank/select on a set of $$n$$ elements from a universe of size $$U$$, that achieves the optimal amortized expected time complexity of $$O(1 + \log n / \log \log U)$$, while achieving a nearly optimal space consumption of $$\log \binom{U}{n} + n / 2^{(\log n)^{\Omega(1)}} + \polylog U$$ bits in the regime where $$U = \poly(n)$$. This resolves an open question by Pibiri and Venturini as to whether a redundancy (a.k.a.\ space overhead) of $o(n)$ bits is possible, and is the first dynamic solution to bypass the so-called tree-structure bottleneck, in which the bits needed to encode some dynamic tree structure are themselves enough to force a redundancy of $$\tilde{\Omega}(n)$$ bits. Our main technical building block is a dynamic balanced binary search tree, which we call the \emph{compressed tabulation-weighted treap}, that itself achieves a surprising time/space tradeoff. The tree supports $$\polylog n$$-time operations and requires a static lookup table of size $$\poly(n) + \polylog U$$---but, in exchange for these, the tree is able to achieve a remarkable space guarantee. Its total space redundancy is $$O(\log U)$$ bits. In fact, if the tree is given $$n$$ and $$U$$ for free, then the redundancy further drops to $O(1)$ bits. 

In recent decades, cloud computing as a service has emerged as a major computing paradigm. These services (e.g., Amazon EC2, Google Compute Engine, Azure Virtual Machines) all offer variations of the following basic model for how storage works: a compute instance can choose between placing data on something that resembles a local disk (e.g., Amazon EBS, Google Block Store, Azure Managed Disks) versus what we will refer to as a global disk (e.g., Amazon S3, Google GCS, Azure Blob Storage). The disks are distinguished by two features:(1) Bandwidth: Whereas the local disk has a fixed limited bandwidth, the global disk offers essentially unlimited bandwidth.(2) Cost: The local disk supports I/Os for free, while the global disk charges money each time an object is read or written.This storage model suggests a natural algorithmic problem: How should a system manage its storage across local and global disk in order to simultaneously optimize cost and performance?In this paper, we formalize this local/global disk problem as follows. A scheduler running many (potentially parallel) processes must serve I/O requests to local/global disks and can move objects between the disks over time. The local disk performs I/Os for free, but can only perform one I/O per timestep, while the global disk charges a fee for each I/O, but has unlimited bandwidth. The scheduler wishes to optimize both the stretch of each process that it runs (the running-time blowup compared to if that process used only global disk) and the overall cost savings (the amount of money saved compared to a world in which we use only the global disk).We show, for any ε ∈ (0, 1] that it is possible to support an expected stretch of 1 + O(ε) while saving a total of εE[T] expected dollars, where T is the number of distinct timesteps in which I/Os are performed. We also offer a second tradeoff curve that, for any δ \v{s} (0, 1), supports expected stretch 1 + O(δ−1) with expected cost savings (1 − δ)E[T]. Finally, we prove that both of these tradeoff curves are asymptotically optimal. 

Themonotone minimal perfect hash function(MMPHF)problem is the following indexing problem. Given a set\(S=\{s_{1},\ldots,s_{n}\}\)of\(n\)distinct keys from a universe\(U\)of size\(u\), create a data structure\(\mathbf{D}\)that answers the following query:\(\rm{{R\small{ANK}}}(q)=\begin{cases}\text{rank of }q\text{ in }S&q\in S \\ \text{arbitrary answer}&\text{otherwise.}\end{cases}\) Solutions to the MMPHF problem are in widespread use in both theory and practice. The best upper bound known for the problem encodes\(\mathbf{D}\)in\(O(n\log\log\log u)\)bits and performs queries in\(O(\log u)\)time. It has been an open problem to either improve the space upper bound or to show that this somewhat odd looking bound is tight. In this article, we show the latter: any data structure (deterministic or randomized) for monotone minimal perfect hashing of any collection of\(n\)elements from a universe of size\(u\)requires\(\Omega(n\cdot\log\log\log{u})\)expected bits to answer every query correctly. We achieve our lower bound by defining a graph\(\mathbf{G}\)where the nodes are the possible\({u\choose n}\)inputs and where two nodes are adjacent if they cannot share the same\(\mathbf{D}\). The size of\(\mathbf{D}\)is then lower bounded by the log of the chromatic number of\(\mathbf{G}\). Finally, we show that the fractional chromatic number (and hence the chromatic number) of\(\mathbf{G}\)is lower bounded by\(2^{\Omega(n\log\log\log u)}\). 

Dynamic filters are data structures supporting approximate membership queries to a dynamic set S of n keys, allowing a small false-positive error rate ε, under insertions and deletions to the set S. Essentially all known constructions for dynamic filters use a technique known as fingerprinting. This technique, which was first introduced by Carter et al. in 1978, inherently requires log(nε−1n)=nlogε−1+nloge−o(n) bits of space when ε=o(1). Whether or not this bound is optimal for all dynamic filters (rather than just for fingerprint filters) has remained for decades as one of the central open questions in the area. We resolve this question by proving a sharp lower bound of nlogε−1+nloge−o(n) bits for ε=o(1), regardless of operation time.