Dynamic Perfect Hashing: Upper and Lower Bounds
From MaRDI portal
Publication:4305355
DOI10.1137/S0097539791194094zbMath0820.68038OpenAlexW2077229436WikidataQ55878437 ScholiaQ55878437MaRDI QIDQ4305355
Hans Rohnert, Anna R. Karlin, Martin Dietzfelbinger, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Robert Endre Tarjan
Publication date: 17 October 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539791194094
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Parallel algorithms in computer science (68W10) Data structures (68P05)
Related Items (51)
An old sub-quadratic algorithm for finding extremal sets ⋮ Recognizing Hamming graphs in linear time and space ⋮ Order-preserving indexing ⋮ Stochastic analysis of dynamic processes ⋮ Two- and three- dimensional point location in rectangular subdivisions ⋮ Lower bounds for dynamic algorithms ⋮ Adjacency queries in dynamic sparse graphs ⋮ Hyper-minimisation Made Efficient ⋮ A construction method for optimally universal hash families and its consequences for the existence of RBIBDs ⋮ Exploiting storage redundancy to speed up randomized shared memory simulations ⋮ Simulating shared memory in real time: On the computation power of reconfigurable architectures ⋮ Fast structural alignment of biomolecules using a hash table, n-grams and string descriptors ⋮ On the succinct representation of equivalence classes ⋮ Validating the Knuth-Morris-Pratt failure function, fast and online ⋮ CuCoTrack: cuckoo filter based connection tracking ⋮ Flash memory efficient LTL model checking ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ The nearest colored node in a tree ⋮ On-line graph algorithms for incremental compilation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Simple fast parallel hashing ⋮ Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion ⋮ A simple sub-quadratic algorithm for computing the subset partial order ⋮ Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem ⋮ Maintaining dynamic sequences under equality tests in polylogarithmic time ⋮ Fast computation of abelian runs ⋮ Polynomial-time compression ⋮ ON THE PERFORMANCE AND COST OF SOME PRAM MODELS ON CMP HARDWARE ⋮ Dynamic space efficient hashing ⋮ Fast local searches and updates in bounded universes ⋮ UNWEIGHTED AND WEIGHTED HYPER-MINIMIZATION ⋮ Clocked adversaries for hashing ⋮ Two-dimensional packet classification and filter conflict resolution in the internet ⋮ Predecessor on the Ultra-Wide Word RAM ⋮ Online algorithms on antipowers and antiperiods ⋮ Polynomial hash functions are reliable ⋮ Fast incremental planarity testing ⋮ Cuckoo hashing: Further analysis ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ A Space-Optimal Grammar Compression. ⋮ Min-wise independent permutations ⋮ Dynamic Space Efficient Hashing. ⋮ Contracting a Planar Graph Efficiently ⋮ Succinct representation for (non)deterministic finite automata ⋮ Union and split operations on dynamic trapezoidal maps ⋮ TYPE INFERENCE FOR FIRST-CLASS MESSAGES WITH FEATURE CONSTRAINTS ⋮ Two-way chaining for non-uniform distributions ⋮ Lower bounds for encrypted multi-maps and searchable encryption in the leakage cell probe model ⋮ Optimal bounds for the predecessor problem and related problems ⋮ Authenticated hash tables based on cryptographic accumulators
This page was built for publication: Dynamic Perfect Hashing: Upper and Lower Bounds
