Catalan Hashing: Efficient Linear Probing for Variable-Length Items
Alex Conway, Hanna Komlós, William Kuszmaul
AI 速览：提出 Catalan hashing，在存储任意长度元素的线性探测哈希表中，将扫描代价控制在接近单位长度情形的量级。
A defining feature of the linear-probing hash table is its spatial locality: at load factor $1 - \varepsilon$, the hash table can be implemented so that each operation scans a single contiguous region of expected size $O(1/\varepsilon)$ (this is known as the \emph{scan cost}). This guarantee, however, relies on all items having unit size. In this paper, we ask whether it is possible to achieve a similar guarantee, but in a hash table that stores items of arbitrary lengths $|x| \ge 1$. The main result of the paper is a new hash table called \emph{Catalan hashing}, which supports amortized expected scan cost $O(|x|/\varepsilon)$ for positive queries, $O(1/\varepsilon)$ for negative queries, and $O(|x|\varepsilon^{-1}\log^{1+δ}|x|)$ for insertions/deletions, for any constant $δ> 0$. As a corollary, we obtain the same bounds in the cache-oblivious model, with a scan cost of $S$ translating to $1 + O(S/B)$ I/Os. Along the way, we introduce several high-level techniques that may be of independent interest; this includes a novel way of using erasure codes in order to perform write optimization within a hash table, and a connection to scheduling that allows us to place elements in a way which avoids clustering at high load factors.
António Farinhas, Nuno M. Guerreiro, José Pombal, Pedro Henrique Martins, Laura Melton, Alex Conway, Cara Dochat, Maya D'Eon 等 9 位作者
Large language models are increasingly used for mental health support, yet their conversational coherence alone does not ensure clinical appropriateness. Existing general-purpose safeguards often fail to distinguish therapeutic disclosures from genuine clinical crises, and progress on developing better ones is bottlenecked by a lack of clinically grounded evaluation resources. To address this gap, we introduce a risk taxonomy, developed in collaboration with PhD-level clinical psychologists, that identifies actionable harm (self-harm and harm to others) while preserving space for safe, non-crisis therapeutic content. We release MindGuard-testset, a dataset of multi-turn conversations annotated at the turn level by clinical experts, which is, to our knowledge, the first public benchmark with turn-level clinical risk labels for multi-turn mental health support. We also release an automated red-teaming (ART) framework designed to measure how safety classifiers affect downstream model behavior in adversarial multi-turn interactions. Using synthetic dialogues generated via a controlled two-agent setup, we train MindGuard, a family of lightweight safety classifiers (with 4B and 8B parameters). Our classifiers reduce false positives at high-recall operating points and, when paired with clinician language models, help achieve lower attack success and harmful engagement rates compared to general-purpose safeguards. We release all models, training and human evaluation data, and the ART framework.
Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Ben Landrum, Christopher Musco, Yarin Shechter, Torsten Suel, Richard Wen
Graph-based nearest neighbor search methods, which run greedy search on a directed graph over the data points, have surged in popularity in recent years. A common goal is to construct a search graph with the $α$-navigability property, which ensures that greedy search returns provably good approximate nearest neighbors and converges in few iterations. Increasing $α\geq 1$ improves accuracy and convergence rate, but requires more edges, which increases both space and search time. This tradeoff has motivated the study of algorithms for constructing a sparsest $α$-navigable graph for a given set of points. For any point set and any distance function, we show how to compute an $α$-navigable graph with at most $O(\log n)$ times as many edges as the sparsest $(1+\varepsilon)α$-navigable graph, in $O(n^ω\log(Δ)/\varepsilon)$ time, where $ω< 2.372$ is the matrix multiplication exponent and $Δ$ is the aspect ratio of the input. This improves on Khanna, Padaki, and Waingarten (SODA 2026), who achieve the same runtime but are only competitive with the sparsest $2(1+\varepsilon)α$-navigable graph. Since sparsity often increases rapidly with $α$ (typically $α\leq 1.1$), their bound can be significantly weaker. Previously, the best algorithm competing with the sparsest $(1+\varepsilon)α$-navigable graph required $\widetilde{O}(n^{2.5})$ time. Our techniques also extend to constructing sparse $τ$-monotonic graphs, another popular target in nearest neighbor search. Finally, we give a fine-grained complexity analysis suggesting that improving the $O(n^ω)$ running time is unlikely, or would require a very different approach. It is based on hardness results for problems related to verifying whether a graph is navigable, a topic of independent interest.