The Spatial Complexity of Oblivious k-Probe Hash Functions

DOI10.1137/0219054zbMATH Open0711.68039OpenAlexW2079301493MaRDI QIDQ3495640FDOQ3495640

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

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

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)

Cited In (29)

• Title not available (Why is that?)
• Parameterized complexity of even/odd subgraph problems
• Linear-space data structures for range frequency queries on arrays and trees
• 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
• The parameterized complexity of unique coverage and its variants
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• 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
• Polynomial hash functions are reliable (extended abstract)
• Flash memory efficient LTL model checking
• Parameterized complexity of a coupled-task scheduling problem
• 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
• Confronting intractability via parameters
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• 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
• Bounds for \(c\)-ideal hashing
• Nearly Optimal Static Las Vegas Succinct Dictionary
• Implicit $O(1)$ Probe Search

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)