Exponential time improvement for min-wise based algorithms
DOI10.1016/J.IC.2011.01.005zbMATH Open1214.68256OpenAlexW2086694417MaRDI QIDQ716331FDOQ716331
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
Recommendations
- Exponential time improvement for min-wise based algorithms
- d-k-min-wise independent family of hash functions
- Exponential space improvement for min-wise based algorithms
- A small approximately min-wise independent family of hash functions
- Bottom-k and priority sampling, set similarity and subset sums with minimal independence
Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40) Data structures (68P05)
Cites Work
- Title not available (Why is that?)
- Low discrepancy sets yield approximate min-wise independent permutation families
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Size-estimation framework with applications to transitive closure and reachability
- Sketching Algorithms for Approximating Rank Correlations in Collaborative Filtering Systems
- On the k-Independence Required by Linear Probing and Minwise Independence
- Title not available (Why is that?)
- Title not available (Why is that?)
- Summarizing data using bottom-k sketches
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fingerprinting Ratings for Collaborative Filtering — Theoretical and Empirical Analysis
- A derandomization using min-wise independent permutations
Cited In (2)
This page was built for publication: Exponential time improvement for min-wise based algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q716331)
