Exponential space improvement for min-wise based algorithms

DOI10.4230/LIPICS.FSTTCS.2012.70zbMATH Open1354.68303OpenAlexW2293016185MaRDI QIDQ2957482FDOQ2957482

Authors: Guy Feigenblat, Ely Porat, Ariel Shiftan 

Publication date: 26 January 2017

Full work available at URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2012.70

Recommendations

• d-k-min-wise independent family of hash functions
• Exponential time improvement for min-wise based algorithms
• Exponential time improvement for min-wise based algorithms
• A small approximately min-wise independent family of hash functions
• Approximately minwise independence with twisted tabulation

zbMATH Keywords

online algorithmssimilarityhash functionsstreamingmin-wise based algorithmssub-linear algorithms

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)

Cited In (6)

• A small approximately min-wise independent family of hash functions
• Approximately minwise independence with twisted tabulation
• d-k-min-wise independent family of hash functions
• Fingerprints for highly similar streams
• Exponential time improvement for min-wise based algorithms
• Exponential time improvement for min-wise based algorithms

This page was built for publication: Exponential space 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 Q2957482)