База данных для хранения разреженной матрицы

Question

У меня очень большая и очень разреженная матрица, состоящая только из 0 и 1.Затем я в основном работаю с парами (строка-столбец).У меня не более 10 тысяч пар в строке / столбце.

Мои потребности следующие:

• Параллельная вставка пар (строка-столбец)

• Быстрый поиск всей строки или столбца

• Быстрый запрос на существование пары (строка-столбец)

• Клиент Ruby, если это возможно

---

Существуют ли существующие базы данных, адаптированные для такого рода ограничений?

Если нет, что даст мне наилучшую производительность:

• База данных SQL с такой таблицей:

row(indexed) | column(indexed) (но индексы должны постоянно обновляться)

• AХранилище ключей NoSQL с двумя таблицами, подобными этой:

row => columns ordered list

column => rows ordered list

(но с параллельной вставкой элементов в списки)

• Что-то еще

Спасибо за помощь!

Answer 1

Разреженная матрица 0/1 звучит для меня как матрица смежности , которая используется для представления графика.Исходя из этого, возможно, что вы пытаетесь решить некоторую проблему с графами, и база данных графов подойдет вам.

Базы графов, такие как Neo4J , очень хороши для быстрого обходаграф, потому что для поиска соседей вершины требуется O (количество соседей данной вершины), поэтому он не связан с количеством вершин во всем графе.Neo4J также транзакционный, поэтому параллельная вставка не является проблемой.Вы можете использовать оболочку REST API в MRI Ruby или библиотеку JRuby для более плавной интеграции.

С другой стороны, если вы пытаетесь проанализироватьсвязей на графике, и этого будет достаточно, чтобы время от времени проводить такой анализ и просто предоставлять результаты, вы можете попытать счастья с помощью инфраструктуры для обработки графиков, основанной на Google Pregel .Это немного похоже на Map-Reduce, но нацелено на обработку графиков.Уже существует несколько реализаций с открытым исходным кодом этой статьи .

Однако, если база данных графов или среда обработки графов не удовлетворяют вашим потребностям, я рекомендую взглянуть на HBase, хранилище данных с открытым исходным кодом, ориентированное на столбцы, основанное на Google BigTable .Эта модель данных на самом деле очень похожа на описанную вами (разреженная матрица), она имеет транзакции на уровне строк и не требует извлечения всей строки, просто чтобы проверить, существует ли определенная пара.Для этой базы данных есть библиотеки Ruby , но я думаю, что для взаимодействия с ней было бы безопаснее использовать JRuby вместо MRI.

Answer 2

Если ваша матрица действительно разрежена (то есть узлы имеют только несколько взаимосвязей), то вы получите достаточно эффективное хранилище от СУБД, такой как Oracle, PostgreSQL или SQL Server.По сути, у вас будет таблица с двумя полями (строка, столбец) и индексом или ключом в каждую сторону.

Установите первичный ключ в одну сторону (в зависимости от того, выполняете ли вы в основном запрос по строке или столбцу) и выполнитедругой индекс на полях наоборот.Это будет хранить данные только там, где есть соединение, и оно будет пропорционально количеству ребер на графике.

Индексы позволят вам эффективно извлекать либо строку, либо столбец и всегда будут синхронизированы.

Если у вас есть 10 000 узлов и 10 соединений на узел, в базе данных будет только 100 000 записей.100 ребер на узел будут иметь 1000000 записей и так далее.Для разреженных подключений это должно быть достаточно эффективным.

Оценка пакета с ошибками

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

Если бы вы добавляли вставки по строкам или столбцам, вы получитеменьше операций ввода-вывода по одному из индексов, поскольку записи физически расположены вместе в одном из индексов.Если матрица действительно разрежена, то это представление списка смежности является, безусловно, самым компактным способом его хранения, который будет намного быстрее, чем сохранение его в виде двумерного массива.

Матрица 10 000 x 10 000 с 64-битнойзначение займет 800 МБ плюс индекс строки.Обновление одного значения потребовало бы записи по крайней мере 80 КБ для каждой записи (выписывание всей строки).Вы можете оптимизировать записи по строкам, если ваши данные могут быть сгруппированы по строкам на вставках.Если вставки выполняются в реальном времени и случайным образом, то для каждой вставки вы будете записывать по 80 тыс. Строк.

На практике эти записи будут иметь некоторую эффективность, поскольку все они будут записываться в непрерывной области, в зависимости откак ваша платформа NoSQL физически хранила свои данные.

Я не знаю, насколько скудна ваша связь, но если бы у каждого узла было в среднем 100 соединений, то у вас было бы 1 000 000 записей.Это будет примерно 16 байт на строку (строка Int4, столбец Int4, значение Double) плюс несколько байтов для кластерной таблицы и индекса покрытия.Эта структура заняла бы около 32 МБ + немного накладных расходов на хранение.

Обновление одной записи в строке или столбце приведет к двум операциям записи в один диск (8 КБ, на практике сегмент) для произвольного доступа, при условии, что вставки не упорядочены по строке или столбцу.

Добавление 1 миллиона случайно упорядоченных записей в представление массива приведет к примерно 80 ГБ операций записи + небольшие накладные расходы.Добавление 1м записей в представление списка смежности приведет к записи приблизительно 32 МБ (на практике 16 ГБ, поскольку весь блок будет записан для каждого конечного узла индекса), а также к небольшим накладным расходам.

Для этого уровня подключения (10000 узлов, 100 ребер на узел) список смежности будет более эффективным в пространстве памяти, а также, вероятно, и в операциях ввода-вывода.Вы получите некоторую оптимизацию от платформы, так что какой-то эталонный тест может быть уместным, чтобы увидеть, что быстрее на практике.