d-k-min-wise independent family of hash functions

DOI10.1016/j.jcss.2016.09.005zbMath1353.68064OpenAlexW2531371138MaRDI QIDQ340570

Guy Feigenblat, Ely Porat, Ariel Shiftan

Publication date: 14 November 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2016.09.005

zbMATH Keywords

similaritydata streamsmin-wise hash functionsraritywindowed data streams

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Randomized algorithms (68W20)

Cites Work

• Low discrepancy sets yield approximate min-wise independent permutation families
• Fingerprints for highly similar streams
• New hash functions and their use in authentication and set equality
• Size-estimation framework with applications to transitive closure and reachability
• Exponential Space Improvement for minwise Based Algorithms
• Sketching Algorithms for Approximating Rank Correlations in Collaborative Filtering Systems
• On the k-Independence Required by Linear Probing and Minwise Independence
• Sketching for Big Data Recommender Systems Using Fast Pseudo-random Fingerprints
• The Power of Simple Tabulation Hashing
• Summarizing data using bottom-k sketches
• Bottom-k and priority sampling, set similarity and subset sums with minimal independence
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: d-k-min-wise independent family of hash functions