Balanced allocation and dictionaries with tightly packed constant size bins

DOI10.1016/J.TCS.2007.02.054MaRDI QIDQ2373735zbMATH OpenOpenAlexFDO

Authors Martin Dietzfelbinger, Christoph Weidling

Publication date 16 July 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.02.054

zbMATH Keywords

data structuresrandomized algorithmsrandom graphsdictionarieshashingbalanced allocationstorage space

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Recommendations

• Automata, Languages and Programming
• Balanced allocations (extended abstract)
• Balanced Allocations
• Balanced allocation through random walk
• Consistent hashing with bounded loads

Cites work

• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A guided tour of Chernoff bounds
• Almost random graphs with simple hash functions
• Applications of a Splitting Trick
• Average-case analysis of algorithms for matchings and related problems
• Balanced Allocations
• Balanced allocations: the heavily loaded case
• Contention Resolution in Hashing Based Shared Memory Simulations
• Cuckoo hashing
• Efficient PRAM simulation on a distributed memory machine
• Efficient hashing with lookups in two memory accesses
• Fast concurrent access to parallel disks
• Fast priority queues for cached memory
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Paths in graphs
• Perfectly balanced allocation
• Space efficient hash tables with worst case constant access time
• Uniform hashing in constant time and linear space

Cited in

(28)

• Dynamic dictionaries for multisets and counting filters with constant time operations
• Generalized cuckoo hashing with a stash, revisited
• Layered hashing algorithm for real-time systems
• Two-way chaining for non-uniform distributions
• Adaptive Cuckoo Filters
• Dynamic space efficient hashing
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• Load thresholds for cuckoo hashing with double hashing
• Dynamic space efficient hashing
• Cuckoo hashing in cryptography: optimal parameters, robustness and applications
• Cuckoo commitments: registration-based encryption and key-value map commitments for large spaces
• Automata, Languages and Programming
• Consistent hashing with bounded loads
• Efficient hashing with lookups in two memory accesses
• Efficiently extendible mappings for balanced data distribution
• Sharp load thresholds for cuckoo hashing
• Hashing, load balancing and multiple choice
• Improved private set intersection for sets with small entries
• On the k-orientability of random graphs
• An improved version of cuckoo hashing: average case analysis of construction cost and search operations
• Hardness-preserving reductions via cuckoo hashing
• c-trie++: a dynamic trie tailored for fast prefix searches
• Dynamic dictionaries for multisets and counting filters with constant time operations
• Balanced allocation through random walk
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• scientific article; zbMATH DE number 7525475 (Why is no real title available?)
• scientific article; zbMATH DE number 7525476 (Why is no real title available?)
• scientific article; zbMATH DE number 7559133 (Why is no real title available?)

This page was built for publication: Balanced allocation and dictionaries with tightly packed constant size bins

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373735)