Exponential time improvement for min-wise based algorithms

DOI10.1016/j.ic.2011.01.005zbMath1214.68256OpenAlexW2086694417MaRDI QIDQ716331

Ariel Shiftan, Ely Porat, Guy Feigenblat

Publication date: 28 April 2011

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2011.01.005

zbMATH Keywords

min-wise independent family of hash functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Data structures (68P05) Online algorithms; streaming algorithms (68W27) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Low discrepancy sets yield approximate min-wise independent permutation families
• A derandomization using min-wise independent permutations
• Size-estimation framework with applications to transitive closure and reachability
• Fingerprinting Ratings for Collaborative Filtering — Theoretical and Empirical Analysis
• Sketching Algorithms for Approximating Rank Correlations in Collaborative Filtering Systems
• On the k-Independence Required by Linear Probing and Minwise Independence
• Summarizing data using bottom-k sketches
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Exponential time improvement for min-wise based algorithms