Случайные поиски в больших разреженных массивах?

Question

Im, использующий HDF5 для хранения массивных разреженных массивов в формате координат (в основном, массив M x 3, который хранит значение, индекс x и индекс y для каждого ненулевого элемента).

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

например, учитывая 100x100 матрицы, я мог бы хранить то не редкие элементы, как так:

[[1,2,3,4,5], // Data values 
[13, 14, 55, 67, 80], // X-indices 
[45, 12, 43, 55, 12]] // Y-indices 

Я тогда хотел бы получить все значения данных между 10<x<32 и 10<y<32, например. В текущем формате все, что я могу сделать, это перебрать массивы индексов x и y, которые ищут соответствующие индексы. Это очень медленно, с несколькими чтениями с диска (мои реальные данные обычно имеют размер 200000x200000, и, возможно, 10000000 нерезкие элементы).

Есть ли лучший способ хранения больших (больших, чем RAM) разреженных матриц и поддержки быстрого поиска по индексу?

Я использую hdf5, но счастлив отметить и в других направлениях

Answer 1

Во-первых, давайте предположим, что, как ваш пример намеков, но не утверждать окончательно, вы храните элементы в порядке, отсортированные по x первым и на y секунд.

Один простой метод для более быстрого поиска будет хранить x-index-index, вектор кортежей (следуя вашему примеру, это может быть [(10,1),(20,null),(30,null),(40,null),(50,3),...]), указывающие на места в векторе х-индекс, на котором работает от запуска элементов. Если этот индекс-индекс удобно помещается в ОЗУ, вы можете уйти с чтением его с диска только один раз в начале вашего вычисления.

Конечно, это поддерживает только быстрое расположение индексов x, а затем сканирование для y. Если вам необходимо поддерживать быстрое расположение как в области пространственного индексирования, так и HDF5, возможно, не лучшее хранилище на диске, которое вы могли бы выбрать.

Одна мысль, которая действительно имеет место, заключалась бы в определении z-order curve по вашему массиву и сохранению элементов в вашем файле HDF5 в этом порядке. В дополнение к тому, что вы хотите определить z-index, который идентифицирует местоположение начала элементов в каждом «фрагменте» массива. Это все начинает немного волосатым, я предлагаю вам посмотреть на the Wikipedia article on z-order curves и немного почесывать голову.

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

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