Implicit O(1) Probe Search

DOI10.1137/0222001zbMATH Open0766.68017OpenAlexW2055034980MaRDI QIDQ4037679FDOQ4037679

Authors: Moni Naor, Amos Fiat 

Publication date: 16 May 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0222001

Recommendations

• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Two results on tables
• scientific article; zbMATH DE number 2086642
• On the cell probe complexity of membership and perfect hashing
• A tradeoff between search and update time for the implicit dictionary problem

zbMATH Keywords

Ramsey theoryperfect hashingspatial complexityrandomness in computations

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Searching and sorting (68P10)

Cited In (8)

• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Increasing the output length of zero-error dispersers
• Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs
• Representing graphs implicitly using almost optimal space
• Increasing the Output Length of Zero-Error Dispersers
• Dispersing Hash functions
• Tables should be sorted (on random access machines)
• Nearly Optimal Static Las Vegas Succinct Dictionary

This page was built for publication: Implicit $O(1)$ Probe Search

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