We show that there exists a (strongly) history-independent two-choice balls-and-bins algorithm that supports both insertions and deletions on a set of up to \(m\) balls, while guaranteeing a maximum load of \(m/n + O(1)\) with high probability, and achieving an expected recourse of \(O(\log \log (m/n))\) per operation. To the best of our knowledge, this is the first history-independent solution to achieve nontrivial guarantees of any sort for \(m/n \ge \omega(1)\), and is the first fully dynamic solution (history independent or not) to achieve \(O(1)\) overload with \(o(m/n)\) expected recourse.

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)}} + \operatorname{polylog} U\) bits in the regime where \(U = \operatorname{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 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 \(\operatorname{poly}(n)+\operatorname{polylog} U\unicode{x2014}\)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:

In a widely-cited 1985 result, Yao showed that any greedy open-addressed hash table, when filled to 1 − є full, must incur an amortized expected query time of at least Ω(logє−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є−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 є beforehand.

In the static retrieval problem, a data structure must answer retrieval queries mapping a set of n keys in a universe $[U]$ to v-bit values. Information-theoretically, retrieval data structures can use as little as nv bits of space. For small value sizes v, it is possible to achieve $O(1)$ query time while using space $n v+o(n)$ bits-whether or not such a result is possible for larger values of v (e.g., $v=\Theta(\log n)$) has remained open.In this paper, we obtain a tight lower bound (as well as matching upper bounds) for the static retrieval problem. In the case where values are large, we show that there is actually a significant tension between time and space. It is not possible, for example, to get $O(1)$ query time using $n v+o(n)$ bits of space, when $v=\Theta(\log n)$ (and assuming the word RAM model with $O(\log n)$-bit words)At first glance, our lower bound would seem to render retrieval unusable in many settings that aim to achieve very low redundancy. However, our second result offers a way around this: We show that, whenever a retrieval data structure $D_{1}$ is stored along with another data structure $D_{2}$ (whose size is similar to or larger than the size of $D_{1}$), it is possible to implement the combined data structure $D_{1} \cup D_{2}$ so that queries to $D_{1}$ take $O(1)$ time, operations on $D_{2}$ take the same asymptotic time as if $D_{2}$ were stored on its own, and the total space is $n v+\operatorname{Space}\left(D_{2}\right)+n^{0.67}$ bits.

Dynamic filters are data structures supporting approximate membership queries to a dynamic set S of n keys, allowing a small false-positive error rate $\varepsilon$, 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 \binom{n \varepsilon^{-1}}{n}=n \log \varepsilon^{-1}+n \log e-o(n)$ bits of space when $\varepsilon=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 $n \log \varepsilon^{-1}+n \log e-o(n)$ bits for $\varepsilon=o(1)$, regardless of operation time.

A d-ary cuckoo hash table is an open-addressed hash table that stores each key x in one of d random positions h1 (x ), h 2(x ),…, hd(x ). In the offline setting, where all items are given and keys need only be matched to locations, it is possible to support a load factor of 1 — ϵ while using hashes. The online setting, where keys are moved as new keys arrive sequentially, has the additional challenge of the time to insert new keys, and it has not been known whether one can use d = O (ln ϵ-1) hashes to support poly(ϵ-1) expected-time insertions.

Retrieval data structures are data structures that answer key-value queries without paying the space overhead of explicitly storing keys. The problem can be formulated in four settings (static, value-dynamic, incremental, or dynamic), each of which offers different levels of dynamism to the user. In this paper, we establish optimal bounds for the final two settings (incremental and dynamic) in the case of a polynomial universe. Our results complete a line of work that has spanned more than two decades, and also come with a surprise: the incremental setting, which has long been viewed as essentially equivalent to the dynamic one, actually has a phase transition, in which, as the value size v approaches log n, the optimal space redundancy actually begins to shrink, going from roughly n log log n (which has long been thought to be optimal) all the way down to Θ(n ) (which is the optimal bound even for the seemingly much-easier value-dynamic setting).

Perhaps the most influential result in the theory of caches is the following theorem due to Sleator and Tarjan: With O(1) resource augmentation, the basic LRU eviction policy is guaranteed to be O(1)-competitive with the optimal offline policy.

Abstract. The online list-labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal is to store a dynamically changing set of [Formula: see text] items in an array of [Formula: see text] slots, while maintaining the invariant that the items appear in sorted order and while minimizing the relabeling cost, defined to be the number of items that are moved per insertion/deletion. For the linear regime, where [Formula: see text], an upper bound of [Formula: see text] on the relabeling cost has been known since 1981. A lower bound of [Formula: see text] is known for deterministic algorithms and for so-called smooth algorithms, but the best general lower bound remains [Formula: see text]. The central open question in the field is whether [Formula: see text] is optimal for all algorithms. In this paper, we give a randomized data structure that achieves an expected relabeling cost of [Formula: see text] per operation. More generally, if [Formula: see text] for [Formula: see text], the expected relabeling cost becomes [Formula: see text]. Our solution is history independent, meaning that the state of the data structure is independent of the order in which items are inserted/deleted. For history-independent data structures, we also prove a matching lower bound: for all [Formula: see text] between [Formula: see text] and some sufficiently small positive constant, the optimal expected cost for history-independent list-labeling solutions is [Formula: see text].

The monotone 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)}\) .

The classical paging problem, introduced by Sleator and Tarjan in 1985, formalizes the problem of caching pages in RAM in order to minimize IOs. Their online formulation ignores the cost of address translation: Programs refer to data via virtual addresses, and these must be translated into physical locations in RAM. Although the cost of an individual address translation is much smaller than that of an IO, every memory access involves an address translation, whereas IOs can be infrequent. In practice, one can spend money to avoid paging by over-provisioning RAM; in contrast, address translation is effectively unavoidable. Thus address-translation costs can sometimes dominate paging costs, and systems must simultaneously optimize both. To mitigate the cost of address translation, all modern CPUs have translation lookaside buffers (TLBs), which are hardware caches of common address translations. What makes TLBs interesting is that a single TLB entry can potentially encode the address translation for many addresses. This is typically achieved via the use of huge pages, which translate runs of contiguous virtual addresses to runs of contiguous physical addresses. Huge pages reduce TLB misses at the cost of increasing the IOs needed to maintain contiguity in RAM. This tradeoff between TLB misses and IOs suggests that the classical paging problem does not tell the full story. This article introduces the Address-Translation Problem, which formalizes the problem of maintaining a TLB, a page table, and RAM in order to minimize the total cost of both TLB misses and IOs. We present an algorithm that achieves the benefits of huge pages for TLB misses without the downsides of huge pages for IOs.

