Balanced families of perfect hash functions and their applications

DOI10.1145/1798596.1798607zbMATH Open1300.68062arXiv0805.4300OpenAlexW1980074516MaRDI QIDQ2930337FDOQ2930337

Authors: Noga Alon, Shai Gutner 

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Abstract: The construction of perfect hash functions is a well-studied topic. In this paper, this concept is generalized with the following definition. We say that a family of functions from $[n]$ to $[k]$ is a $delta$-balanced $(n,k)$-family of perfect hash functions if for every $Ssubseteq[n]$, $|S|=k$, the number of functions that are 1-1 on $S$ is between $T/delta$ and $deltaT$ for some constant $T>0$. The standard definition of a family of perfect hash functions requires that there will be at least one function that is 1-1 on $S$, for each $S$ of size $k$. In the new notion of balanced families, we require the number of 1-1 functions to be almost the same (taking $delta$ to be close to 1) for every such $S$. Our main result is that for any constant $delta>1$, a $delta$-balanced $(n,k)$-family of perfect hash functions of size $2^{O(kloglogk)}logn$ can be constructed in time $2^{O(kloglogk)}nlogn$. Using the technique of color-coding we can apply our explicit constructions to devise approximation algorithms for various counting problems in graphs. In particular, we exhibit a deterministic polynomial time algorithm for approximating both the number of simple paths of length $k$ and the number of simple cycles of size $k$ for any $kleqO(fraclognlogloglogn)$ in a graph with $n$ vertices. The approximation is up to any fixed desirable relative error.

Full work available at URL: https://arxiv.org/abs/0805.4300

Recommendations

• Balanced Families of Perfect Hash Functions and Their Applications
• Balanced hashing, color coding and approximate counting
• Perfect hash families: Probabilistic methods and explicit constructions
• Simple and Space-Efficient Minimal Perfect Hash Functions
• Constructing Perfect Hash Families Using a Greedy Algorithm

zbMATH Keywords

color-codingperfect hashingapproximate counting of subgraphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cited In (11)

• The \(k\)-distinct language: parameterized automata constructions
• Approximate Counting of k-Paths: Deterministic and in Polynomial Space
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• The Budgeted Unique Coverage Problem and Color-Coding
• Counting problems in parameterized complexity
• Faster algorithms for finding and counting subgraphs
• Tensor network complexity of multilinear maps
• Counting connected subgraphs with maximum-degree-aware sieving
• Balanced Families of Perfect Hash Functions and Their Applications
• Balanced hashing, color coding and approximate counting
• The challenges of unbounded treewidth in parameterised subgraph counting problems

This page was built for publication: Balanced families of perfect hash functions and their applications

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