Как сохранить разреженную матрицу с запросами на диске или в базе данных?

Question

Мне нужно хранить разреженную матрицу на диске. Это похоже на таблицу базы данных с миллионами строк и тысячами столбцов, где многие или большинство столбцов равны нулю. Он должен быть запрашиваемым, как SQL SELECT с WHERE в некоторых столбцах.

Мои конкретные требования касаются Java. Сначала я подумал об использовании Berkeley DB для Java для имитации таблицы, но затем он не поддерживает запросы на основе значений.

Затем я подумал об использовании обычной базы данных SQL. Например, создание схемы только с идентификатором строки, идентификатором столбца и значением. Виртуальная строка будет все фактические строки с одинаковым идентификатором. Но тогда это выглядит как злоупотребление базой данных.

Есть идеи?

Answer 1

Первое, что пришло мне в голову при чтении заголовка вопроса, была строка базы данных для (x, y), как вы предложили в своем следующем, последнем абзаце.

Еще одна вещь, на которую следует обратить внимание, это то, что базы данных часто сжимают строки, особенно для NULL, поэтому прямое представление может не тратить столько места, сколько вы думаете.

Answer 2

Недавно я заинтересовался хранением типа ключ-значение и наткнулся на эту запись в блоге, описывающую, как FriendFeed использует MySQL для реализации аналогичного требования:

http://bret.appspot.com/entry/how-friendfeed-uses-mysql

Answer 3

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

Answer 4

база данных Intersystems Cache использует внутренние структуры для хранения данных, которые представляют собой разреженные многомерные массивы. Может быть, проверить это. Вы можете сделать запрос и сопоставить его с таблицами SQL. Я не уверен, что вы можете напрямую получить доступ к многомерным массивам в Intersystems Cache из Java.

Answer 5

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

Если вы можете сделать все с помощью последовательной обработки (например, сканирование в порядке строк), то для этого стоит рассмотреть еще один плоский файл.