Установить оракул пересечения

Оракул пересечения множеств (SIO) — это структура данных , которая представляет собой коллекцию множеств и может быстро отвечать на запросы о том, является ли пересечение множеств двух заданных множеств непустым.

Входные данные для задачи — n конечных множеств. Сумма размеров всех множеств равна N (что также означает, что существует не более N различных элементов). SIO должен быстро отвечать на любой запрос вида:

«Пересекается ли множество S _i с множеством S _k »?

Минимальный объем памяти, максимальное время запроса

Без какой-либо предварительной обработки ответ на запрос может быть получен путем вставки элементов S _i во временную хэш-таблицу , а затем проверки для каждого элемента S _k наличия его в хэш-таблице. Время запроса составляет . $O(|S_{i}|+|S_{j}|)=O(N)$

Максимум памяти, минимум времени запроса

В качестве альтернативы мы можем предварительно обработать наборы и создать таблицу n -by -n , в которую уже введена информация о пересечении. Тогда время запроса составит , но требуемая память составит . $O(1)$ $O(n^{2})$

Компромисс

Определите «большой набор» как набор с не менее элементами. Очевидно, что таких наборов не более . Создайте таблицу данных пересечения между каждым большим набором с каждым другим большим набором. Для этого требуется память. Кроме того, для каждого большого набора храните хэш-таблицу всех его элементов. Для этого требуется дополнительная память. ${\sqrt {N}}$ ${\sqrt {N}}$ $O(N)$ $O(N^{3/2})$

При наличии двух наборов возможны три случая:

Оба множества большие. Тогда просто прочитайте ответ на запрос пересечения из таблицы, во времени . $O(1)$
Оба набора малы. Затем вставьте элементы одного из них в хэш-таблицу и проверьте элементы другого; поскольку наборы малы, требуемое время составляет . $O({\sqrt {N}})$
Один набор большой, а другой маленький. Перебрать все элементы в маленьком наборе и проверить их по хэш-таблице большого набора. Требуемое время снова . $O({\sqrt {N}})$

В общем случае, если мы определяем «большой набор» как набор, содержащий не менее элементов, то число больших наборов не превышает , поэтому требуемая память составляет , а время запроса — . $N^{c}$ $N^{1-c}$ $O(N^{2-c})$ $O(N^{c})$

Сведение к приблизительному расстоянию оракула

Проблему SIO можно свести к проблеме приближенного оракула расстояния (DO) следующим образом. ^[1]

Постройте неориентированный двудольный граф , в котором одна часть содержит узел для каждого из n множеств, а другая часть содержит узел для каждого из (максимум) N элементов, содержащихся в множествах.
Между множеством и элементом существует ребро, если множество содержит элемент.

Этот граф имеет следующие свойства:

Если два множества пересекаются, то расстояние между ними равно 2 (от одного множества до элемента в пересечении и до другого множества).
Если два множества не пересекаются, то расстояние между ними составляет не менее 4.

Таким образом, с помощью DO, коэффициент аппроксимации которого меньше 2, мы можем решить проблему SIO.

Считается, что проблема SIO не имеет нетривиального решения. То есть, она требует пространства для ответа на запросы за время . Если эта гипотеза верна, это означает, что не существует DO с коэффициентом аппроксимации менее 2 и постоянным временем запроса. ^[1] $\Омега (n^{2})$ $O(1)$

Ссылки

^ ab Patrascu, M. ; Roditty, L. (2010). Оракулы расстояний за пределами границы Торупа–Цвика . 2010 IEEE 51-й ежегодный симпозиум по основам компьютерной науки (FOCS). стр. 815. doi :10.1109/FOCS.2010.83. ISBN 978-1-4244-8525-3.

[pr10-1] Patrascu, M. ; Roditty, L. (2010). Оракулы расстояний за пределами границы Торупа–Цвика . 2010 IEEE 51-й ежегодный симпозиум по основам компьютерной науки (FOCS). стр. 815. doi :10.1109/FOCS.2010.83. ISBN 978-1-4244-8525-3.