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

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

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

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

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

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

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

В качестве альтернативы мы можем предварительно обработать наборы и создать n на таблицу размером 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.

Итак, с ДО, коэффициент аппроксимации которого меньше 2, мы можем решить проблему SIO.

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

Ссылки

^ Jump up to: ^а ^б Патраску, М. ; Родитти, Л. (2010). Оракулы расстояния за границей Торупа-Цвика . 2010 51-й ежегодный симпозиум IEEE по основам информатики (FOCS). п. 815. дои : 10.1109/FOCS.2010.83 . ISBN 978-1-4244-8525-3 .

[pr10-1] Jump up to: ^а ^б Патраску, М. ; Родитти, Л. (2010). Оракулы расстояния за границей Торупа-Цвика . 2010 51-й ежегодный симпозиум IEEE по основам информатики (FOCS). п. 815. дои : 10.1109/FOCS.2010.83 . ISBN 978-1-4244-8525-3 .

[1]