Results 11 to 20 of about 569,401 (216)
Fast and scalable minimal perfect hashing for massive key sets [PDF]
arXiv, 2017 Minimal perfect hash functions provide space-efficient and collision-free hashing on static sets. Existing algorithms and implementations that build such functions have practical limitations on the number of input elements they can process, due to high construction time, RAM or external memory usage.
Chikhi, Rayan +3 more
arxiv +6 more sources
Linear time Constructions of some $d$-Restriction Problems [PDF]
arXiv, 2014 We give new linear time globally explicit constructions for perfect hash families, cover-free families and separating hash functions.
Bshouty, Nader H.
arxiv +4 more sources
Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence [PDF]
arXiv, 2015 Randomized algorithms and data structures are often analyzed under the assumption of access to a perfect source of randomness. The most fundamental metric used to measure how "random" a hash function or a random number generator is, is its independence: a sequence of random variables is said to be $k$-independent if every variable is uniform and every ...
A. Siegel +7 more
arxiv +4 more sources
Minimal perfect hash functions made simple [PDF]
Communications of the ACM, 1980 A method is presented for computing machine independent, minimal perfect hash functions of the form: hash value ← key length + the associated value of the key's first character + the associated value of the key's last character. Such functions allow single probe retrieval from minimally sized tables of identifier lists.
Richard J. Cichelli
openalex +3 more sources
Perfect Hash Function Generation on the GPU with RecSplit [PDF]
, 2022 Minimale perfekte Hashfunktionen (MPHFs) bilden eine statische Menge S von beliebigen Schlüsseln auf die Menge der ersten |S| natürlichen Zahlen bijektiv ab, d. h., jeder Hashwert wird exakt einmal verwendet. Sie sind in vielen Anwendungen hilfreich, zum
Bez, Dominik
core +4 more sources
An undergraduate project to compute minimal perfect hashing functions [PDF]
ACM SIGCSE Bulletin, 1992 Some heuristics for computing the character weights in a Cichelli-style, minimal perfect hashing function are given. These ideas should perform best when applied to relatively small, static sets of character strings and they can be used as the foundation for a large programming assignment.
John A. Trono
openalex +3 more sources
A polynomial time generator for minimal perfect hash functions [PDF]
Communications of the ACM, 1985 A perfect hash function PHF is an injection F from a set W of M objects into the set consisting of the first N nonnegative integers where N ⩾ M. If N = M, then F is a minimal perfect hash function, MPHF. PHFs are useful for the compact storage and fast retrieval of frequently used objects such as reserved words in a programming language or commonly ...
Thomas J. Sager
openalex +3 more sources
Practical minimal perfect hash functions for large databases [PDF]
Communications of the ACM, 1992 We describe the first practical algorithms for finding minimal perfect hash functions that have been used to access very large databases (i.e., having over 1 million keys). This method extends earlier work wherein an 0(n-cubed) algorithm was devised, building upon prior work by Sager that described an 0(n-to the fourth) algorithm.
Edward A. Fox +3 more
openalex +3 more sources
Parallel and External-Memory Construction of Minimal Perfect Hash Functions With PTHash [PDF]
IEEE Transactions on Knowledge and Data Engineering, 2023 Accepted by IEEE ...
Giulio Ermanno Pibiri, Roberto Trani
openalex +6 more sources
Perfect hashing functions [PDF]
Communications of the ACM, 1977 A refinement of hashing which allows retrieval of an item in a static table with a single probe is considered. Given a set I of identifiers, two methods are presented for building, in a mechanical way, perfect hashing functions, i.e. functions transforming the elements of I into unique addresses.
Renzo Sprugnoli
openalex +3 more sources