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

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)

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
• 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)