This article introduces a new data-structural object that we call the tiny pointer. In many applications, traditional \(\log n\) -bit pointers can be replaced with \(o(\log n)\) -bit tiny pointers at the cost of only a constant-factor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers and give optimal constructions for both fixed-size tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i.e., settings in which the average tiny-pointer size must be small, but some tiny pointers can be larger). If a tiny pointer references an item in an array filled to load factor \(1-\delta\) , then the optimal tiny-pointer size is \(\Theta(\log\log\log n+\log\delta^{-1})\) bits in the fixed-size case, and \(\Theta(\log\delta^{-1})\) expected bits in the variable-size case. Our tiny-pointer constructions also require us to revisit several classic problems having to do with balls and bins; these results may be of independent interest. Using tiny pointers, we apply tiny pointers to five classic data-structure problems. We show that: — A data structure storing \(n\) \(v\) -bit values for \(n\) keys with constant-factor time modifications/queries can be implemented to take space \(nv+O(n\log^{(r)}n)\) bits, for any constant \(r>0\) , as long as the user stores a tiny pointer of expected size \(O(1)\) with each key—here, \(\log^{(r)}n\) is the \(r\) th iterated logarithm. — Any binary search tree can be made succinct, meaning that it achieves \((1+o(1))\) times the optimal space, with constant-factor time overhead, and can even be made to be within \(O(n)\) bits of optimal if we allow for \(O(\log^{*}n)\) -time modifications—this holds even for rotation-based trees such as the splay tree and the red-black tree. — Any fixed-capacity key-value dictionary can be made stable (i.e., items do not move once inserted) with constant-factor time overhead and \((1+o(1))\) -factor space overhead. — Any key-value dictionary that requires uniform-size values can be made to support arbitrary-size values with constant-factor time overhead and with an additional space consumption of \(\log^{(r)}n+O(\log j)\) bits per \(j\) -bit value for an arbitrary constant \(r>0\) of our choice. — Given an external-memory array \(A\) of size \((1+\varepsilon)n\) containing a dynamic set of up to \(n\) key-value pairs, it is possible to maintain an internal-memory stash of size \(O(n\log\varepsilon^{-1})\) bits so that the location of any key-value pair in \(A\) can be computed in constant time (and with no IOs). In each case tiny pointers allow for us to take a natural space-inefficient solution that uses pointers and make it space-efficient for free.

The list-labeling problem captures the basic task of storing a dynamically changing set of up to$n$elements in sorted order in an array of size$m=(1+\Theta(1))n$• The goal is to support insertions and deletions while moving around elements within the array as little as possible. Until recently, the best known upper bound stood at$O(\log^{2}n)$amortized cost. This bound, which was first established in 1981, was finally improved two years ago, when a randomized$O(\log^{3/2}n)$expected-cost algorithm was discovered. The best randomized lower bound for this problem remains$\Omega(\log n)$, and closing this gap is considered to be a major open problem in data structures. In this paper, we present the See-Saw Algorithm, a randomized list-labeling solution that achieves a nearly optimal bound of$O(\log n \text{polyloglog}\ n)$amortized expected cost. This bound is achieved despite at least three lower bounds showing that this type of result is impossible for large classes of solutions.

We introduce a classical open-addressed hash table, called rainbow hashing, that supports a load factor of up to 1$-\varepsilon$, while also supporting$O(1)$expected-time queries, and$O\left({\log \,\log {\varepsilon ^{ - 1}}} \right)$expected-time insertions and deletions. We further prove that this tradeoff curve is optimal: any classical open-addressed hash table that supports load factor$1-\varepsilon$must incur$\Omega \left({\log \,log{\varepsilon ^{ - 1}}} \right)$expected time per operation. Finally, we extend rainbow hashing to the setting where the hash table is dynamically resized over time. Surprisingly, the addition of dynamic resizing does not come at any time cost-even while maintaining a load factor of$\geq 1-\varepsilon$at all times, we can support$O(1)$queries and$O\left({\log \,\log {\varepsilon ^{ - 1}}} \right)$updates. Prior to our work, achieving any time bounds of the form$o(\varepsilon^{-1})$for all of insertions, deletions, and queries simultaneously remained an open Question.

