Exponential space improvement for min-wise based algorithms

DOI10.4230/LIPICS.FSTTCS.2012.70MaRDI QIDQ2957482zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(6)

• Fingerprints for highly similar streams
• 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
• d-k-min-wise independent family of hash functions
• Approximately minwise independence with twisted tabulation

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)