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
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, 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