Linear-probing hash tables have been classically believed to support insertions in time$\Theta(x^{2})$, where$1-1/x$is the load factor of the hash table. Recent work by Bender, Kuszmaul, and Kuszmaul (FOCS'21), however, has added a new twist to this story: in some versions of linear probing, if the maximum load factor is at most$1-1/x$, then the amortized expected time per insertion will never exceed$x\ \text{polylog}\ x$(even in workloads that operate continuously at a load factor of$1-1/x$). Determining the exact asymptotic value for the amortized insertion time remains open. In this paper, we settle the amortized complexity with matching upper and lower bounds of$\Theta(x\log^{1.5}x)$. Along the way, we also obtain tight bounds for the so-called path surplus problem, a problem in combinatorial geometry that has been shown to be closely related to linear probing. We also show how to extend Bender et al.'s bounds to say something not just about ordered linear probing (the version they study) but also about classical linear probing, in the form that is most widely implemented in practice.

In this paper, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table so that elements can later be retrieved with as few probes as possible. We show that, even without reordering elements over time, it is possible to construct a hash table that achieves far better expected search complexities (both amortized and worst-case) than were previously thought possible. Along the way, we disprove the central conjecture left by Yao in his seminal paper “Uniform Hashing is Optimal”.

We consider the problem of load-balancing on distributed databases. We assume that data is divided into chunks and each chunk can be replicated on a constant number d of servers. When a request arrives, it is routed to one of the servers that contains the relevant chunk. Each server may store outstanding requests in a bounded queue and requests may be rejected if the queue is full. The goal is to design strategies for data distribution and request routing that minimize both the rejection rate and the average request latency.

This paper introduces the serial-parallel decision problem. Consider an online scheduler that receives a series of tasks, where each task has both a parallel and a serial implementation. The parallel implementation has the advantage that it can make progress concurrently on multiple processors, but the disadvantage that it is (potentially) work-inefficient. As tasks arrive, the scheduler must decide for each task which implementation to use.

A filter is a data structure that answers approximate-membership queries on a set S of n elements, with a false-positive rate of є. A filter is said to be dynamic if it supports insertions/deletions to the set S, subject to a capacity constraint of n. This paper considers the space requirement of filters, regardless of running time. It has been known for decades that static filters have optimal space n logє−1 + O(1) expected bits, and that dynamic filters can be implemented in space n logє−1 + Θ(n) bits. We prove that this Θ(n)-bit gap is fundamental: any dynamic filter must use n logє−1 + Ω(n) bits, no matter the choice of є. Extending our techniques, we are also able to obtain a lower bound for the value-dynamic retrieval problem. Here again, we show that there is a Θ(n)-bit gap between the optimal static and (value-)dynamic solutions.

The list-labeling problem is one of the most basic and well-studied algorithmic primitives in data structures, with an extensive literature spanning upper bounds, lower bounds, and data management applications. The classical algorithm for this problem, dating back to 1981, has amortized cost O(log bn). Subsequent work has led to improvements in three directions: low-latency (worst-case) bounds; high-throughput (expected) bounds; and (adaptive) bounds for important workloads. Perhaps surprisingly, these three directions of research have remained almost entirely disjoint---this is because, so far, the techniques that allow for progress in one direction have forced worsening bounds in the others. Thus there would appear to be a tension between worst-case, adaptive, and expected bounds. List labeling has been proposed for use in databases at least as early as PODS'99, but a database needs good throughput, response time, and needs to adapt to common workloads (e.g., bulk loads), and no current list-labeling algorithm achieve good bounds for all three. We show that this tension is not fundamental. In fact, with the help of new data-structural techniques, one can actually combine any three list-labeling solutions in order to cherry-pick the best worst-case, adaptive, and expected bounds from each of them.

The TLB is increasingly a bottleneck for big data applications. In most designs, the number of TLB entries are highly constrained by latency requirements, and growing much more slowly than the working sets of applications. Many solutions to this problem, such as huge pages, perforated pages, or TLB coalescing, rely on physical contiguity for performance gains, yet the cost of defragmenting memory can easily nullify these gains. This paper introduces mosaic pages, which increase TLB reach by compressing multiple, discrete translations into one TLB entry. Mosaic leverages virtual contiguity for locality, but does not use physical contiguity. Mosaic relies on recent advances in hashing theory to constrain memory mappings, in order to realize this physical address compression without reducing memory utilization or increasing swapping. This paper presents a full-system prototype of Mosaic, in gem5 and modified Linux. In simulation and with comparable hardware to a traditional design, mosaic reduces TLB misses in several workloads by 6-81%. Our results show that Mosaic’s constraints on memory mappings do not harm performance, we never see conflicts before memory is 98% full in our experiments — at which point, a traditional design would also likely swap. Once memory is over-committed, Mosaic swaps fewer pages than Linux in most cases. Finally, we present timing and area analysis for a verilog implementation of the hashing function required on the critical path for the TLB, and show that on a commercial 28nm CMOS process; the circuit runs at a maximum frequency of 4 GHz, indicating that a mosaic TLB is unlikely to affect clock frequency.

A data structure is said to be strongly history independent if its state is fully determined by its current set of elements (and random bits). One of the most basic questions that strongly history-independent algorithms face is storage allocation: given a set S of up to $(1-\epsilon) n+1$ elements, assign them to distinct positions in an array of size n. If we ask that the allocation be strongly history independent, then what is the optimal asymptotic cost of performing an insertion or deletion? On the upper-bound side, Berger et al. (ICALP ’22) showed how to achieve expected cost $O\left(1+\log \epsilon^{-1}\right)$. In this paper, we offer a nearly matching lower bound of $\tilde{\Omega}\left(\log \epsilon^{-1}\right)$. As corollaries, we get nearly tight lower bounds for strongly history-independent hashing (STOC ’01, FOCS ’07, ICALP’ 08) and for the so-called memoryless worker-task assignment problem (SSS ’17, ICALP ’20, ICALP ’22). Next we consider the problem of partitioning an array of size n among many items of different sizes (and whose cumulative sizes are at most $(1-\epsilon) n+1)$. In STOC ’01, Naor and Teague gave a weakly history-independent solution to this problem with logarithmic overhead (and with $\epsilon=1 / 2$); they posed as an open question whether one could hope to do better. We give a new construction that achieves $O(1)$ expected overhead, also for $\epsilon=$ $1 / 2$, and that is strongly history independent. Generalizing to $\epsilon\lt 1 / 2$, our solution achieves expected overhead $O\left(1+\log \epsilon^{-1}\right)$ for insertion/deletions of objects whose sizes are at most $O\left(\epsilon^{4} n\right)$.

The monotone minimal perfect hash function (MMPHF) problem is the following indexing problem. Given a set S = {sı,…, sn} of n distinct keys from a universe U of size u, create a data structure D that answers the following query:

This paper introduces a new data-structural object that we call the tiny pointer. In many applications, traditional log n-bit pointers can be replaced with o(log n)-bit tiny pointers at the cost of only a constant-factor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers, and give optimal constructions for both fixed-size tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i.e., settings in which the average tiny-pointer size must be small, but some tiny pointers can be larger). If a tiny pointer references an element in an array filled to load factor 1 — δ, then the optimal tiny-pointer size is Θ(log log log n + log δ-1) bits in the fixed-size case, and Θ(log δ-1) expected bits in the variable-size case. Our tiny-pointer constructions also require us to revisit several classic problems having to do with balls and bins; these results may be of independent interest. Using tiny pointers, we revisit five classic data-structure problems. We show that: • A data structure storing n v-bit values for n keys with constant-time modifications/queries can be implemented to take space nv + O(n log(r) n) bits, for any constant r > 0, as long as the user stores a tiny pointer of expected size O(1) with each key—here, log(r) n is the r-th iterated logarithm. • Any binary search tree can be made succinct with constant-factor time overhead, and can even be made to be within O(n) bits of optimal if we allow for O(log* n)-time modifications—this holds even for rotation-based trees such as the splay tree and the red-black tree. • Any fixed-capacity key-value dictionary can be made stable (i.e., items do not move once inserted) with constant-time overhead and 1 + o(1) space overhead. • Any key-value dictionary that requires uniform-size values can be made to support arbitrary-size values with constant-time overhead and with an additional space consumption of log(r) n + O(log j) bits per j-bit value for an arbitrary constant r > 0 of our choice. • Given an external-memory array A of size (1 + ε)n containing a dynamic set of up to n key-value pairs, it is possible to maintain an internal-memory stash of size O(n log ε-1) bits so that the location of any key-value pair in A can be computed in constant time (and with no IOs). These are all well studied and classic problems, and in each case tiny pointers allow for us to take a natural space-inefficient solution that uses pointers and make it space-efficient for free.

One of the most basic algorithmic problems concerning caches is to compute the LRU hit-rate curve on a given trace. Unfortunately, the known algorithms exhibit poor data locality and fail to scale to large caches. It is widely believed that the LRU hit-rate curve cannot be computed efficiently enough to be used in online production settings. This has led to a large literature on heuristics that aim to approximate the curve efficiently.

Despite being one of the oldest data structures in computer science, hash tables continue to be the focus of a great deal of both theoretical and empirical research. A central reason for this is that many of the fundamental properties that one desires from a hash table are difficult to achieve simultaneously; thus many variants offering different trade-offs have been proposed. This article introduces Iceberg hashing, a hash table that simultaneously offers the strongest known guarantees on a large number of core properties. Iceberg hashing supports constant-time operations while improving on the state of the art for space efficiency, cache efficiency, and low failure probability. Iceberg hashing is also the first hash table to support a load factor of up to 1 - o(1) while being stable, meaning that the position where an element is stored only ever changes when resizes occur. In fact, in the setting where keys are Θ (log n ) bits, the space guarantees that Iceberg hashing offers, namely that it uses at most \(\log \binom{|U|}{n} + O(n \log \ \text{log} n)\) bits to store n items from a universe U , matches a lower bound by Demaine et al. that applies to any stable hash table. Iceberg hashing introduces new general-purpose techniques for some of the most basic aspects of hash-table design. Notably, our indirection-free technique for dynamic resizing, which we call waterfall addressing, and our techniques for achieving stability and very-high probability guarantees, can be applied to any hash table that makes use of the front-yard/backyard paradigm for hash table design.

Modern hash table designs for DRAM and PMEM strive to minimize space while maximizing speed. The most important factor in speed is the number of cache lines accessed during updates and queries. On PMEM, there is an additional consideration, which is to minimize the number of writes, because on PMEM writes are more expensive than reads. This paper proposes two design objectives, stability and low-associativity, that enable us to build hash tables that minimize cache-line accesses for all operations. A hash table is stable if it does not move items around, and a hash table has low associativity if there are only a few locations where an item can be stored. Low associativity ensures that queries need to examine only a few memory locations, and stability ensures that insertions write to very few cache lines. Stability also simplifies concurrency and, on PMEM, crash safety. We present IcebergHT, a fast, concurrent, space-efficient, and crash-safe (for PMEM) hash table based on the design principles of stability and low associativity. IcebergHT combines in-memory metadata with a new hashing technique, iceberg hashing, that is (1) space efficient, (2) stable, and (3) supports low associativity. In contrast, existing hash-tables either modify numerous cache lines during insertions (e.g. cuckoo hashing), access numerous cache lines during queries (e.g. linear probing), or waste space (e.g. chaining). Moreover, the combination of (1)-(3) yields several emergent benefits: IcebergHT scales better than other hash tables, has excellent performance, and supports crash-safety on PMEM. Our benchmarks show that IcebergHT has excellent performance both in DRAM and PMEM. In PMEM, IcebergHT insertions are 50% to 3× faster than state-of-the-art PMEM hash tables, such as Dash and CLHT, and queries are 20% to 2× faster. IcebergHT space overhead is 17%, whereas Dash and CLHT have space overheads of 2× and 3×, respectively. IcebergHT also scaled linearly throughout our experiments and is crash safe. In DRAM, IcebergHT outperforms state-of-the-art hash tables libcuckoo and CLHT by almost 2× on insertions while offering good query throughput and much better space efficiency.

Dynamic Time Warping (DTW) is a widely used similarity measure for comparing strings that encode time series data, with applications to areas including bioinformatics, signature verification, and speech recognition. The standard dynamic-programming algorithm for DTW takes $O(n^2)$ time, and there are conditional lower bounds showing that no algorithm can do substantially better. In many applications, however, the strings $x$ and $y$ may contain long runs of repeated letters, meaning that they can be compressed using run-length encoding. A natural question is whether the DTW-distance between these compressed strings can be computed efficiently in terms of the lengths $k$ and $\ell$ of the compressed strings. Recent work has shown how to achieve $O(k\ell^2 + \ell k^2)$ time, leaving open the question of whether a near-quadratic $\tilde{O}(k\ell)$-time algorithm might exist. We show that, if a small approximation loss is permitted, then a near-quadratic time algorithm is indeed possible: our algorithm computes a $(1 + ε)$-approximation for $DTW(x, y)$ in $\tilde{O}(k\ell / ε^3)$ time, where $k$ and $\ell$ are the number of runs in $x$ and $y$. Our algorithm allows for $DTW$ to be computed over any metric space $(Σ, δ)$ in which distances are $O(log(n))$-bit integers. Surprisingly, the algorithm also works even if $δ$ does not induce a metric space on $Σ$ (e.g., $δ$ need not satisfy the triangle inequality).

In the 2-choice allocation problem, m balls are placed into n bins, and each ball must choose between two random bins $i,j\in[n]$ that it has been assigned to. It has been known for more than two decades, that if each ball follows the GREEDY strategy (i.e., always pick the less-full bin), then the maximum load will be $m/n+O(\log\log n)$ with high probability in n (and $m/n+O(\log m)$ with high probability in m). It has remained an open question whether the same bounds hold in the dynamic version of the same game, where balls are inserted/deleted with no more than m balls present at a time.We show that, somewhat surprisingly, these bounds do not hold in the dynamic setting: already on 4 bins, there exists a sequence of insertions/deletions that cause the GREEDY strategy to incur a maximum load of $m/4+\Omega(\sqrt{m})$ with probability $\Omega(1)$—this is the same bound that one gets in the single-choice allocation model where each ball is assigned to a random bin!This raises the question of whether any 2-choice allocation strategy can offer a strong bound in the dynamic setting. Our second result answers this question in the affirmative: we present a new strategy, called MODULATEDGREEDY, that guarantees a maximum load of $m/n+O(\log m)$, at any given moment, with high probability in m. We also show how to generalize ModulatedGreedy to obtain dynamic guarantees for the $(1+\beta)$-choice setting, and for the setting of balls-and-bins on a graph.Finally, we consider an extension of the dynamic setting in which balls can be reinserted after they are deleted, and where the pair i, j that a given ball uses is consistent across insertions. This seemingly small modification renders tight load balancing impossible: on 4 bins, any balls-and-bins strategy that is oblivious to the specific identities of balls being inserted/deleted must allow for a maximum load of $m/4+\mathrm{poly}(m)$ at some point in the first poly (m) insertions/deletions, with high probability in m. This is a remarkable departure from the m=n case where the maximum load of O(loglogn) holds independently of whether reinsertions are allowed or not.

The online list-labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal is to store a dynamically-changing set of n items in an array of m slots, while maintaining the invariant that the items appear in sorted order, and while minimizing the relabeling cost, defined to be the number of items that are moved per insertion/deletion. For the linear regime, where $m = (1+\Theta(1))n$, an upper bound of $O(\log^{2}n)$ on the relabeling cost has been known since 1981. A lower bound of $\Omega(\log^{2}n)$ is known for deterministic algorithms and for so-called smooth algorithms, but the best general lower bound remains $\Omega(\log n)$. The central open question in the field is whether $O(\log^{2}n)$ is optimal for all algorithms. In this paper, we give a randomized data structure that achieves an expected relabeling cost of $O(\log^{3/2}n)$ per operation. More generally, if $m=(1+\varepsilon)n$ for $\varepsilon=O(1)$, the expected relabeling cost becomes $O(\varepsilon^{-1}\log^{3/2}n)$. Our solution is history independent, meaning that the state of the data structure is independent of the order in which items are inserted/deleted. For history-independent data structures, we also prove a matching lower bound: for all $\varepsilon$ between $1/n^{1/3}$ and some sufficiently small positive constant, the optimal expected cost for history-independent list-labeling solutions is $\Theta(\varepsilon^{-1}\log^{3/2}n)$.

This paper considers the basic question of how strong of a probabilistic guarantee can a hash table, storing $n(1+\Theta(1))\log n$-bit key/value pairs, offer? Past work on this question has been bottlenecked by limitations of the known families of hash functions: The only hash tables to achieve failure probabilities less than $1/2^{\text{polylog}n}$ require access to fully-random hash functions-if the same hash tables are implemented using the known explicit families of hash functions, their failure probabilities become $1/{poly}(n)$. To get around these obstacles, we show how to construct a randomized data structure that has the same guarantees as a hash table, but that avoids the direct use of hash functions. Building on this, we able to construct a hash table using $O(n)$ random bits that achieves failure probability $1/n^{n^{1-\varepsilon}}$ for an arbitrary positive constant $\varepsilon$. In fact, we show that this guarantee can even be achieved by a succinct dictionary, that is, by a dictionary that uses space within a $1+o(1)$ factor of the information-theoretic optimum. Finally we also construct a succinct hash table whose probabilistic guarantees fall on a different extreme, offering a failure probability of $1/{poly}(n)$ while using only $\tilde{O}(\log n)$ random bits. This latter result replicates a guarantee previously achieved by Dietzfelbinger et al., but with increased space efficiency and with several surprising technical components.

We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of $w$ workers and a multiset $T \subseteq[t]$ of $|T|=w$ tasks, a memoryless worker-task assignment function is any function $ϕ$ that assigns the workers $[w]$ to the tasks $T$ based only on the current value of $T$. The assignment function $ϕ$ is said to have switching cost at most $k$ if, for every task multiset $T$, changing the contents of $T$ by one task changes $ϕ(T)$ by at most $k$ worker assignments. The goal of memoryless worker task assignment is to construct an assignment function with the smallest possible switching cost. In past work, the problem of determining the optimal switching cost has been posed as an open question. There are no known sub-linear upper bounds, and after considerable effort, the best known lower bound remains 4 (ICALP 2020). We show that it is possible to achieve polylogarithmic switching cost. We give a construction via the probabilistic method that achieves switching cost $O(\log w \log (wt))$ and an explicit construction that achieves switching cost $\operatorname{polylog} (wt)$. We also prove a super-constant lower bound on switching cost: we show that for any value of $w$, there exists a value of $t$ for which the optimal switching cost is $w$. Thus it is not possible to achieve a switching cost that is sublinear strictly as a function of $w$. Finally, we present an application of the worker-task assignment problem to a metric embeddings problem. In particular, we use our results to give the first low-distortion embedding from sparse binary vectors into low-dimensional Hamming space.

The p-processor cup game is a classic and widely studied scheduling problem that captures the setting in which a p-processor machine must assign tasks to processors over time in order to ensure that no individual task ever falls too far behind. The problem is formalized as a multi-round game in which two players, a filler (who assigns work to tasks) and an emptier (who schedules tasks) compete. The emptier’s goal is to minimize backlog, which is the maximum amount of outstanding work for any task. Recently, Kuszmaul and Westover (ITCS, 2021) proposed the variable-processor cup game, which considers the same problem, except that the amount of resources available to the players (i.e., the number p of processors) fluctuates between rounds of the game. They showed that this seemingly small modification fundamentally changes the dynamics of the game: whereas the optimal backlog in the fixed p-processor game is Θ(log n), independent of p, the optimal backlog in the variable-processor game is Θ(n). The latter result was only known to apply to games with exponentially many rounds, however, and it has remained an open question what the optimal tradeoff between time and backlog is for shorter games. This paper establishes a tight trade-off curve between time and backlog in the variable-processor cup game. We show that, for a game consisting of t rounds, the optimal backlog is Θ (b (t)) where b(t) = t (if t ≤ log n) t^{1/3} log^{2/3} ({n^3}/t + 1) (if log n < t ≤ n^3) n (if n ^ 3 < t). An important consequence is that the optimal backlog is Θ(n) if and only if t ≥ Ω(n³). Our techniques also allow for us to resolve several other open questions concerning how the variable-processor cup game behaves in beyond-worst-case-analysis settings.

The classical paging problem can be described as follows: given a cache that can hold up to k pages (or blocks) and a sequence of requests to pages, how should we manage the cache so as to maximize performance-or, in other words, complete the sequence as quickly as possible. Whereas this sequential paging problem has been well understood for decades, the parallel version, where the cache is shared among p processors each issuing its own sequence of page requests, has been much more resistant. In this problem we are given p request sequences R1, R2, . . . , Rp , each of which accesses a disjoint set of pages, and we ask the question: how should the paging algorithm manage the cache to optimize the completion time of all sequences (i.e., the makespan). As for the classical sequential problem, the goal is to design an online paging algorithm that achieves an optimal competitive ratio, using O(1) resource augmentation.

For nearly six decades, the central open question in the study of hash tables has been to determine the optimal achievable tradeoff curve between time and space. State-of-the-art hash tables offer the following guarantee: If keys/values are Θ(logn) bits each, then it is possible to achieve constant-time insertions/deletions/queries while wasting only O(loglogn) bits of space per key when compared to the information-theoretic optimum—this bound has been proven to be optimal for a number of closely related problems (e.g., stable hashing, dynamic retrieval, and dynamically-resized filters).

First introduced in 1954, linear probing is one of the oldest data structures in computer science, and due to its unrivaled data locality, it continues to be one of the fastest hash tables in practice. It is widely believed and taught, however, that linear probing should never be used at high load factors; this is because primary-clustering effects cause insertions at load factor $1 - 1 /x$ to take expected time $Θ(x^2)$ (rather than the ideal $Θ(x)$). The dangers of primary clustering, first discovered by Knuth in 1963, have been taught to generations of computer scientists, and have influenced the design of some of many widely used hash tables. We show that primary clustering is not a foregone conclusion. We demonstrate that small design decisions in how deletions are implemented have dramatic effects on the asymptotic performance of insertions, so that, even if a hash table operates continuously at a load factor $1 - Θ(1/x)$, the expected amortized cost per operation is $\tilde{O}(x)$. This is because tombstones created by deletions actually cause an anti-clustering effect that combats primary clustering. We also present a new variant of linear probing (which we call graveyard hashing) that completely eliminates primary clustering on \emph{any} sequence of operations: if, when an operation is performed, the current load factor is $1 - 1/x$ for some $x$, then the expected cost of the operation is $O(x)$. One corollary is that, in the external-memory model with a data blocks of size $B$, graveyard hashing offers the following remarkable guarantee: at any load factor $1 - 1/x$ satisfying $x = o(B)$, graveyard hashing achieves $1 + o(1)$ expected block transfers per operation. Past external-memory hash tables have only been able to offer a $1 + o(1)$ guarantee when the block size $B$ is at least $Ω(x^2)$.

