On the k-independence required by linear probing and minwise independence

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

On the k-independence required by linear probing and minwise independence. / Pǎtraşcu, Mihai; Thorup, Mikkel.

In: ACM Transactions on Algorithms, Vol. 12, No. 1, 8, 2016.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Pǎtraşcu, M & Thorup, M 2016, 'On the k-independence required by linear probing and minwise independence', ACM Transactions on Algorithms, vol. 12, no. 1, 8. https://doi.org/10.1145/2716317

APA

Pǎtraşcu, M., & Thorup, M. (2016). On the k-independence required by linear probing and minwise independence. ACM Transactions on Algorithms, 12(1), [8]. https://doi.org/10.1145/2716317

Vancouver

Pǎtraşcu M, Thorup M. On the k-independence required by linear probing and minwise independence. ACM Transactions on Algorithms. 2016;12(1). 8. https://doi.org/10.1145/2716317

Author

Pǎtraşcu, Mihai ; Thorup, Mikkel. / On the k-independence required by linear probing and minwise independence. In: ACM Transactions on Algorithms. 2016 ; Vol. 12, No. 1.

Bibtex

@article{5896a5276c9f4a5f81dc315df6f8281b,
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. [2009]. More precisely, we construct a random 4-independent hash function yielding expected logarithmic search time for certain keys. For (1 + ε)-approximate minwise independence, we show that Ω(lg1 ε)-independent hash functions are required, matching an upper bound of Indyk [2001]. We also show that the very fast 2-independent multiply-shift scheme of Dietzfelbinger [1996] fails badly in both applications.",
keywords = "k-Independent hashing, Linear probing, Minwise independence",
author = "Mihai Pǎtra{\c s}cu and Mikkel Thorup",
year = "2016",
doi = "10.1145/2716317",
language = "English",
volume = "12",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery, Inc.",
number = "1",

}

RIS

TY - JOUR

T1 - On the k-independence required by linear probing and minwise independence

AU - Pǎtraşcu, Mihai

AU - Thorup, Mikkel

PY - 2016

Y1 - 2016

N2 - We show that linear probing requires 5-independent hash functions for expected constant-time performance, matching an upper bound of Pagh et al. [2009]. More precisely, we construct a random 4-independent hash function yielding expected logarithmic search time for certain keys. For (1 + ε)-approximate minwise independence, we show that Ω(lg1 ε)-independent hash functions are required, matching an upper bound of Indyk [2001]. We also show that the very fast 2-independent multiply-shift scheme of Dietzfelbinger [1996] 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. [2009]. More precisely, we construct a random 4-independent hash function yielding expected logarithmic search time for certain keys. For (1 + ε)-approximate minwise independence, we show that Ω(lg1 ε)-independent hash functions are required, matching an upper bound of Indyk [2001]. We also show that the very fast 2-independent multiply-shift scheme of Dietzfelbinger [1996] fails badly in both applications.

KW - k-Independent hashing

KW - Linear probing

KW - Minwise independence

U2 - 10.1145/2716317

DO - 10.1145/2716317

M3 - Journal article

AN - SCOPUS:84947920506

VL - 12

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 1

M1 - 8

ER -

ID: 160018732