From Big Data Theory to Big Data Practice

The talk presents results on using shared caches where $p$ disjoint request sequences are trying to access a cache concurrently.

In this talk we revisit the classical problem of randomized exponential backoff on a multiple-access channel. We show how to achieve constant throughput even when the players cannot detect collisions, i.e, simultaneous transmissions, on the channel.

We consider the predecessor problem on the ultra-wide word RAM model of computation, which extends the word RAM model with ultrawords consisting of $w^2$ bits [TAMC, 2015]. The model supports arithmetic and boolean operations on ultrawords, in addition to scattered memory opera- tions that access or modify w (potentially non-contiguous) memory addresses simultaneously. The ultra-wide word RAM model captures (and idealizes) modern vector processor architectures. Our main result is a simple, linear space data structure that supports predecessor in constant time and updates in amortized, expected constant time. This improves the space of the previous constant time solution that uses space in the order of the size of the universe. Our result holds even in a weaker model where ultrawords consist of $w^{(1+\epsilon )}$ bits for any $\epsilon >0$. It is based on a new implementation of the classic x-fast trie data structure of Willard [Inform. Process. Lett. 17(2), 1983] combined with a new dictionary data structure that supports fast parallel lookups.

In this talk, I present an algorithmic approach to co-designing TLB hardware and the paging mechanism to increase TLB reach without the fragmentation issues incurred by huge pages. Along the way, I’ll introduce a new hash-table design that overcomes existing tradeoffs, and achieves better performance than state-of-the-art hash tables both in theory and in practice. Key to these results are “tiny pointers,” an algorithmic technique for compressing pointers.

Sampling edges from a graph in sublinear time is a fundamental problem and a powerful subroutine for designing sublinear-time algorithms. Suppose we have access to the vertices of the graph and know a constant-factor approximation to the number of edges. An algorithm for pointwise $\epsilon$-approximate edge sampling with complexity $O(n/\sqrt{\epsilon m})$ has been given by Eden and Rosenbaum [SOSA 2018]. This has been later improved by Tětek and Thorup [STOC 2022] to $O(n\log ({\epsilon }^{-1})/\sqrt{m})$. At the same time, $\mathrm{\Omega }(n/\sqrt{m})$ time is necessary. We close the problem, by giving an algorithm with complexity $O(n/\sqrt{m})$ for the task of sampling an edge exactly uniformly.

We introduce 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--\delta$, then the optimal tiny-pointer size is $\mathrm{\Theta }(\log \log \log n+\log {\delta }^{-1})$ bits in the fixed-size case, and $\mathrm{\Theta }(\log {\delta }^{-1})$ expected bits in the variable-size case. Using tiny pointers, it is possible to improve succinctness bounds on a variety of classic data-structure problems.

We prove an $\mathrm{\Omega }(\log n\log \log n)$ lower bound for the span of implementing the $n$ input, $\log n$-depth FFT circuit (also known as butterfly network) in the nonatomic binary fork-join model. In this model, memory-access synchronizations occur only through fork operations, which spawn two child threads, and join operations, which resume a parent thread when its child threads terminate. Our bound is asymptotically tight for the nonatomic binary fork-join model, which has been of interest of late, due to its conceptual elegance and ability to capture asynchrony. Our bound implies super-logarithmic lower bound in the nonatomic binary fork-join model for implementing the butterfly merging networks used, e.g., in Batcher’s bitonic and odd-even mergesort networks. This lower bound also implies an asymptotic separation result for the atomic and nonatomic versions of the fork-join model, since, as we point out, FFT circuits can be implemented in the atomic binary fork-join model with span equal to their circuit depth.

The online list-labeling problem is a classical combinatorial problem 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. There has long existed a gap between the lower and upper bounds in the most algorithmically interesting part of the problem’s parameter space. We present our recent results, which narrow this gap for the first time in nearly 4 decades.

The linear-probing hash table is one of the oldest and most widely used data structures in computer science. However, linear probing also famously comes with a major drawback: 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 clustering phenomenon, which was first discovered by Donald Knuth in 1962, increases the expected time per insertion to $\mathrm{\Theta }(x^2)$ (rather than the more desirable $\mathrm{\Theta }(x)$) in a hash table that is a $1--1/x$ fraction full.

A natural question is whether one can somehow reduce clustering. In this paper, we establish an even stronger statement: the classical linear-probing hash table (even as it was first implemented in the 1950s) already has less clustering than the classical results would seem to suggest. As insertions and deletions are performed over time, the tombstones left behind by deletions cause the combinatorial structure of the hash table to stabilize in a way that eliminates clustering. This means that, for some versions of linear probing, the amortized expected time per operation is actually $\tilde{O}(x)$. We also present a new version of linear probing that avoids clustering entirely, achieving $O(x)$ expected time per operation.

Cardinality estimation is the task of approximating the number of distinct elements in a large dataset with possibly repeating elements. LogLog and HyperLogLog (c.f. Durand and Flajolet [ESA 2003], Flajolet et al. [Discrete Math Theor. 2007]) are small space sketching schemes for cardinality estimation, which have both strong theoretical guarantees of performance and are highly effective in practice. This makes them a highly popular solution with many implementations in big-data systems (e.g. Algebird, Apache DataSketches, BigQuery, Presto and Redis). However, despite having simple and elegant formulation, both the analysis of LogLog and HyperLogLog are extremely involved – spanning over tens of pages of analytic combinatorics and complex function analysis. We propose a modification to both LogLog and HyperLogLog that replaces discrete geometric distribution with the continuous Gumbel distribution. This leads to a very short, simple and elementary analysis of estimation guarantees, and smoother behavior of the estimator.