The linear-probing hash table is one of the oldest and most widely used data structures in computer science. However, linear probing famously comes with a major draw-back: as soon as the hash table reaches a high memory utilization, elements within the hash table begin to cluster together, causing insertions to become slow. This phenomenon, now known as primary clustering, was first captured by Donald Knuth in 1963; at a load factor of$1 -1/x$, the expected time per insertion is$\Theta(x^{2})$, rather than the more desirable$\Theta(x)$. We show that there is more to the story than the classic analysis would seem to suggest. It turns out that small design decisions in how deletions are implemented have dramatic effects on the asymptotic performance of insertions. If these design decisions are made correctly, then even a hash table that is continuously at a load factor$1-\Theta(1/x)$can achieve average insertion time$\tilde{O}(x)$. A key insight is that the tombstones left behind by deletions cause a surprisingly strong “anti-clustering” effect, and that when insertions and deletions are one-for-one, the anti-clustering effects of deletions actually overpower the clustering effects of insertions. We also present a new variant of linear probing, which we call graveyard hashing, that completely eliminates primary clustering on any sequence of operations. If, when an operation is performed, the current load factor is$1 -1/x$for some$x$, then the expected cost of the operation is$O(x)$. One corollary is that, in the external-memory model with a data block size of$B$, graveyard hashing offers the following remarkable guarantee: at any load factor$1 -1/x$satisfying$x=o(B)$, graveyard hashing achieves$1 +o(1)$expected block transfers per operation. Past external-memory hash tables have only been able to offer a$1 +o(1)$guarantee when the block size$B$is at least$\Omega(x^{2})$. Our results come with actionable lessons for both theoreticians and practitioners, in particular, that well-designed use of tombstones can completely change the asymptotic landscape of how the linear probing behaves (and if there are no deletions).

The generalized sorting problem is a restricted version of standard comparison sorting where we wish to sort$n$elements but only a subset of pairs are allowed to be compared. Formally, there is some known graph$G=(V, E)$on the$n$elements$v_{1, \ldots, v_{n}}$, and the goal is to determine the true order of the elements using as few comparisons as possible, where all comparisons ($v_{i, v_{j}}$) must be edges in$E$. We are promised that if the true ordering is$x_{1 < x_{2} < \cdots < x_{n}}$for$\{x_{i\}}$an unknown permutation of the vertices$\{v_{i\}}$, then$(x_{i, x_{i+1})\in E}$for all$i$: this Hamiltonian path ensures that sorting is actually possible. In this work, we improve the bounds for generalized sorting on both random graphs and worst-case graphs. For Erdős-Renyi random graphs$G(n, p)$(with the promised Hamiltonian path added to ensure sorting is possible), we provide an algorithm for generalized sorting with an expected$O(n\ \text{lg}(np))$comparisons, which we prove to be optimal for query complexity. This strongly improves over the best known algorithm of Huang, Kannan, and Khanna (FOCS 2011), which uses$\tilde{O(\min(n\sqrt{np},\ n/p^{2}))}$comparisons. For arbitrary graphs$G$with$n$vertices and$m$edges (again with the promised Hamiltonian path), we provide an algorithm for generalized sorting with$\tilde{O(\sqrt{mn})}$comparisons. This improves over the best known algorithm of Huang et al., which uses$\min(m,\tilde{O}(n^{3/2}))$comparisons.

In the parallel paging problem, there are p processors that share a cache of size k. The goal is to partition the cache among the processors over time in order to minimize their average completion time. For this long-standing open problem, we give tight upper and lower bounds of Θ(logp) on the competitive ratio with O(1) resource augmentation. A key idea in both our algorithms and lower bounds is to relate the problem of parallel paging to the seemingly unrelated problem of green paging. In green paging, there is an energy-optimized processor that can temporarily turn off one or more of its cache banks (thereby reducing power consumption), so that the cache size varies between a maximum size k and a minimum size k/p. The goal is to minimize the total energy consumed by the computation, which is proportional to the integral of the cache size over time. We show that any efficient solution to green paging can be converted into an efficient solution to parallel paging, and that any lower bound for green paging can be converted into a lower bound for parallel paging, in both cases in a black-box fashion. We then show that, with O(1) resource augmentation, the optimal competitive ratio for deterministic online green paging is Θ(log p), which, in turn, implies the same bounds for deterministic online parallel paging.

In each step of the cup game on n cups, a filler distributes up to 1 – ∊ water among the cups, and then an emptier removes 1 unit of water from a single cup. The emptier's goal is to minimize the height of the fullest cup, also known as the backlog. The cup emptying game has found extensive applications to processor scheduling, network-switch buffer management, quality of service guarantees, and data-structure deamortization. The greedy emptying algorithm (i.e., always remove from the fullest cup) is known to achieve backlog O(log n) and to be the optimal deterministic algorithm. Randomized algorithms can do significantly better, achieving backlog O (log log n) with high probability, as long as ∊ is not too small. In order to achieve these improvements, the known randomized algorithms require that the filler is an oblivious adversary, unaware of which cups the emptier chooses to empty out of at each step. Such randomized guarantees are known to be impossible against fully adaptive fillers. We show that, even when the filler is just “slightly” non-adaptive, randomized emptying algorithms can still guarantee a backlog of O (log log n). In particular, we give randomized randomized algorithms against an elevated adaptive filler, which is an adaptive filler that can see the precise fills of every cup containing more than 3 units of water, but not of the cups containing less than 3 units.

The classical paging problem, introduced by Sleator and Tarjan in 1985, formalizes the problem of caching pages in RAM in order to minimize IOs. Their online formulation ignores the cost of address translation: programs refer to data via virtual addresses, and these must be translated into physical locations in RAM. Although the cost of an individual address translation is much smaller than that of an IO, every memory access involves an address translation, whereas IOs can be infrequent. In practice, one can spend money to avoid paging by over-provisioning RAM; in contrast, address translation is effectively unavoidable. Thus address-translation costs can sometimes dominate paging costs, and systems must simultaneously optimize both.

The cup game on n cups is a multi-step game with two players, a filler and an emptier. At each step, the filler distributes 1 unit of water among the cups, and then the emptier selects a single cup to remove (up to) 1 unit of water from.

Buffer-and-flush is a technique for transforming standard external-memory search trees into write-optimized search trees. In exchange for faster amortized insertions, buffer-and-flush can sometimes significantly increase the latency of operations by causing cascades of flushes. In this paper, we show that flushing cascades are not a fundamental consequence of the buffer-flushing technique, and can be removed entirely using randomization techniques. The underlying implementation of buffer flushing relies on a buffer-eviction strategy at each node in the tree. The ability for the user to select the buffer eviction strategy based on the workload has been shown to be important for performance, both in theory and in practice. In order to support arbitrary buffer-eviction strategies, we introduce the notion of a universal flush, which uses a universal eviction policy that can simulate any other eviction policy. This abstracts away the underlying eviction strategy, even allowing for workload-specific strategies that change dynamically. Our deamortization preserves the amortized throughput of the underlying flushing strategy on all workloads. In particular, with our deamortization and a node cache of size poly-logarithmic in the number of insertions performed on the tree, the amortized insertion cost matches the lower bound of Brodal and Fagerberg. For typical parameters, the lower bound is less than 1 I/O per insertion. For such parameters, our worst-case insertion cost is O(1) I/Os.

In each step of the p-processor cup game on n cups, a filler distributes up to p units of water among the cups, subject only to the constraint that no cup receives more than 1 unit of water; an emptier then removes up to 1 unit of water from each of p cups. Designing strategies for the emptier that minimize backlog (i.e., the height of the fullest cup) is important for applications in processor scheduling, buffer management in networks, quality of service guarantees, and deamortization. We prove that the greedy algorithm (i.e., the empty-from-fullest-cups algorithm) achieves backlog O(log n) for any p ≥ 1. This resolves a long-standing open problem for p > 1, and is asymptotically optimal as long as n ≥ 2p. If the filler is an oblivious adversary, then we prove that there is a randomized emptying algorithm that achieve backlog O(log p + log log n) with probability 1 – 2− polylog(n) for 2polylog(n) steps. This is known to be asymptotically optimal when n is sufficiently large relative to p. The analysis of the randomized algorithm can also be reinterpreted as a smoothed analysis of the deterministic greedy algorithm. Previously, the only known bound on backlog for p > 1, and the only known randomized guarantees for any p (including when p = 1), required the use of resource augmentation, meaning that the filler can only distribute at most p(1 – ϵ) units of water in each step, and that the emptier is then permitted to remove 1 + δ units of water from each of p cups, for some ϵ, δ > 0. w

We study two fundamental variants of the classic paging problem: green paging and parallel paging. In green paging one can choose the exact memory capacity in use at any given instant, between a maximum of k and a minimum of k/p pages; the goal is to minimize the integral of this number over the time required to complete a computation (note that running at lower capacity is not necessarily better, since might disproportionately increase the total completion time). In parallel paging, a memory of k pages is shared between p processors, each carrying out a separate computation; the goal is to minimize the respective completion times.

Cache-adaptive analysis was introduced to analyze the performance of an algorithm when the cache (or internal memory) available to the algorithm dynamically changes size. These memory-size fluctuations are, in fact, the common case in multi-core machines, where threads share cache and RAM. An algorithm is said to be efficiently cache-adaptive if it achieves optimal utilization of the dynamically changing cache. Cache-adaptive analysis was inspired by cache-oblivious analysis. Many (or even most) optimal cache-oblivious algorithms have an $(a,b,c)$-regular recursive structure. Such $(a, b, c)$-regular algorithms include Longest Common Subsequence, All Pairs Shortest Paths, Matrix Multiplication, Edit Distance, Gaussian Elimination Paradigm, etc. Bender et al. (2016) showed that some of these optimal cache-oblivious algorithms remain optimal even when cache changes size dynamically, but that in general they can be as much as logarithmic factor away from optimal. However, their analysis depends on constructing a highly structured, worst-case memory profile, or sequences of fluctuations in cache size. These worst-case profiles seem fragile, suggesting that the logarithmic gap may be an artifact of an unrealistically powerful adversary. We close the gap between cache-oblivious and cache-adaptive analysis by showing how to make a smoothed analysis of cache-adaptive algorithms via random reshuffling of memory fluctuations. Remarkably, we also show the limits of several natural forms of smoothing, including random perturbations of the cache size and randomizing the algorithm's starting time. Nonetheless, we show that if one takes an arbitrary profile and performs a random shuffle on when "significant events'' occur within the profile, then the shuffled profile becomes optimally cache-adaptive in expectation, even when the initial profile is adversarially constructed. These results suggest that cache-obliviousness is a solid foundation for achieving cache-adaptivity when the memory profile is not overly tailored to the algorithm structure.

We present an in-place algorithm for the parallel-partition problem with linear work and polylogarithmic span. The algorithm uses only exclusive read/write shared variables and can be implemented using parallel-for-loops without any additional concurrency considerations (i.e., the algorithm is EREW). A key feature of the algorithm is that it exhibits provably optimal cache behavior up to small-order factors.

This paper focuses on the contention resolution problem on a shared communication channel that does not support collision detection. A shared communication channel is a multiple access channel, which consists of a sequence of synchronized time slots. Players on the channel may attempt to broadcast a packet (message) in any time slot. A player's broadcast succeeds if no other player broadcasts during that slot. If two or more players broadcast in the same time slot, then the broadcasts collide and both broadcasts fail. The lack of collision detection means that a player monitoring the channel cannot differentiate between the case of two or more players broadcasting in the same slot (a collision) and zero players broadcasting. In the contention-resolution problem, players arrive on the channel over time, and each player has one packet to transmit. The goal is to coordinate the players so that each player is able to successfully transmit its packet within reasonable time. However, the players can only communicate via the shared channel by choosing to either broadcast or not. A contention-resolution protocol is measured in terms of its throughput (channel utilization). Previous work on contention resolution that achieved constant throughput assumed that either players could detect collisions, or the players' arrival pattern is generated by a memoryless (non-adversarial) process.

We resolve the randomized one-way communication complexity of Dynamic Time Warping (DTW) distance. We show that there is an efficient one-way communication protocol using $\widetilde{O}(n/α)$ bits for the problem of computing an $α$-approximation for DTW between strings $x$ and $y$ of length $n$, and we prove a lower bound of $Ω(n / α)$ bits for the same problem. Our communication protocol works for strings over an arbitrary metric of polynomial size and aspect ratio, and we optimize the logarithmic factors depending on properties of the underlying metric, such as when the points are low-dimensional integer vectors equipped with various metrics or have bounded doubling dimension. We also consider linear sketches of DTW, showing that such sketches must have size $Ω(n)$.

