EUVIMEDEUVIMED entdecken
Crossref

Peeling Close to the Orientability Threshold Spatial Coupling in Hashing-Based Data Structures

Stefan Walzer

ACM Transactions on Algorithms · 31.07.2025 · 21 (3) · 1-23

DOI: 10.1145/3711822 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 28.07.2025. Verfasst von Stefan Walzer. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 69 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In multiple-choice data structures each element \(x\) in a set \(S\) of \(m\) keys is associated with a random set \(e(x) \subseteq [n]\) of buckets with capacity \(\ell\geq 1\) by hash functions. This setting is captured by the hypergraph \(H=([n],\{e(x)\mid x \in S\})\) . Accommodating each key in an associated bucket amounts to finding an \(\ell\) -orientation of \(H\) assigning to each hyperedge an incident vertex such that each vertex is assigned at most \(\ell\) hyperedges. If each subhypergraph of \(H\) has minimum degree at most \(\ell\) , then an \(\ell\) -orientation can be found greedily and \(H\) is called \(\ell\) -peelable . Peelability has a central role in invertible Bloom lookup tables and can speed up the construction of retrieval data structures, perfect hash functions, and cuckoo hash tables. Many hypergraphs exhibit sharp density thresholds with respect to \(\ell\) -orientability and \(\ell\) -peelability, i.e., as the density \(c=\frac{m}{n}\) grows past a critical value, the probability of these properties drops from almost \(1\) to almost \(0\) . In fully random \(k\) -uniform hypergraphs the thresholds \(c_{\smash{k,\ell}}^{*}\) for \(\ell\) -orientability significantly exceed the thresholds for \(\ell\) -peelability. In this article, for every \(k\geq 2\) and \(\ell\geq 1\) with \((k,\ell)\neq(2,1)\) and every \(z>0\) , we construct a new family of random \(k\) -uniform hypergraphs with i.i.d. random hyperedges such that both the \(\ell\) -peelability and the \(\ell\) -orientability thresholds approach \(c_{\smash{k,\ell}}^{*}\) as \(z \rightarrow \infty \) . In particular, we achieve \(1\) -peelability at densities arbitrarily close to \(1\) , extending the reach of greedy algorithms. Our construction is simple: The \(n\) vertices are linearly ordered and each hyperedge selects its \(k\) elements uniformly at random from a random range of \(\frac{n}{z+1}\) consecutive vertices. We thus exploit the phenomenon of threshold saturation via spatial coupling discovered in the context of low-density parity-check codes. Once the connection to data structures is in plain sight, a framework by Kudekar, Richardson and Urbanke does the heavy lifting in our proof. We demonstrate the usefulness of our construction using our hypergraphs as a drop-in replacement in a retrieval data structure by Botelho et al. This reduces memory usage from \(\approx 1.23m\) bits to \(\approx 1.12m\) bits (for input size \(m\) ). Using \(k>3\) attains, at small sacrifices in running time, further improvements to memory usage.

Zitieren

APA

Walzer, S. (2025). Peeling Close to the Orientability Threshold Spatial Coupling in Hashing-Based Data Structures. ACM Transactions on Algorithms, 21(3), 1-23. https://doi.org/10.1145/3711822

Vancouver

Walzer S. Peeling Close to the Orientability Threshold Spatial Coupling in Hashing-Based Data Structures. ACM Transactions on Algorithms. 2025;21(3):1-23. doi:10.1145/3711822

BibTeX
@article{Walzer2025,
  author = {Walzer, Stefan},
  title = {Peeling Close to the Orientability Threshold Spatial Coupling in Hashing-Based Data Structures},
  journal = {ACM Transactions on Algorithms},
  year = {2025},
  volume = {21},
  number = {3},
  pages = {1--23},
  doi = {10.1145/3711822}
}
Kostenlos starten →