Exponential time improvement for min-wise based algorithms

DOI10.1016/J.IC.2011.01.005MaRDI QIDQ716331zbMATHOpenAlexFDO

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

zbMATH Keywords

min-wise independent family of hash functions

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 1615265 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1256644 (Why is no real title available?)
• scientific article; zbMATH DE number 1305436 (Why is no real title available?)
• scientific article; zbMATH DE number 1947403 (Why is no real title available?)
• scientific article; zbMATH DE number 2019620 (Why is no real title available?)
• scientific article; zbMATH DE number 1775418 (Why is no real title available?)
• A derandomization using min-wise independent permutations
• A near-optimal algorithm for computing the entropy of a stream
• Fingerprinting ratings for collaborative filtering -- theoretical and empirical analysis
• Low discrepancy sets yield approximate min-wise independent permutation families
• On the \(k\)-independence required by linear probing and minwise independence
• Size-estimation framework with applications to transitive closure and reachability
• Sketching Algorithms for Approximating Rank Correlations in Collaborative Filtering Systems
• Summarizing data using bottom-\(k\) sketches

Cited in

(8)

• Exponential space improvement for min-wise based algorithms
• Faster parameterized algorithms for minor containment
• Consistent subset sampling
• Exponential time improvement for min-wise based algorithms
• 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

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)