Dynamic time warping distance (DTW) is a widely used distance measure between time series, with applications in areas such as speech recognition and bioinformatics. The best known algorithms for computing DTW run in near quadratic time, and conditional lower bounds prohibit the existence of significantly faster algorithms. The lower bounds do not prevent a faster algorithm for the important special case in which the DTW is small, however. For an arbitrary metric space Sigma with distances normalized so that the smallest non-zero distance is one, we present an algorithm which computes dtw(x, y) for two strings x and y over Sigma in time O(n * dtw(x, y)). When dtw(x, y) is small, this represents a significant speedup over the standard quadratic-time algorithm. Using our low-distance regime algorithm as a building block, we also present an approximation algorithm which computes dtw(x, y) within a factor of O(n^epsilon) in time O~(n^{2 - epsilon}) for 0 < epsilon < 1. The algorithm allows for the strings x and y to be taken over an arbitrary well-separated tree metric with logarithmic depth and at most exponential aspect ratio. Notably, any polynomial-size metric space can be efficiently embedded into such a tree metric with logarithmic expected distortion. Extending our techniques further, we also obtain the first approximation algorithm for edit distance to work with characters taken from an arbitrary metric space, providing an n^epsilon-approximation in time O~(n^{2 - epsilon}), with high probability. Finally, we turn our attention to the relationship between edit distance and dynamic time warping distance. We prove a reduction from computing edit distance over an arbitrary metric space to computing DTW over the same metric space, except with an added null character (whose distance to a letter l is defined to be the edit-distance insertion cost of l). Applying our reduction to a conditional lower bound of Bringmann and Künnemann pertaining to edit distance over {0, 1}, we obtain a conditional lower bound for computing DTW over a three letter alphabet (with distances of zero and one). This improves on a previous result of Abboud, Backurs, and Williams, who gave a conditional lower bound for DTW over an alphabet of size five. With a similar approach, we also prove a reduction from computing edit distance (over generalized Hamming Space) to computing longest-common-subsequence length (LCS) over an alphabet with an added null character. Surprisingly, this means that one can recover conditional lower bounds for LCS directly from those for edit distance, which was not previously thought to be the case.

We present an algorithm for approximating the edit distance ed(x, y) between two strings x and y in time parameterized by the degree to which one of the strings x satisfies a natural pseudorandomness property. The pseudorandomness model is asymmetric in that no requirements are placed on the second string y, which may be constructed by an adversary with full knowledge of x. We say that x is (p, B)-pseudorandom if all pairs a and b of disjoint B-letter substrings of x satisfy ed(a, b) ≥ pB. Given parameters p and B, our algorithm computes the edit distance between a (p, B)-pseudorandom string x and an arbitrary string y within a factor of O(1/p) in time Õ(nB), with high probability. If x is generated at random, then with high probability it will be (Ω(1), O(log n))-pseudorandom, allowing us to compute ed(x, y) within a constant factor in near linear time. For strings x of varying degrees of pseudorandomness, our algorithm offers a continuum of runtimes. Our algorithm is robust in the sense that it can handle a small portion of x being adversarial (i.e., not satisfying the pseudorandomness property). In this case, the algorithm incurs an additive approximation error proportional to the fraction of x which behaves maliciously. The asymmetry of our pseudorandomness model has particular appeal for the case where x is a source string, meaning that ed(x, y) will be computed for many strings y. Suppose that one wishes to achieve an O(α)-approximation for each ed(x, y) computation, and that B is the smallest block-size for which the string x is (1/α, B)-pseudorandom. We show that without knowing B beforehand, x may be preprocessed in time , so that all future computations of the form ed(x, y) may be O(α)-approximated in time Õ(nB). Furthermore, for the special case where only a single ed(x, y) computation will be performed, we show how to achieve an O(α)-approximation in time Õ(n4/3 B2/3).

Many problems in processor scheduling, deamortization, and buffer management can be modeled as single- and multi-processor cup games.

Edit distance is a fundamental measure of distance between strings and has been widely studied in computer science. While the problem of estimating edit distance has been studied extensively, the equally important question of actually producing an alignment (i.e., the sequence of edits) has received far less attention. Somewhat surprisingly, we show that any algorithm to estimate edit distance can be used in a black-box fashion to produce an approximate alignment of strings, with modest loss in approximation factor and small loss in run time. Plugging in the result of Andoni, Krauthgamer, and Onak, we obtain an alignment that is a $(\log n)^{O(1/\varepsilon^2)}$ approximation in time $\tilde{O}(n^{1 + \varepsilon})$. Closely related to the study of approximation algorithms is the study of metric embeddings for edit distance. We show that min-hash techniques can be useful in designing edit distance embeddings through three results: (1) An embedding from Ulam distance (edit distance over permutations) to Hamming space that matches the best known distortion of $O(\log n)$ and also implicitly encodes a sequence of edits between the strings; (2) In the case where the edit distance between the input strings is known to have an upper bound $K$, we show that embeddings of edit distance into Hamming space with distortion $f(n)$ can be modified in a black-box fashion to give distortion $O(f(\operatorname{poly}(K)))$ for a class of periodic-free strings; (3) A randomized dimension-reduction map with contraction $c$ and asymptotically optimal expected distortion $O(c)$, improving on the previous $\tilde{O}(c^{1 + 2 / \log \log \log n})$ distortion result of Batu, Ergun, and Sahinalp.

Cuckoo hashing guarantees constant-time lookups regardless of table density, making it a viable candidate for high-density tables. Cuckoo hashing insertions perform poorly at high table densities, however. In this paper, we mitigate this problem through the introduction of novel kick-out eviction algorithms. Experimentally, our algorithms reduce the number of bins viewed per insertion for high-density tables by as much as a factor of ten. We also implement an optimistic concurrency scheme for serializable multi-writer cuckoo hash tables (not using hardware transactional memory). For delete-light loads, one of our kick-out schemes avoids all competition between insertions with high probability, and significantly reduces transaction-abort frequency. This result is extended to arbitrary workloads using a new mechanism called a claim flag.

In a multistage network, hotspots induce tree saturation. The known solutions employ a variety of techniques, including combining (which works only for certain kinds of messages), feedback damping (which appears to provide low utilization in the absence of hot spots), and large numbers of buffers. In practice, the approach used today is to provide large numbers of buffers: in a P-processor system, the rule of thumb appears to be to provide $10P$ buffers, but 10P buffers may be too expensive for systems containing 105 or more processors. Even employing $\Omega(P)$ buffers does not appear to provide any guarantees, however. This paper shows that by organizing the switches so that the messages addressed to a particular processor can use only certain of the buffers, many hotspots can be tolerated with few buffers. For example, a switch with $O(\log P)$ buffers can tolerate a single hotspot with probability $1$, and allows the first few hotspots to have a large number of buffers before being declared a hotspot. A switch with B buffers will block a given non-hotspot message with probability less than $O(1/s)$ if there are $O(B/\log s)$ hotspots, and can handle a factor of O(ln \ln s) more hotspots before the probability becomes a constant. A similar approach can also be used to improve caching behavior in a multithreaded system in which one of the threads tries to consume all of the cache.