On the k-Independence Required by Linear Probing and Minwise IndependenceReportar como inadecuado



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


On the k-Independence Required by Linear Probing and Minwise Independence - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Descargar gratis o leer online en formato PDF el libro: On the k-Independence Required by Linear Probing and Minwise Independence
We show that linear probing requires 5-independent hash functions for expected constant-time performance, matching an upper bound of Pagh et al. STOC07. More precisely, we construct a 4-independent hash functions yielding expected logarithmic search time. For 1+{\epsilon}-approximate minwise independence, we show that \Omegalog 1-{\epsilon}-independent hash functions are required, matching an upper bound of Indyk, SODA99. We also show that the very fast 2-independent multiply-shift scheme of Dietzfelbinger STACS96 fails badly in both applications.



Autor: Mikkel Thorup

Fuente: https://archive.org/







Documentos relacionados