Memperkirakan ukuran persimpangan beberapa set dengan menggunakan sampel satu set

Saya sedang mengerjakan suatu algoritma yang perlu menghitung ukuran satu set yang dihasilkan oleh persimpangan setidaknya 2 set. Lebih spesifik:

z = | A_{0} \cap \dots \cap A_{n} |

$z = \left |A_0 \cap \ldots \cap A_n \right |$

Set yang berpotongan dihasilkan oleh query SQL, dan dalam upaya untuk menjaga hal-hal cepat, saya mendapatkan hitungan setiap query sebelumnya, kemudian mengambil set dengan jumlah terendah ( ) dan menggunakan ID tersebut sebagai batas pada sisa pertanyaan besar, sehingga persimpangan secara efektif menjadi: $A_0$

z = | (A_{0} \cap A_{1}) \cap \dots \cap (A_{0} \cap A_{n}) |

$z = \left |\left ( A_0 \cap A_1 \right ) \cap \ldots \cap \left ( A_0 \cap A_n \right ) \right |$

Bahkan strategi ini membuat saya dengan beberapa pertanyaan yang cukup besar untuk dijalankan, karena terkadang bisa besar. Ide saya untuk berurusan dengan itu adalah mengambil sampel acak dan memotongnya dengan sisa set sebelum mengekstrapolasi kembali ke perkiraan tepat . Pertanyaan saya adalah: apa cara terbaik untuk melakukan pengambilan sampel dan kemudian memperkirakan untuk kembali ke nilai yang, jika tidak sepenuhnya akurat, memiliki rentang kesalahan yang dapat diprediksi? $\left | A_0 \right |$ $A_0$ $z$ $z$

Inilah yang saya coba sejauh ini (dalam kodesemu, semacam):

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)

Kode ini berfungsi, tetapi tampaknya secara konsisten melebih-lebihkan z, dengan ukuran sampel yang lebih rendah menghasilkan perkiraan yang lebih tinggi. Selain itu, saya tidak yakin bagaimana ini akan skala dengan lebih dari dua set untuk berpotongan.

Saya harap pertanyaan ini masuk akal, beri tahu saya jika saya dapat mengklarifikasi lebih lanjut. Juga, jika pertanyaan ini di luar topik atau berada di tempat lain, beri tahu saya dan saya senang memindahkannya.

Per komentar Bill , saya menjalankan beberapa percobaan cepat untuk menunjukkan ukuran sampel vs kesalahan. Setiap ember ukuran sampel dijalankan 20 kali, dan seperti yang Anda lihat ada tren yang cukup jelas:

Merencanakan

error sample Jimmy Sawczuk
sumber

A_{0}

$A_0$

A

$A$

@Bill Saya menambahkan sebidang ukuran sampel vs kesalahan yang menggambarkan apa yang saya lihat. Ini lebih seperti 20 kali dari 20. Adapun sampel acak, ini acak ORDER BY RAND(), yang tidak sempurna tetapi harus cocok untuk tugas ini.

Jimmy Sawczuk

@JimmySawczuk Bukankah lebih baik hanya memotong "set kerja" dengan "a" secara langsung, daripada "berpotongan (A0, a)"? Karena "A0" mungkin akan lebih besar dari "set kerja" saat ini dalam algoritme setelah dijalankan pertama ... Apakah saya memahami ini dengan benar?

A_{0}

$A_0$

Dapatkah saya bertanya apakah ukuran persimpangan, relatif terhadap ukuran set aslinya, sangat kecil? Jika demikian, saya merasa seperti itu akan menjelaskan masalah Anda. Saya telah menjalankan beberapa simulasi (dengan set yang lebih kecil) dan saya juga mendapatkan estimasi yang cukup konsisten, meskipun kecil, terlalu tinggi.

Memperkirakan ukuran persimpangan beberapa set dengan menggunakan sampel satu set

Jawaban: