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

2013/02/20 by Mikkel Thorup, Thorup, Mikkel · 2 citations
Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1302.5127

openalex publication_date 2013/02/20 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28

Abstract

We show that linear probing requires 5-independent hash functions for\nexpected constant-time performance, matching an upper bound of [Pagh et al.\nSTOC'07]. More precisely, we construct a 4-independent hash functions yielding\nexpected logarithmic search time.\n For (1+\ε)-approximate minwise independence, we show that \Ω(log\n1/\ε)-independent hash functions are required, matching an upper bound\nof [Indyk, SODA'99].\n We also show that the very fast 2-independent multiply-shift scheme of\nDietzfelbinger [STACS'96] fails badly in both applications.\n

Cited by

• Explicit Min-wise Hash Families with Optimal Size
• Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data

Related

• Linear Probing with Constant Independence
• Linear Probing with 5-Independent Hashing
• Even Better Framework for min-wise Based Algorithms
• Constructions of k-Min-Wise Hash from Bounded Independence
• Two-way Linear Probing Revisited