Bottom-k and priority sampling, set similarity and subset sums with minimal independence
From MaRDI portal
(Redirected from Publication:5495807)
Abstract: We consider bottom-k sampling for a set X, picking a sample S_k(X) consisting of the k elements that are smallest according to a given hash function h. With this sample we can estimate the relative size f=|Y|/|X| of any subset Y as |S_k(X) intersect Y|/k. A standard application is the estimation of the Jaccard similarity f=|A intersect B|/|A union B| between sets A and B. Given the bottom-k samples from A and B, we construct the bottom-k sample of their union as S_k(A union B)=S_k(S_k(A) union S_k(B)), and then the similarity is estimated as |S_k(A union B) intersect S_k(A) intersect S_k(B)|/k. We show here that even if the hash function is only 2-independent, the expected relative error is O(1/sqrt(fk)). For fk=Omega(1) this is within a constant factor of the expected relative error with truly random hashing. For comparison, consider the classic approach of kxmin-wise where we use k hash independent functions h_1,...,h_k, storing the smallest element with each hash function. For kxmin-wise there is an at least constant bias with constant independence, and it is not reduced with larger k. Recently Feigenblat et al. showed that bottom-k circumvents the bias if the hash function is 8-independent and k is sufficiently large. We get down to 2-independence for any k. Our result is based on a simply union bound, transferring generic concentration bounds for the hashing scheme to the bottom-k sample, e.g., getting stronger probability error bounds with higher independence. For weighted sets, we consider priority sampling which adapts efficiently to the concrete input weights, e.g., benefiting strongly from heavy-tailed input. This time, the analysis is much more involved, but again we show that generic concentration bounds can be applied.
Recommendations
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds
- A lower bound for sampling disjoint sets
- scientific article; zbMATH DE number 7650118
- Efficiency bounds for a generalization of ranked-set sampling
- An algorithm with applications in ranked-set sampling
- Priority sampling for estimation of arbitrary subset sums
- On computing minimal independent support and its applications to sampling and counting
- Near-optimal dominating sets via random sampling
- On the totality of ranked set sampling
- On the \(k\)-independence required by linear probing and minwise independence
Cited in
(9)- Binary vectors for fast distance and similarity estimation
- On computing minimal independent support and its applications to sampling and counting
- Consistent subset sampling
- d-k-min-wise independent family of hash functions
- Fingerprints for highly similar streams
- Real-valued embeddings and sketches for fast distance and similarity estimation
- scientific article; zbMATH DE number 7278047 (Why is no real title available?)
- Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum
- Exponential time improvement for min-wise based algorithms
This page was built for publication: Bottom-k and priority sampling, set similarity and subset sums with minimal independence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495807)
