2

Say I have a List A of $1,000,000$ values, and List $B$ of $2,000,000$ values. I want to know what percent of List $B$ is in list A without looking at all $2,000,000$ values and referencing List $A$.

So, I want to only look at some of list $A$ and list $B$, rather than going through the entire list. Is there a way to reliably look at a percentage of the values of list $A$ and a percentage of the values of list $B$ (at random), compare those samples, and estimate the percent overlap for the entire lists $A$ and $B$?

Caleb Stanford
  • 45,895
Dan
  • 21
  • 1
    I don't understand the question. So you're given the precentage of each value in list A and in list B? Isn't that equivalent to being given the original lists? Are the 1,000,000 values and 2,000,000 values possible all distinct, or are they coming from a small set of possibilities? – Caleb Stanford Sep 23 '16 at 20:47
  • Not percentage of a value percentage of the list of values. I want to select a percentage of the values in List A and B at random and get an intersection. Use that intersection the guess the intersection of the full list. – Dan Sep 23 '16 at 20:52
  • Thanks for clarifying. This is a great question. It is easy to estimate by only looking at a random subset of list $B$. The hard part is trying to avoid going through the entire list $A$. – Caleb Stanford Sep 23 '16 at 21:04

0 Answers0