Оценка размера пересечения нескольких наборов с использованием выборки из одного набора

Я работаю над алгоритмом, который должен рассчитать размер набора, сгенерированного пересечениями не менее 2 наборов. Более конкретно:

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

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

Пересекающиеся наборы генерируются запросами SQL, и, чтобы поддерживать скорость, я заблаговременно получаю счет каждого запроса, затем беру набор с наименьшим счетом ( ) и использую эти идентификаторы в качестве границ для Остальные большие запросы, поэтому пересечение эффективно становится: $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 |$

Даже из-за этой стратегии у меня довольно большие запросы, так какиногда может быть большим. Моя идея разобраться с этим - взять случайную выборку и пересечь ее с остальными множествами, прежде чем экстраполировать обратно до правильной оценки . Мой вопрос: каков наилучший способ выполнить выборку, а затем экстраполировать, чтобы вернуться к значению , которое, если не совсем точно, имеет предсказуемый диапазон ошибок? $\left | A_0 \right |$ $A_0$ $z$ $z$

Вот что я пробовал до сих пор (в псевдокоде, вроде):

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 раз, и, как вы можете видеть, есть довольно четкая тенденция:

участок

error sample Джимми Сочук
источник

Я думаю, что простая случайная выборка без замены должна работать. Я сбит с толку, что вы получаете завышенные оценки. Похоже, что это точно соответствует оценке среднего значения по выборке из случайной выборки. Вы пытаетесь оценить вероятность того, что элемент находится на пересечении других s. Я показал простой пример, и он отлично работает. Насколько вы уверены, что вы постоянно переоцениваете? Случилось ли это как 15 раз из 20 или как 150 раз из 200? Образец действительно случайный?

A_{0}

$A_0$

A

$A$

Билл

@Bill Я добавил график зависимости размера выборки от ошибки, который иллюстрирует то, что я вижу. Это больше похоже на 20 раз из 20. Что касается случайной выборки, то она такая же случайная, как ORDER BY RAND()и не идеальная, но должна подходить для этой задачи.

Джимми Сончук

@JimmySawczuk Не лучше ли было бы просто пересечь «рабочий набор» с «a» напрямую, а не «intersect (A0, a)»? Потому что «A0», вероятно, будет больше, чем текущий «рабочий набор» в алгоритме после первого запуска ... Я правильно понимаю?

Можете ли вы подтвердить, что вы имеете в виду наборы, а не мультимножества (то есть, что в наборах нет дубликатов)? Потому что, если таковые имеются, легко переоценить размер «пересечения» по вашему методу. (Рассмотрим случай, когда - это всего лишь 100 копий одного и того же элемента, и вы отобрали половину из них.)

A_{0}

$A_0$

Innuo

Также я могу спросить, является ли размер пересечения относительно размера оригинальных наборов чрезвычайно маленьким? Если так, я чувствую, что это объяснит вашу проблему. Я провел несколько симуляций (с меньшими наборами), и я также получаю довольно последовательную, хотя и небольшую, переоценку.

Как указывает Innuo , моя проблема была из-за дубликатов в моем наборе , что привело к , что мой псевдокод оказался слишком низким, что, в свою очередь, привело к тому, что конечная экстраполяция оказалась слишком высокой, потому что она была сгенерирована с помощью инверсии . Удаление дубликатов решило эту проблему, и теперь алгоритм генерирует график зависимости дельты от размера выборки в соответствии с тем, что я ожидал (линии показывают предел погрешности при уровне достоверности 95% для этого размера выборки по отношению к общей совокупности). ): $A_0$ factorzfactor

участок

Джимми Сочук
источник

Оценка размера пересечения нескольких наборов с использованием выборки из одного набора

Ответы: