Renfei Zhou

Yang Hu, William Kuszmaul, Jingxun Liang et al.

Quadratic probing is one of the most widely used open-addressing hash-table schemes in practice, but after more than half a century, even its most basic performance guarantees remain poorly understood. In this paper, we revisit quadratic probing through the lens of a smoothed variant in which each key follows a random probe sequence where its $k$th probe is expected at offset $Θ(k^2)$. This is simultaneously a toy model for better understanding regular quadratic probing and a natural hashing scheme in its own right. We analyse smoothed quadratic probing for both Robin Hood ordering and anti-Robin Hood ordering and reveal a surprising separation: At load factor $1-\varepsilon$, anti-Robin Hood achieves an expected query time of $Θ(\log \varepsilon^{-1})$, which matches the conjectured expected average successful query time for regular quadratic probing, while Robin Hood falls short at $Θ(\varepsilon^{-1/2})$. Our analysis generalises to degree-$d$ probing for any $d \ge 1$ with expected query time $O(\max(\log \varepsilon^{-1}, \varepsilon^{1-2/d}))$ for anti-Robin Hood and $Θ(\varepsilon^{-1/d})$ for Robin Hood. Finally, we go beyond smoothed analysis: using the probabilistic method, we show that for every $d \ge 2$, almost every random fixed-offset degree-$d$ probing sequence achieves expected query time $O(\log \varepsilon^{-1})$ under anti-Robin Hood ordering, simultaneously over all admissible table sizes and load factors. Thus, while quadratic probing itself remains elusive, we prove that essentially all quadratic-probing-like fixed-offset schemes achieve the ideal performance under the anti-Robin Hood ordering.

Michael A. Bender, Guy E. Blelloch, Martin Farach-Colton et al.

We study the problem of constructing concurrent objects in a setting where $P$ processes run in parallel and interact through a shared memory that is subject to write contention. Our goal is to transform hardware primitives that are subject to write contention into ones that handle contention gracefully. We give contention-resolution algorithms for several basic primitives, and analyze them under a relaxed, roughly-synchronous stochastic scheduler, where processes run at roughly the same rate up to a constant factor with high probability. Specifically, we construct read/write registers and CAS registers that have latency $O(\log P)$ w.h.p. under our scheduler model, using $O(1)$ hardware read/write registers and, in the case of our CAS construction, one hardware CAS register. Our algorithms guarantee performance even when their operations are invoked by an adaptive adversary that is able to see the entire history of operations so far, including their timing and return values. This allows them to be used as building blocks inside larger programs; using this compositionality property, we obtain several other constructions (LL/SC, fetch-and-increment, bounded max registers, and counters). To complement our constructions, we give a trade-off showing that even under a perfectly synchronous schedule and even if each process only executes one operation, any algorithm that implements any of the primitives that we consider, uses space $M$, and has latency at most $L$ with high probability must have expected latency at least $Ω(\log_{ML} P)$.

Yipeng Liu, Renfei Zhou, Jiaqi Yan et al.

Modern cloud data warehouses store data in micro-partitions and rely on metadata (e.g., zonemaps) for efficient data pruning during query processing. Maintaining data clustering in a large-scale table is crucial for effective data pruning. Existing automatic clustering approaches lack the flexibility required in dynamic cloud environments with continuous data ingestion and evolving workloads. This paper advocates a clean separation between reclustering policy and clustering-key selection. We introduce the concept of boundary micro-partitions that sit on the boundary of query ranges. We then present WAIR, a workload-aware algorithm to identify and recluster only boundary micro-partitions most critical for pruning efficiency. WAIR achieves near-optimal (with respect to fully sorted table layouts) query performance but incurs significantly lower reclustering cost with a theoretical upper bound. We further implement the algorithm into a prototype reclustering service and evaluate on standard benchmarks (TPC-H, DSB) and a real-world workload. Results show that WAIR improves query performance and reduces the overall cost compared to existing solutions.

William Kuszmaul, Aaron Putterman, Tingqiang Xu et al.

A dynamic retrieval data structure encodes a function $f:K \rightarrow [2^v]$ for a set $K \subseteq [U]$, while supporting queries $f(x)$ for $x\in K$, insertions \texttt{Insert}$(x, f(x))$ for $x \notin K$, and deletions \texttt{Delete}$(x)$ for $x \in K$. Given an upper bound $N$ on $|K|$, it is known how to solve the dynamic retrieval problem with $O(1)$-time operations and space $Nv + O(N \log \log (U/N))$ bits. An open question, first posed by Demaine et al. in 2006, is whether a similar bound can be achieved with a resizable data structure, whose space bound is parameterized by the \emph{current} size $n$ of $K$. We answer this question in the affirmative and prove matching lower bounds for the space-time trade-off achieved by our data structure. We also give corollaries for space-efficient memory allocation and dynamic filters.