Scalable Data Structures

Differential privacy is the gold standard for rigorous data privacy guarantees where the traditional central model assumes a trusted curator who takes private input and outputs privatized answers to user queries. However, one major assumption in this model is that the trusted curator always keeps the input private. Unfortunately, such a strong notion of trust is too ideal in today’s world where massive data leaks occur. Thus, in this talk, I’ll discuss private graph algorithms in the local model, where nodes trust no one with their private information. One major issue in the local privacy model for graphs is scalability. Scalability is often an issue for graph algorithms in the local privacy model because many techniques for making graph algorithms private change the density of the input graph (i.e. making the graph much denser than it was previously). I’ll present the first local edge differentially private (LEDP) algorithms for k-core decomposition, low out-degree ordering, and densest subgraph. Furthermore, our algorithms are scalable and can be implemented in distributed and parallel models without the issue of changing graph density. Our algorithm’s approximation factor matches that of the currently best non-private distributed algorithm for k-core decomposition with only an $\mathrm{poly}(\log n)/ϵ$ additive error. I’ll conclude with a discussion of some open questions and potential future work.

This paper studies parallel algorithms for the longest increasing subsequence (LIS) problem. Let $n$ be the input size and $k$ be the LIS length of the input. Sequentially, LIS is a simple problem that can be solved using dynamic programming (DP) in $O(n\log n)$ work. However, parallelizing LIS is a long-standing challenge. We are unaware of any parallel LIS algorithm that has optimal $O(n\log n)$ work and non-trivial parallelism (i.e., $\tilde{O}(k)$ or $o(n)$ span). This paper proposes a parallel LIS algorithm that costs $O(n\log k)$ work, $\tilde{O}(k)$ span, and $O(n)$ space, and is much simpler than the previous parallel LIS algorithms. We also generalize the algorithm to a weighted version of LIS, which maximizes the weighted sum for all objects in an increasing subsequence. To achieve a better work bound for the weighted LIS algorithm, we designed parallel algorithms for the van Emde Boas (vEB) tree, which has the same structure as the sequential vEB tree, and supports work-efficient parallel batch insertion, deletion, and range queries.

We also implemented our parallel LIS algorithms. Our implementation is light-weighted, efficient, and scalable.

We report experimental results for a Quicksort variant based on Lomuto’s partitioning suggested by Andrei Alexandrescu. This variant eliminates branches inside the main loop of the partitioning process for the price of an increased number of overall executed instructions. However, the resulting reduction of mispredicted branches gives rise to a heavily used pipeline. As a consequence, the resulting Quicksort implementation runs faster than one using Hoare/Sedgewick partitioning. Our adaptations of the latter to different branch free versions imply a similar overhead of instructions and a comparable reduction of branch misses. However, the speedup observed due to improved pipelining is way smaller than for the Lomuto variant and results in an overall worse runtime. So far we have no explanation for this.

We present Sliding Block Hashing (Slick) a simple hash table data structure that combines high performance with very good space efficiency.

A growing line of work shows how learned predictions can be used to break through worst-cast barriers to improve the running time of an algorithm. However, incorporating predictions into data structures with strong theoretical guarantees remains underdeveloped. This work takes a step in this direction by showing that predictions can be leveraged in the fundamental online list labeling problem. In the problem, n items arrive over time and must be stored in sorted order in an array of size $\mathrm{\Theta }(n)$. The array slot of an element is its label and the goal is to maintain sorted order while minimizing the total number of elements moved (i.e., relabeled). We present a new list labeling data structure and bound its performance in two models. In the worst-case learning-augmented model, we give guarantees in terms of the error in the predictions. Our data structure provides strong theoretical guarantees— it is optimal for any prediction error and guarantees the best-known worst-case bound even when the predictions are entirely erroneous. We also consider a stochastic error model and bound the performance in terms of the expectation and variance of the error. Finally, the theoretical results are demonstrated empirically. In particular, we show that our data structure performs well on numerous real datasets, including temporal data sets where predictions are constructed from elements that arrived in the past (as is typically done in a practical use case).

We present a hash table that achieves nearly the state of the art but requires only basic analytical techniques. The aim is to present an algorithm that can be taught to graduate students (or perhaps advanced undergrads).

We describe data structures and data-management algorithms for monitoring cyber streams. We wish to identify specific patterns that arrive slowly over time, hidden among high-speed streams of normal traffic. The key piece of the Firehose benchmark that models this application is a variant of the heavy-hitters problem: report a key after it has been seen a specific constant number of times. To solve this without false negatives requires $\mathrm{\Omega }(N)$ space for partial-pattern storage for a stream of size $N$. We give write-optimized external-memory algorithms to accurately monitor high-speed streams with provable tunable trade-off between reporting delay and I/O overhead. Our experimental results show that a multithreaded version of our algorithm has throughput comparable to an engineered in-RAM reference implementation, but our method reports all reportable keys, while the in-RAM method can miss almost all reports for sufficiently large key space. We describe extensions to unending streams.

This talk covers Search-optimized Packed Memory Arrays (SPMAs), a collection of data structures based on Packed Memory Arrays (PMAs) that address suboptimal search via cache-optimized search layouts. Traditionally, PMAs and B-trees have tradeoffs between searches/inserts and scans: B-trees were faster for searches and inserts, while PMAs were faster for scans. Our empirical evaluation shows that SPMAs overcome this tradeoff for unsorted input distributions: on average, SPMAs are faster than B+-trees (a variant of B-trees optimized for scans) on all major operations.

I gave a presentation on two topics:

1. 1.

   How to use an L1 IPM to turn the task of solving an LP into a sequence data structure queries, and how this can be applied to solve minimum-cost flow problems via min-ratio cycle updates.

2. 2.

   How to design dynamic spanners that allow for edge insertions and deletions and vertex splits.

The dynamic connectivity problem is to process an online sequence of edge insertions and deletions in a graph while answering connectivity queries. Here we simplify and parallelize the sequential Monte Carlo algorithms of King et al. as improved by Wang for dynamic connectivity, which requires polylogarithmic time per update and per query in the worst-case. Our simplification adds no cost to the asymptotic sequential running time. It enables us to rely strictly on ET-trees, rather than more complicated path compression data structures, making it simpler to perform batch-parallel updates.

The arboricity $\alpha$ of a graph is the number of forests it takes to cover all its edges. Being asymptotically related to the graph’s degeneracy and maximal subgraph density, arboricity is considered a good measure of the sparsity of a graph. Natural computational questions about arboricity include: computing the arboricity, obtaining a decomposition of the edges into few forests, and orienting the edges so that each vertex has only close to $\alpha$ out-edges.

In this talk, we will address these questions in the dynamic setting, in which the graph is subject to arbitrary, adversarial insertions and deletions of edges. We will see how maintaining an orientation with few out-edges from each vertex leads to efficient dynamic algorithms for matching, colouring, and decomposing into $O(\alpha )$ forests; And we will see how to efficiently balance the number of out-edges in an orientation of the dynamic graph, via an almost local reconciliation between neighbouring vertices.

A Dyck sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The Dyck edit distance of a given sequence of parentheses $S$ is the smallest number of edit operations (insertions, deletions, and substitutions) needed to transform $S$ into a Dyck sequence. We consider the threshold Dyck edit distance problem, where the input is a sequence of parentheses $S$ and a positive integer $k$, and the goal is to compute the Dyck edit distance of $S$ only if the distance is at most $k$, and otherwise report that the distance is larger than $k$. Backurs and Onak [PODS’16] showed that the threshold Dyck edit distance problem can be solved in $O(n+k^{16})$ time. In this work, we design new algorithms for the threshold Dyck edit distance problem which costs $O(n+k^{4.782036})$ time with high probability or $O(n+k^{4.853059})$ deterministically. Our algorithms combine several new structural properties of the Dyck edit distance problem, a refined algorithm for fast (min, +) matrix product, and a careful modification of ideas used in Valiant’s parsing algorithm.

The heap, or priority queue data structure supports fast access to the smallest of a set of items subject to insertions, deletions, and decreases in value. We describe recent results giving tight and almost-tight amortized efficiency bounds for three self-adjusting heap implementations, the slim heap, the smooth heap, and the multipass pairing heap.

The talk is about recent advancements in the design of dictionaries and other related data structures. A dynamic dictionary is a data structure that maintains sets under insertions and deletions and supports membership queries of the form “is an element x in the set or not?”. A related problem is that of maintaining a perfect hash function over the set, in which the data structure assigns a unique hashcode to each element in the set (but does not need to support membership queries). We specifically focus on showing a perfect hashing data structure whose space is proportional to the cardinality of the set at all points in time and whose hashcodes are stable in the incremental setting (i.e., when only insertions are allowed, the hashcode of an element does not change while the element is in the set). This is joint work with Guy Even, based on our STOC 2022 paper.

In this talk we will briefly review the models of computation used for designing algorithms on GPUs. We will also discuss recent algorithmic results on how to avoid bank conflicts when designing algorithms for GPUs.

A regular expression specifies a set of strings formed by single characters combined with concatenation, union, and Kleene star operators. Given a regular expression $R$ and a string $Q$, the regular expression matching problem is to decide if $Q$ matches any of the strings specified by $R$. Regular expressions are a fundamental concept in formal languages and regular expression matching is a basic primitive for searching and processing data. A standard textbook solution [Thompson, CACM 1968] constructs and simulates a nondeterministic finite automaton, leading to an $O(nm)$ time algorithm, where $n$ is the length of $Q$ and $m$ is the length of $R$. Despite considerable research efforts only polylogarithmic improvements of this bound are known. Recently, conditional lower bounds provided evidence for this lack of progress when Backurs and Indyk [FOCS 2016] proved that, assuming the strong exponential time hypothesis (SETH), regular expression matching cannot be solved in $O({(nm)}^{1-ϵ})$, for any constant $ϵ>0$. Hence, the complexity of regular expression matching is essentially settled in terms of $n$ and $m$.

In this paper, we take a new approach and go beyond worst-case analysis in $n$ and $m$. We introduce a density parameter, $\mathrm{\Delta }$, that captures the amount of nondeterminism in the NFA simulation on $Q$. The density is at most $nm+1$ but can be significantly smaller. Our main result is a new algorithm that solves regular expression matching in

time.

This essentially replaces $nm$ with $\mathrm{\Delta }$ in the complexity of regular expression matching. We complement our upper bound by a matching conditional lower bound that proves that we cannot solve regular expression matching in time $O({\mathrm{\Delta }}^{1-ϵ})$ for any constant $ϵ>0$ assuming SETH.

An $n$-permutation $S$ “avoids” a $k$-permutation $\pi$ if there are no $k$ indices such that iff . Chalermsook et al. (2015) and Kozma and Saranurak (2019) presented two algorithms for sorting such permutations in $O(n\cdot 2^{{(\alpha (n))}^{3k/2}})$ time. Their upper bound was derived by transcribing the behavior of the algorithm as an $n\times n$ 0-1 matrix and proving that this matrix avoids a certain pattern, which is the Kronecker product of a permutation (encoding $\pi$) and a “hat” pattern. In this talk I prove that both of these algorithms actually run in $O(n\cdot 2^{(1+o(1))\alpha (n)})$ time, by bounding the extremal function of all such patterns. I also show that this bound is essentially tight, and that most such patterns have an extremal function that is $\mathrm{\Omega }(n\cdot 2^{\alpha (n)})$.

Filters, such as Bloom, quotient, cuckoo, xor, and ribbon filters, are space-efficient, lossy representations of sets. They have become widely used in systems and extensively researched by data structures designers. In this talk, we argue that most applications would be better served by maplets, i.e. space efficient, lossy maps, rather than filters. We explain how to generalize the filter notion of lossiness to maps, show how several classic filter applications can be dramatically improved by using maplets, and show how to construct maplets straightforwardly from many of today’s filters.

Given two planar (straight-line) drawings of a planar graph, can one drawing be transformed to the other in a little number of steps, where during each step every vertex moves along a straight line segment with a uniform speed? It is crucially required that there is no crossing between any elements of a drawing at any moment. Such transformation is called a morph. If the drawings are topologically equivalent, then a 2D morph is always possible in $O(n)$ steps, and sometimes a linear number of steps is necessary [1]. Allowing intermediate drawings to lie in 3D reduces the upper bound on the number of steps to $O(\log n)$ for trees [2], and lifts the topologically equivalent requirement for arbitrary graphs, however at a cost of quadratic number of steps [3]. No non-trivial lower bound for this setting is known. During the seminar I proposed a query variant of the graph morphing problem, and jointly with Eunjin Oh we obtained the first result in this direction:

A planar drawing Gamma of an n-vertex graph G can be preprocessed in $O(n^{5/3}{\log }^{2}n)$ expected time and $O(n\log n)$ space for the following queries: given a vertex $v$ of $G$, and a point t in $R^2$, can $v$ be moved from its position in Gamma to the point t, such that the morph is non-crossing?

After the above preprocessing, this query can be answered in $O(\log m{\log }^{2}n)$ time, when m is the degree of vertex $v$. We hope to further improve this runtime and generalise our data structure to availability region queries, updates and 3D morphs.

This result is a joint work during the seminar with its participant Eunjin Oh.

We examine the well-known problem of determining whether some value occurs in the majority of positions in an array. The twist is that in the past comparisons have been $(=,\ne )$, while here we focus on a three way outcome . We show, that like the $(=,\ne )$ version, $3n/2-o(1)$ comparisons are necessary (and sufficient) in the worst case, but give a Las Vegas algorithm requiring an expected $n+o(1)$ comparisons and $n-o(n)$ lower bound, in contrast with a $1.059\mathrm{\dots }n$ lower bound for the $(=,\ne )$ version.

Given a planar graph $G$ with $n$ vertices and a set $T=\{(s_1,t_1),\mathrm{\dots },(s_k,t_k)\}$ of $k$ terminal pairs, the disjoint paths problem asks for computing a set of vertex disjoint paths $P_1,\mathrm{\dots },P_k$ such that $P_i$ connects $s_i$ and $t_i$. In this talk, I will introduce a $2^{O(k^2)}n$-time algorithm for the planar disjoint paths problem. This improves the previously best-known algorithm with running times of $2^{O(k^2)}{n}^6$ and $2^{2^{O(k)}}n$.

Processing-In-Memory (PIM) is a hardware architecture that allows reducing the memory bottleneck: while data are sent from the memory to the CPU in the traditional memory hierarchy, in a PIM architecture the computation is sent to the memory. The main idea is to add a small computing unit within each memory module: this is an almost 40-year-old theoretical idea; however, only recently PIM architectures have been successfully implemented and commercialized (e.g., by UPMEM). In this talk, we will see a computational model for designing efficient algorithms that fully exploit PIMs, and introduce PIM algorithms for binary search and triangle counting.

We address two open problems in sorting with priced information, introduced by [Charikar, Fagin, Guruswami, Kleinberg, Raghavan, Sahai (CFGKRS), STOC 2000]. In this setting, different comparisons have different (potentially infinite) costs. The goal is to find a sorting algorithm with small competitive ratio, defined as the (worst-case) ratio of the algorithm’s cost to the cost of the cheapest proof of the sorted order.

1) When all costs are in $\{0,1,n,\mathrm{\infty }\}$, we give an algorithm that has $\tilde{O}(n^{3/4})$ competitive ratio. Our result refutes the hypothesis that a widely cited $\mathrm{\Omega }(n)$ lower bound on the competitive ratio for finding the maximum extends to sorting. This lower bound by [Gupta, Kumar, FOCS 2000] uses costs in $\{0,1,n,\mathrm{\infty }\}$ and was claimed as the reason why sorting with arbitrary costs seemed bleak and hopeless. Our algorithm also generalizes the algorithms for generalized sorting (all costs in $\{1,\mathrm{\infty }\}$), a version initiated by [Huang, Kannan, Khanna, FOCS 2011] and addressed recently by [Kuszmaul, Narayanan, FOCS 2021].

2) We answer the problem of bichromatic sorting posed by [CFGKRS]: We are given two sets $A$ and $B$ of total size $n$, and the cost of an $A-A$ comparison or a $B-B$ comparison is higher than an $A-B$ comparison. The goal is to sort $A\cup B$. An $\mathrm{\Omega }(\log n)$ lower bound on competitive ratio follows from unit-cost sorting. We give a randomized algorithm with an almost-optimal w.h.p. competitive ratio of $O({\log }^{3}n)$.

