Min-wise independent permutations

DOI10.1006/JCSS.1999.1690zbMath0958.68047DBLPjournals/jcss/BroderCFM00OpenAlexW2081193615WikidataQ57401536 ScholiaQ57401536MaRDI QIDQ1577016

Andrei Z. Broder, Alan M. Frieze, Moses Charikar, Michael Mitzenmacher

Publication date: 27 August 2000

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

Full work available at URL: https://doi.org/10.1006/jcss.1999.1690

zbMATH Keywords

min-wise independent families of permutations

Mathematics Subject Classification ID

Theory of compilers and interpreters (68N20)

Related Items (38)

Counting distinct items over update streams ⋮ Probabilistic frequent subtrees for efficient graph classification and retrieval ⋮ The Distortion of Locality Sensitive Hashing ⋮ Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence ⋮ Locality sensitive hashing with extended differential privacy ⋮ Incremental design-space model checking via reusable reachable state approximations ⋮ Derandomized constructions of \(k\)-wise (almost) independent permutations ⋮ Spatially-decaying aggregation over a network ⋮ Interval selection in the streaming model ⋮ Unnamed Item ⋮ A Sketch Algorithm for Estimating Two-Way and Multi-Way Associations ⋮ Optimizing \(K^2\) trees: a case for validating the maturity of network of practices ⋮ A fast output-sensitive algorithm for Boolean matrix multiplication ⋮ Min-wise independent groups ⋮ Growth of the perfect sequence covering array number ⋮ Succinct representations of permutations and functions ⋮ The complexity of LSH feasibility ⋮ Unnamed Item ⋮ FURL: fixed-memory and uncertainty reducing local triangle counting for multigraph streams ⋮ Streaming techniques and data aggregation in networks of tiny artefacts ⋮ On the Distortion of Locality Sensitive Hashing ⋮ Fingerprints for highly similar streams ⋮ Perturbed Identity Matrices Have High Rank: Proof and Applications ⋮ On the minimum number of completely 3-scrambling permutations ⋮ MULTIPLE TRANSITIVITY AND MIN-WISE INDEPENDENCE IN PERMUTATION GROUPS ⋮ Min-Wise Independent Families with Respect to any Linear Order ⋮ Improving MinHash via the containment index with applications to metagenomic analysis ⋮ How should we solve search problems privately? ⋮ Disjoint bases in a polymatroid ⋮ Using Bloom Filters to Speed Up HITS-Like Ranking Algorithms ⋮ Optimality in external memory hashing ⋮ Sketching information divergences ⋮ How to catch \(L_2\)-heavy-hitters on sliding windows ⋮ Frequent-Itemset Mining Using Locality-Sensitive Hashing ⋮ Anchor-based self-ensembling for semi-supervised deep pairwise hashing ⋮ Train tracks with gaps: applying the probabilistic method to trains ⋮ Simple multi-party set reconciliation ⋮ Unnamed Item

Cites Work

• Universal classes of hash functions
• Randomized geometric algorithms and pseudorandom generators
• Fredman–Komlós bounds and information theory
• Simple Constructions of Almost k-wise Independent Random Variables
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Min-wise independent permutations