The Spatial Complexity of Oblivious k-Probe Hash Functions

DOI10.1137/0219054MaRDI QIDQ3495640zbMATH OpenOpenAlexFDO

Authors Jeanette P. Schmidt, Alan Siegel

Publication date 1990

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

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

zbMATH Keywords

hash functionsperfect hashingspatial complexitypower bound

Mathematics Subject Classification ID

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

Recommendations

• Nonoblivious hashing
• On the \(k\)-independence required by linear probing and minwise independence
• On the cell probe complexity of membership and perfect hashing
• Two results on tables
• scientific article; zbMATH DE number 1688373

Cited in

(29)

• Implicit $O(1)$ Probe Search
• Linear-space data structures for range frequency queries on arrays and trees
• Parameterized complexity of even/odd subgraph problems
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• Improved bounds for dictionary look-up with one error
• The Budgeted Unique Coverage Problem and Color-Coding
• An approximation algorithm for computing longest paths.
• Graphs, hypergraphs and hashing
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• The parameterized complexity of unique coverage and its variants
• Packing Arc-Disjoint Cycles in Tournaments
• Variants of constrained longest common subsequence
• Hardness and tractability of the \(\gamma\)-complete subgraph problem
• The limits of local search for weighted \(k\)-set packing
• Flash memory efficient LTL model checking
• Polynomial hash functions are reliable (extended abstract)
• Parameterized complexity of a coupled-task scheduling problem
• Confronting intractability via parameters
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• The communication complexity of set intersection and multiple equality testing
• Balanced hashing, color coding and approximate counting
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Packing arc-disjoint cycles in tournaments
• Perfect hashing
• Nearly Optimal Static Las Vegas Succinct Dictionary
• Bounds for \(c\)-ideal hashing

This page was built for publication: The Spatial Complexity of Oblivious k-Probe Hash Functions

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