On the k-Independence Required by Linear Probing and Minwise Independence

Mihai Pǎtraşcu; Mikkel Thorup

doi:10.1007/978-3-642-14165-2_60

On the k-Independence Required by Linear Probing and Minwise Independence

22 Citations (Scopus)

Abstract

We show that linear probing requires 5-independent hash functions for expected constant-time performance, matching an upper bound of [Pagh et al. STOC'07]. For (1+ε)-approximate minwise independence, we show that -independent hash functions are required, matching an upper bound of [Indyk, SODA'99]. We also show that the multiply-shift scheme of Dietzfelbinger, most commonly used in practice, fails badly in both applications.

Translated title of the contribution	On the k-Independence Required by Linear Probing and Minwise Independence
Original language	English
Title of host publication	Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), Part I, LNCS 6198
Number of pages	12
Publisher	Springer
Publication date	2010
Pages	715-726
ISBN (Print)	978-3-642-14164-5
ISBN (Electronic)	978-3-642-14165-2
DOIs	https://doi.org/10.1007/978-3-642-14165-2_60
Publication status	Published - 2010
Externally published	Yes

Series	Lecture notes in computer science
Volume	6198
ISSN	0302-9743

Access to Document

10.1007/978-3-642-14165-2_60

Cite this

On the k-Independence Required by Linear Probing and Minwise Independence. / Pǎtraşcu, Mihai; Thorup, Mikkel.

Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), Part I, LNCS 6198. Springer, 2010. p. 715-726 (Lecture notes in computer science, Vol. 6198).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

@inproceedings{602e8faba430434699ef5cb31f38dcc4,

title = "On the k-Independence Required by Linear Probing and Minwise Independence",

abstract = "We show that linear probing requires 5-independent hash functions for expected constant-time performance, matching an upper bound of [Pagh et al. STOC'07]. For (1+ε)-approximate minwise independence, we show that -independent hash functions are required, matching an upper bound of [Indyk, SODA'99]. We also show that the multiply-shift scheme of Dietzfelbinger, most commonly used in practice, fails badly in both applications.",

author = "Mihai Pǎtra{\c s}cu and Mikkel Thorup",

year = "2010",

doi = "10.1007/978-3-642-14165-2_60",

language = "English",

isbn = "978-3-642-14164-5",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "715--726",

booktitle = "Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), Part I, LNCS 6198",

}

TY - GEN

T1 - On the k-Independence Required by Linear Probing and Minwise Independence

AU - Pǎtraşcu, Mihai

AU - Thorup, Mikkel

PY - 2010

Y1 - 2010

N2 - We show that linear probing requires 5-independent hash functions for expected constant-time performance, matching an upper bound of [Pagh et al. STOC'07]. For (1+ε)-approximate minwise independence, we show that -independent hash functions are required, matching an upper bound of [Indyk, SODA'99]. We also show that the multiply-shift scheme of Dietzfelbinger, most commonly used in practice, fails badly in both applications.

AB - We show that linear probing requires 5-independent hash functions for expected constant-time performance, matching an upper bound of [Pagh et al. STOC'07]. For (1+ε)-approximate minwise independence, we show that -independent hash functions are required, matching an upper bound of [Indyk, SODA'99]. We also show that the multiply-shift scheme of Dietzfelbinger, most commonly used in practice, fails badly in both applications.

U2 - 10.1007/978-3-642-14165-2_60

DO - 10.1007/978-3-642-14165-2_60

M3 - Article in proceedings

SN - 978-3-642-14164-5

T3 - Lecture notes in computer science

SP - 715

EP - 726

BT - Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), Part I, LNCS 6198

PB - Springer

ER -

On the k-Independence Required by Linear Probing and Minwise Independence

Abstract

Access to Document

Fingerprint

Cite this