Exponential time improvement for min-wise based algorithms
DOI10.1016/J.IC.2011.01.005zbMATH Open1214.68256OpenAlexW2086694417MaRDI QIDQ716331FDOQ716331
Authors: Guy Feigenblat, Ely Porat, Ariel Shiftan 
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
- A near-optimal algorithm for computing the entropy of a stream
- Title not available (Why is that?)
- Fingerprinting ratings for collaborative filtering -- theoretical and empirical analysis
- A derandomization using min-wise independent permutations
Cited In (8)
- A small approximately min-wise independent family of hash functions
- Improved range-summable random variable construction algorithms
- Approximately minwise independence with twisted tabulation
- Estimation of three-way similarities based on connected bit Minwise Hash
- Faster parameterized algorithms for minor containment
- Exponential time improvement for min-wise based algorithms
- Consistent subset sampling
- Exponential space improvement for min-wise based algorithms
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)
