Dynamic dictionaries for multisets and counting filters with constant time operations

DOI10.1007/s00453-022-01057-0OpenAlexW4311529954MaRDI QIDQ6103528

Guy Even, Unnamed Author

Publication date: 5 June 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-01057-0

zbMATH Keywords

data structuresdictionariesmembershipmultisetsapproximate membership

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A guided tour of Chernoff bounds
• On the construction of pseudorandom permutations: Luby-Rackoff revisited
• Space efficient hash tables with worst case constant access time
• Balanced allocation and dictionaries with tightly packed constant size bins
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Low Redundancy in Static Dictionaries with Constant Query Time
• De Dictionariis Dynamicis Pauco Spatio Utentibus
• De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
• Applications of a Splitting Trick
• Efficient Storage and Retrieval by Content and Address of Static Files
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Balls and bins: A study in negative dependence
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Compact dictionaries for variable-length keys and data with applications
• Exact and approximate membership testers
• An Improved Construction for Counting Bloom Filters
• Two-Way Chaining with Reassignment