Zobrazeno 1 - 10
of 3 520
pro vyhledávání: '"perfect hashing"'
A minimal perfect hash function (MPHF) maps a set of n keys to {1, ..., n} without collisions. Such functions find widespread application e.g. in bioinformatics and databases. In this paper we revisit PTHash - a construction technique particularly de
Externí odkaz:
http://arxiv.org/abs/2404.18497
In this work, we provide an upper bound for global certification of graph homomorphism, a generalization of graph coloring. In certification, the nodes of a network should decide if the network satisfies a given property, thanks to small pieces of in
Externí odkaz:
http://arxiv.org/abs/2402.03849
Autor:
Kosolobov, Dmitry
Given an increasing sequence of integers $x_1,\ldots,x_n$ from a universe $\{0,\ldots,u-1\}$, the monotone minimal perfect hash function (MMPHF) for this sequence is a data structure that answers the following rank queries: $rank(x) = i$ if $x = x_i$
Externí odkaz:
http://arxiv.org/abs/2403.07760
A minimal perfect hash function (MPHF) maps a set S of n keys to the first n integers without collisions. There is a lower bound of n*log(e)=1.44n bits needed to represent an MPHF. This can be reached by a brute-force algorithm that tries e^n hash fu
Externí odkaz:
http://arxiv.org/abs/2310.14959
A minimal perfect hash function (MPHF) maps a set $S$ of $n$ keys to the first $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 matching upper bound is obtained using the bru
Externí odkaz:
http://arxiv.org/abs/2308.09561
A Monotone Minimal Perfect Hash Function (MMPHF) constructed on a set S of keys is a function that maps each key in S to its rank. On keys not in S, the function returns an arbitrary value. Applications range from databases, search engines, data encr
Externí odkaz:
http://arxiv.org/abs/2304.11012
Minimal perfect hashing is the problem of mapping a static set of $n$ distinct keys into the address space $\{1,\ldots,n\}$ bijectively. It is well-known that $n\log_2(e)$ bits are necessary to specify a minimal perfect hash function (MPHF) $f$, when
Externí odkaz:
http://arxiv.org/abs/2210.13097
A Perfect Hash Function (PHF) is a hash function that has no collisions on a given input set. PHFs can be used for space efficient storage of data in an array, or for determining a compact representative of each object in the set. In this paper, we p
Externí odkaz:
http://arxiv.org/abs/2210.01560
The monotone minimal perfect hash function (MMPHF) problem is the following indexing problem. Given a set $S= \{s_1,\ldots,s_n\}$ of $n$ distinct keys from a universe $U$ of size $u$, create a data structure $DS$ that answers the following query: \[
Externí odkaz:
http://arxiv.org/abs/2207.10556
Autor:
Domnita, Dan, Oprisa, Ciprian
The problem of fast items retrieval from a fixed collection is often encountered in most computer science areas, from operating system components to databases and user interfaces. We present an approach based on hash tables that focuses on both minim
Externí odkaz:
http://arxiv.org/abs/2007.08311