使用一組樣本估計多組交集的大小

我正在研究一種算法，該算法需要計算由至少 2 個集合的交集生成的集合的大小。進一步來說：

相交的集合是由 SQL 查詢生成的，為了保持速度，我提前計算了每個查詢的計數，然後取計數最低的集合（) 並將這些 ID 用作其餘大查詢的界限，因此交集有效地變為：

即使這個策略也讓我有一些相當大的查詢要運行，因為有時可能很大。我處理這個問題的想法是隨機抽樣並將其與其餘集合相交，然後再推斷回正確估計. 我的問題是：進行採樣然後推斷返回值的最佳方法是什麼也就是說，如果不完全準確，是否具有可預測的誤差範圍？

---

這是我迄今為止嘗試過的（在偽代碼中）：

sample_threshold := 10000
factor := 1
if (len(A0) > sample_treshold) {
   factor = sample_threshold / len(A0)
}

// Take a random sample of size 10000 from A0

// Intersect all the other sets with the A0 sample, then with each other
working_set := A0
for i, a := range A {
   a = intersect(A0, a)
   working_set = intersect(working_set, a)
}

z := len(working_set) * (1 / factor)

此代碼有效，但似乎始終高估z，樣本量越小，估計值越高。此外，我不確定這將如何與兩個以上的集合相交。

我希望這個問題是有道理的，讓我知道是否可以進一步澄清。另外，如果這個問題離題或屬於其他地方，請告訴我，我很樂意移動它。

---

根據比爾的評論，我進行了一些快速試驗以顯示樣本量與錯誤。每個樣本大小的存儲桶運行 20 次，您可以看到有一個非常明顯的趨勢：

如果你的設置有重複的元素（即，它實際上是一個多重集），交集的大小將被您的程序高估，因為您的比例因子使用採樣的元素數量而不是採樣的唯一“類型”的數量。您可以通過將因子計算為隨機樣本中唯一元素數與完整集合中唯一元素數之比來糾正估計值.

引用自：https://stats.stackexchange.com/questions/97093