We also study generalizations of the problem universal sorting and bipartite sorting (a generalization of nuts-and-bolts). Here, we define a notion of instance optimality, and develop an algorithm for bipartite sorting which is $O({\log }^{3}n)$ instance-optimal. Our framework of instance optimality applies to other static problems and may be of independent interest.

The online list labeling problem is a basic primitive in data structures. The goal is to store a dynamically-changing set of n items in an array of m slots, while keeping the elements in sorted order. To do so, some items may need to be moved over time, and the goal is to minimize the number of items moved per insertion/deletion. When $m=Cn$ for some constant $C>1$, an upper bound of $O({\log }^{2}n)$ items moved per insertion/deletion has been known since 1981. There is a matching lower bound for deterministic algorithms, but for randomized algorithms, the best known lower bound is $\mathrm{\Omega }(\log n)$, leaving a gap between upper and lower bounds. We improve the upper bound, providing a randomized data structure with expected $O({\log }^{3/2}n)$ items moved per insertion/deletion.

We present two dynamic data-structures in the word RAM model. The first data structure is a filter that supports approximate membership queries that is characterized by the following properties:

1. 1.

   Dynamic: supports insert, delete, and membership-query operations.

2. 2.

   Can store a dataset of cardinality at most $n$ (insertions may fail with probability $o(1/\mathrm{poly}(n))$).

3. 3.

   Adjustable false-positive probability $\epsilon$, provided that $\epsilon =\mathrm{\Omega }(1/(\mathrm{polylog}n))$.

4. 4.

   Space-efficient: $(1+o(1))\cdot n{\log }_2(1/ϵ)+O(n)$ bits.

5. 5.

   Worst case constant time for every operation.

6. 6.

   Single memory access per operation (not including hash function evaluation).

The second data structure is a retrieval data structure that supports value queries and is characterized by the following properties:

1. 1.

   Supports the following operations: insert key-value pairs, delete a key, and query the value of a key.

2. 2.

   Can store a set of at most $n$ key-value pairs (insertions may fail with probability $1/\mathrm{poly}(n)$).

3. 3.

   Values are binary strings of length $O(\log \log n)$ bits.

4. 4.

   Space-compact: $O(n\log \log n)$ bits.

5. 5.

   Worst case constant time for every operation.

6. 6.

   The expected number of memory accesses per operation is $1+1/\mathrm{polylog}(n)$ (not including hash function evaluation).

The retrieval data structure has an additional “false-positive” feature: the response to a query for a key not in the dataset is $\mathrm{NULL}$ with probability at least $1-1/\mathrm{polylog}(n)$.

We give new polynomial lower bounds for a number of dynamic measure problems in computational geometry. These lower bounds hold in the Word-RAM model, conditioned on the hardness of either 3SUM, APSP, or the Online Matrix-Vector Multiplication problem [Henzinger et al., STOC 2015]. In particular we get lower bounds in the incremental and fully-dynamic settings for counting maximal or extremal points in ${ℝ}^3$, different variants of Klee’s Measure Problem, problems related to finding the largest empty disk in a set of points, and querying the size of the i’th convex layer in a planar set of points. We also answer a question of Chan et al. [SODA 2022] by giving a conditional lower bound for dynamic approximate square set cover. While many conditional lower bounds for dynamic data structures have been proven since the seminal work of Patrascu [STOC 2010], few of them relate to computational geometry problems. This is the first paper focusing on this topic. Most problems we consider can be solved in $O(n\log n)$ time in the static case and their dynamic versions have only been approached from the perspective of improving known upper bounds. One exception to this is Klee’s measure problem in ${ℝ}^2$, for which Chan [CGTA 2010] gave an unconditional $\mathrm{\Omega }(\sqrt{n})$ lower bound on the worst-case update time. By a similar approach, we show that such a lower bound also holds for an important special case of Klee’s measure problem in ${ℝ}^3$ known as the Hypervolume Indicator problem, even for amortized runtime in the incremental setting.