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

Я использую 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 неразреженными элементами).

Есть ли лучший способ хранить большие (больше ОЗУ) разреженные матрицы и поддерживать быстрый поиск на основе индекса?

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


sparse-matrix hdf5 random-access
person jramm    schedule 19.02.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

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

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

person High Performance Mark    schedule 19.02.2016