Implicit O(1) Probe Search

DOI10.1137/0222001MaRDI QIDQ4037679zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

perfect hashingRamsey theoryrandomness in computationsspatial complexity

Mathematics Subject Classification ID

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

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

Cited in

(8)

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

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)