Самый быстрый способ выполнить тестовую операцию с подмножеством в большой коллекции наборов с одним и тем же доменом

Question

Предположим, у нас есть где-то триллионы наборов.Домен для каждого из этих наборов одинаков.Это также конечно и дискретно.Таким образом, каждый набор может быть сохранен как битовое поле (например: 0000100111 ...) относительно короткой длины (например, 1024).То есть бит X в битовом поле указывает, включен ли элемент X (из 1024 возможных элементов) в данный набор или нет.

Теперь я хочу разработать структуру хранения и алгоритм для эффективного ответа на запрос.: то, что устанавливает в хранилище данных, установило Y как подмножество.Сам набор Y не присутствует в хранилище данных и указывается во время выполнения.

Теперь самый простой способ решить эту проблему - это использовать И битовое поле для набора Y с битовыми полями каждого набора в одном хранилище данных.по одному, выбирая те, чей результат AND соответствует битовому полю Y.

Как я могу ускорить это?Существует ли древовидная структура (индекс) или какой-нибудь умный алгоритм, который позволил бы мне выполнить этот запрос без необходимости И И Битовое поле каждого сохраненного набора?

Существуют ли базы данных, которые уже поддерживают такие операции с большими коллекциями наборов?1009 *

Answer 1

Если вы можете предварительно обработать наборы, отношение подмножеств представимо как DAG (потому что вы описываете набор).Если транзитивное сокращение вычисляется, то я думаю, что вы можете избежать тестирования всех наборов, просто выполнив DFS, начиная с самых больших наборов и останавливаясь всякий раз, когда Y больше не является подмножеством посещаемого текущего набора.

Answer 2

В зависимости от количества элементов набора, из которого взяты все наборы, одним из вариантов может быть построение инвертированного отображения индекса из элементов в наборы, которые их содержат.Учитывая набор Y, вы могли бы затем найти все наборы, которые имеют Y в качестве подмножества, найдя все наборы, которые содержат каждый элемент в отдельности, и вычислили их пересечение.Если вы храните списки в отсортированном порядке (например, путем нумерации всех наборов в вашей базе данных со значениями 0, 1 и т. Д.), То вы сможете вычислить это пересечение достаточно эффективно, предполагая, что ни один элемент не содержится в слишкоммного комплектов.

Answer 3

Если бы СУБД была вашей единственной опцией, я бы порекомендовал взглянуть на эту интересную статью о моделировании DAG в SQL:

http://www.codeproject.com/KB/database/Modeling_DAGs_on_SQL_DBs.aspx?msg=3051183

Если вы не можете позволить себе Oracle или MSSQL, взгляните на PostgresQL 9, который поддерживает рекурсивные запросы. Он также поддерживает кросс-соединения в течение достаточно долгого времени.

Answer 4

Быстрый взгляд заставляет меня задуматься о BDD, что в некоторой степени соответствует идее решения DAG. В качестве альтернативы ZDD.

Answer 5

Это будет натяжение обычной СУБД, основанной на вашем объеме, вы смотрели на Neo4j , основанную на модели хранилища графиков?

Answer 6

Я склонен говорить, что ответ отрицательный, поскольку битовое поле имеет очень низкую мощность.