In recent years, there has been a growing interest in designing algorithms in models that capture different aspects of modern computational systems and big data processing. This talk focuses on graph algorithms in several such models, namely: distributed models, dynamic models, fault tolerant settings and the massively parallel computation model (MPC). Specifically, we focus on graph distance computation in these models. We study several graph theoretic structures that preserve approximate distances, but tradeoff this approximation factor with size, query time, or the number of hops on the approximate shortest paths. We then show how these combinatorial structures can be utilized for faster distance computation in distributed or dynamic settings. We conclude with applications in other related problems such as clustering and routing.

In this talk I’ll explain how to make algorithms for dynamic data sets out of distributed algorithms. The talk covers recent improvements on theory of algorithms for big data sets [Improved Dynamic Colouring of Sparse Graphs Aleksander B. G. Christiansen, Krzysztof D. Nowicki, Eva Rotenberg] and addresses some possible practical applications of presented approach [at Pathway.com].

Streaming algorithms and data structures often leverage randomness to lower their utilization of resources such as memory and computation. I will talk about the possible danger coming from the fact that estimates or replies provided by a randomized algorithm can leak information about its internal randomness. This information could be exploited via adaptive updates to break the guarantees of the algorithm that hold for any fixed sequences of updates with high probability.

Is their a way to make these types of randomized algorithms perform well even in the presence of adaptive updates? In this talk I will share both positive and negative news, ranging from simple techniques for moment estimation in the streaming model to a generic framework that shows that explicitly maintaining a collection of samples from nearly uniform distribution cannot be achieved with a small number of edits. This is a relatively new direction of research and many fundamental questions remain open.

Massively-parallel graph algorithms have received extensive attention over the past decade, with research focusing on three memory regimes: the superlinear regime, the near-linear regime, and the sublinear regime. The sublinear regime is the most desirable in practice, but conditional hardness results point towards its limitations. In this work we study a heterogeneous model, where the memory of the machines varies in size. We focus mostly on the heterogeneous setting created by adding a single near-linear machine to the sublinear MPC regime, and show that even a single large machine suffices to circumvent most of the conditional hardness results for the sublinear regime: for graphs with $n$ vertices and $m$ edges, we give (a) an MST algorithm that runs in $O(\log \log (m/n))$ rounds; (b) an algorithm that constructs an $O(k)$-spanner of size $O(n^{1+1/k})$ in $O(1)$ rounds; and (c) a maximal-matching algorithm that runs in $O(\sqrt{\log (m/n)}\log \log (m/n))$ rounds. We also observe that the best known near-linear MPC algorithms for several other graph problems which are conjectured to be hard in the sublinear regime (minimum cut, maximal independent set, and vertex coloring) can easily be transformed to work in the heterogeneous MPC model with a single near-linear machine, while retaining their original round complexity in the near-linear regime. If the large machine is allowed to have superlinear memory, all of the problems above can be solved in $O(1)$ rounds.

Modern hash table designs strive to minimize space while maxi- mizing speed. The most important factor in speed is the number of cache lines accessed during updates and queries. This is especially important on PMEM, which is slower than DRAM and in which writes are more expensive than reads. This paper proposes two stronger design objectives: stability and low-associativity. A stable hash table doesn’t 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 scaling and crash safety. We present IcebergHT, a fast, crash-safe, concurrent, and space-efficient hash table for PMEM based on the design principles of stability and low associativity. IcebergHTcombines 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, supports crash-safety, and has excellent performance on PMEM (where writes are particularly expensive). In our benchmarks, IcebergHT inserts are 50% to 3× faster than state-of-the-art PMEM hash tables Dash and CLHT and queries are 20% to $2\times$ faster. IcebergHT space overhead is 17%, whereas Dash and CLHT have space overheads of $2\times$ and $3\times$, respectively. IcebergHT also exhibits linear scaling and is crash safe. In DRAM, IcebergHT outperforms state-of-the-art hash tables libcuckoo and CLHT by almost $2\times$ on insertions while offering good query throughput and much better space efficiency.

This talk is about sublinear graph algorithms applied to the analysis of real-world graphs. We discuss a provable sublinear algorithms for estimating the degree distribution in sublinear time. To analyze this algorithm, we define fatness indices of the degree distribution. The running time of the algorithm is parameterized by these indices. The algorithm is also practical.

We discuss the overall challenge of designing practical sublinear graph algorithms.

I will discuss the notion of locality in the context of graph problems, from four different perspectives: online graph algorithms, dynamic graph algorithms, sequential distributed algorithms, and parallel distributed algorithms. I will use the graph coloring problem as a running example, and I will explore settings like this:

• $\mathrm{■}$

  Online graph algorithms: The adversary reveals the graph one node at a time. How far do you need to see around a node until it is safe to pick its color?

• $\mathrm{■}$

  Dynamic graph algorithms: The adversary constructs the graph one edge at a time, and you need to maintain a valid coloring after each addition. How far around the new edge do you need to modify the solution?

• $\mathrm{■}$

  Distributed graph algorithms: Each node has to choose its own color simultaneously in parallel based on its local neighborhood. How far does it need to see?

While these are different questions in general, we can show that there are families of graph problems for which all these notions are equal to each other.

Existing graph stream processing systems must store the graph explicitly in RAM which limits the scale of graphs they can process. The graph semi-streaming literature offers algorithms which avoid this limitation via linear sketching data structures that use small (sublinear) space, but these algorithms have not seen use in practice to date. In this talk I will explore what is needed to make graph sketching algorithms practically useful, and as a case study present a sketching algorithm for connected components and a corresponding high-performance implementation. Finally, I will give an overview of the many open problems in this area, focusing on improving query performance of graph sketching algorithms.

In this talk I discuss the ideas of incremental data processing, reactive algorithms, and their connections to dynamic algorithms, distributed algorithms, and big data processing.