Как лучше всего хранить двумерный разреженный массив (двухмерную разреженную матрицу)? Какой размер он будет иметь в VoltDB?

Вопрос первый: существуют ли специализированные базы данных для хранения плотных и разреженных матриц? Я гуглил, но не нашел...

Рассматриваемая матрица огромна (10 ^ 5 на 10 ^ 5), но она разрежена, что означает, что большинство ее значений являются нулями, и мне нужно хранить только ненулевые значения. Вот я и подумал сделать вот такую ​​таблицу:

   2D Matrix
---------------
  X   Y   val
---------------
  1   2    4.2
  5   1    91.0
  9   3    139.1

И так далее. 3 столбца, два для координат, третий для значения этой ячейки в разреженной матрице. Вопрос 2. Является ли это лучшим способом хранения разреженной матрицы? Я также думал о MongoDB, но кажется, что создание одного документа на ячейку матрицы было бы слишком накладным. Базы данных, ориентированные на таблицы, работают медленно, но я могу использовать VoltDB :) Боковой узел: я подумал о Redis Hash, но не могу сделать его двумерным (нашел способ сериализовать 2D-матрицы и сделать их 1D, чтобы я мог хранить в хэш Redis или даже список)

Вопрос 3: Сколько байтов в строке будет использовать VoltDB? Координаты будут целыми числами в диапазоне от 0 до 10^5, а может и больше, значения ячейки будут вещественными.


sql database matrix sparse-matrix voltdb
person João Pinto Jerónimo    schedule 03.06.2012    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Что касается вопроса 3, на основе вашего примера столбцы X и Y могут быть типом данных INTEGER в VoltDB, что составляет 4 байта. Столбец значений может иметь тип данных FLOAT, размер которого составляет 8 байт.

Таким образом, каждая запись будет иметь размер 16 байт, поэтому номинальный размер памяти будет равен 16 байт * количество строк. Как правило, вы добавляете 30 % накладных расходов, а затем 1 ГБ на сервер для размера кучи, чтобы определить общий объем необходимой памяти. См. приведенные ниже ссылки для более подробной информации.

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

Индекс дерева: (сумма размеров столбцов + 8 + 32) * количество строк Хэш-индекс: (((2 * количество строк) + 1) * 8) + ((сумма размеров столбцов + 32) * количество строк)

сумма размеров столбцов для (x, y) составляет 8 байтов.

Использованная литература:

Доступные типы данных перечислены в Приложении A к использованию VoltDB: http://community.voltdb.com/docs/UsingVoltDB/ddlref_createtable#TabDatatypes

Рекомендации и формулы для оценки объема памяти приведены в Руководстве по планированию VoltDB: http://community.voltdb.com/docs/PlanningGuide/ChapMemoryRecs

person BenjaminBallard    schedule 06.06.2012

arrow_upward
2
arrow_downward

Два наиболее важных вопроса: 1) насколько разрежены? и 2) как вы хотите использовать данные?

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

Предполагая, что ваши данные довольно разрежены, и предполагая, что вы хотите использовать данные в базе данных, хранилище кортежей x, y, value, вероятно, лучше всего. Глава 4 Руководства по планированию VoltDB посвящена оценке использования памяти и размерам вашего оборудования.

http://community.voltdb.com/docs/PlanningGuide/ChapMemoryRecs

Короткий ответ заключается в том, что таблицы с числовыми данными упакованы довольно плотно. У вас есть 12 байт реальных данных на строку (короткие, короткие, двойные). Вы должны увидеть в среднем чуть более 1 байта сверх служебных данных на строку. Вам также нужно будет добавить размер любых индексов. В документации описан худший случай. Я думаю, что для индекса по двум коротким целым числам, таким как столбцы X и Y, хранилище на ключ будет близко к 28 байтам, включая накладные расходы.

person John Hugg    schedule 06.06.2012