✦ LIBER ✦

Perfect Hash Families: Probabilistic Methods and Explicit Constructions

✍ Scribed by Simon R. Blackburn

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 113 KB
Volume: 92
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1999.3050

No coin nor oath required. For personal study only.

✦ Synopsis

An (n, q, t)-perfect hash family of size s consists of a set V of order n, a set F of order q, and a sequence , 1 , , 2 , ..., , s of functions from V to F with the following property. For all t-subsets X V, there exists i # [1, 2, ..., s] such that , i is injective when restricted to X. An (n, q, t)-perfect hash family of minimal size is known as optimal. The paper presents a probabilistic existence result for perfect hash families which improves on the well known result of Mehlhorn for many parameter sets. The probabilistic methods are strong enough to establish the size of an optimal perfect hash family in many cases. The paper also gives several explicit constructions of classes of perfect hash families.

📜 SIMILAR VOLUMES

Some recursive constructions for perfect

Some recursive constructions for perfect hash families

✍ M. Atici; S. S. Magliveras; D. R. Stinson; W.-D. Wei 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 452 KB

An (n, m, w)-perfect hash family is a set of functions F such that f : (1

Explicit Constructions of Perfect Hash F

Explicit Constructions of Perfect Hash Families from Algebraic Curves over Finite Fields

✍ Huaxiong Wang; Chaoping Xing 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 149 KB

Let A be a set of order n and B be a set of order m. An (n, m, w)-perfect hash family is a set H of functions from A to B such that for any X A with |X |=w, there exists an element h # H such that h is one-to-one when restricted to X. Perfect hash families have many applications to computer science,

New constructions for perfect hash famil

New constructions for perfect hash families and related structures using combinatorial designs and codes

✍ D. R. Stinson; R. Wei; L. Zhu 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB 👁 1 views

In this paper, we consider explicit constructions of perfect hash families using combinatorial methods. We provide several direct constructions from combinatorial structures related to orthogonal arrays. We also simplify and generalize a recursive construction due to Atici, Magliversas, Stinson and

Constructions of 2-cover-free families a

Constructions of 2-cover-free families and related separating hash families

✍ P. C. Li; G. H. J. van Rees; R. Wei 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 158 KB

## Abstract Cover‐free families (CFFs) were considered from different subjects by numerous researchers. In this article, we mainly consider explicit constructions of (2; __d__)‐cover‐free families. We also determine the size of optimal 2‐cover‐free‐families on 9, 10, and 11 points. Related separati

Optimal linear perfect hash families wit

Optimal linear perfect hash families with small parameters

✍ S. G. Barwick; Wen-Ai Jackson; Catherine T. Quinn 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB

## Abstract A linear (__q__^__d__^, __q__, __t__)‐perfect hash family of size __s__ consists of a vector space __V__ of order __q__^__d__^ over a field __F__ of order __q__ and a sequence ϕ~1~,…,ϕ~__s__~ of linear functions from __V__ to __F__ with the following property: for all __t__ subsets __X_

A Structured Family of Clustering and Tr

A Structured Family of Clustering and Tree Construction Methods

✍ David Bryant; Vincent Berry 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 190 KB

A cluster A is an Apresjan cluster if every pair of objects within A is more similar than either is to any object outside A. The criterion is intuitive, compelling, but often too restrictive for applications in classification. We therefore explore extensions of Apresjan clustering to a family of rel