English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A minimal perfect hash function (MPHF) maps a set $S$ of $n$ keys to thefirst $n$ integers without collisions. There is a lower bound of$n\log_2e-O(\log n)$ bits of space needed to represent an MPHF. A matchingupper bound is obtained using the brute-force algorithm that tries random hashfunctions until stumbling on an MPHF and stores that function's seed. Inexpectation, $e^n\textrm{poly}(n)$ seeds need to be tested. The mostspace-efficient previous algorithms for constructing MPHFs all use such abrute-force approach as a basic building block.  In this paper, we introduce ShockHash - Small, heavily overloaded cuckoo hashtables. ShockHash uses two hash functions $h_0$ and $h_1$, hoping for theexistence of a function $f : S \rightarrow \{0,1\}$ such that $x \mapstoh_{f(x)}(x)$ is an MPHF on $S$. In graph terminology, ShockHash generates$n$-edge random graphs until stumbling on a pseudoforest - a graph where eachcomponent contains as many edges as nodes. Using cuckoo hashing, ShockHash thenderives an MPHF from the pseudoforest in linear time. It uses a 1-bit retrievaldata structure to store $f$ using $n + o(n)$ bits.  By carefully analyzing the probability that a random graph is a pseudoforest,we show that ShockHash needs to try only $(e/2)^n\textrm{poly}(n)$ hashfunction seeds in expectation, reducing the space for storing the seed byroughly $n$ bits. This makes ShockHash almost a factor $2^n$ faster thanbrute-force, while maintaining the asymptotically optimal space consumption. Animplementation within the RecSplit framework yields the currently most spaceefficient MPHFs, i.e., competing approaches need about two orders of magnitudemore work to achieve the same space.

ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force