Low discrepancy sets yield approximate min-wise independent permutation families

DOI10.1016/S0020-0190(99)00163-5zbMath1339.68196OpenAlexW1974833029WikidataQ56570612 ScholiaQ56570612MaRDI QIDQ294714

Shiyu Zhou, David Zuckerman, Aravind Srinivasan, Michael E. Saks

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019099001635?np=y

zbMATH Keywords

permutationsinformation retrievalcombinatorial problemsexplicit constructionsdocument filteringmin-wise independent permutationspseudorandom

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Information storage and retrieval of data (68P20) Internet topics (68M11)

Related Items

d-k-min-wise independent family of hash functions ⋮ Set-Codes with Small Intersections and Small Discrepancies ⋮ Unnamed Item ⋮ Exponential time improvement for min-wise based algorithms ⋮ Disjoint bases in a polymatroid

Cites Work

• Unnamed Item
• Unnamed Item
• Notes on geometry
• On the construction of pseudorandom permutations: Luby-Rackoff revisited
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• On a set of almost deterministic k-independent random variables
• Pseudorandomness for network algorithms
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• Finite Permutation Groups and Finite Simple Groups