On the cell probe complexity of membership and perfect hashing

DOI10.1145/380752.380836zbMath1323.68318OpenAlexW2078726861MaRDI QIDQ5175998

Rasmus Pagh

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380836

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (6)

Nearly Optimal Static Las Vegas Succinct Dictionary ⋮ Determining membership with 2 simultaneous queries ⋮ Pseudo-random graphs and bit probe schemes with one-sided error ⋮ Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes ⋮ On the \(k\)-orientability of random graphs ⋮ A Survey of Data Structures in the Bitprobe Model

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: On the cell probe complexity of membership and perfect hashing