Подскажите, пожалуйста, способ хранения многомерных разреженных матриц
В постановке задачи не хватает описания операций, которые нужно будет над структурой данных делать, ибо если точки надо просто хранить, вопросов возникать не должно 
В постановке задачи не хватает описания операций, которые нужно будет над структурой данных делать, ибо если точки надо просто хранить, вопросов возникать не должноТочно, забыл указать.
Единственная операция, время выполнения которой желательно минимизировать, это получение среза пространства по N-1 измерению (надеюсь, правильно сформулировал). То есть, если всего измерений N, на входе имеем N-1 фиксированную координату, на выходе - массив "вёдер", пересекаемых прямой, получаемой при варьировании оставшейся незафиксированной координаты.
Можно, но нежелательно, оставить возможность при формировании среза фиксировать только первые N-1 координат, а последняя всегда будет свободной. Такое ограничение, возможно, позволит более эффективно хранить данные для выполнения такой операции.
Операций модификации структуры вообще не требуется, достаточно полного перестроения при получении новой порции данных.
ИМХО текстовые файлы + любой скриптовый язык.. (но про любой это я пожалуй соврал)...
а моно уточнить - 1000 ГБ - это в каком виде? В принципе, есть системы для in-memory OLAP, причем данные загнанные в эту самую in-memory занимают раза в 3-5 меньше чем в реляционной СУБД, но серваки с 256 ГБ оперативки на дороге еще пока не валяются...
а моно уточнить - 1000 ГБ - это в каком виде? В принципе, есть системы для in-memory OLAP, причем данные загнанные в эту самую in-memory занимают раза в 3-5 меньше чем в реляционной СУБД, но серваки с 256 ГБ оперативки на дороге еще пока не валяются...
Какая точность нужна и какие минимальная и максимальная координаты по измерениям?
В общем так:
Делим пространство на кусочки. Каждую координату на 2 части, чтоб по сторонам было примерно одинаковое количество точек.
Получаем кубики.
Прямая проходит через сколько-то кубиков.
Выбираем те, через которые она проходит.
С этими кубиками делаем то же что и с первым.
Предварительно (перед запуском алгоритма) нужно посчитать границы будущих кубиков, уровень, до которого хотим дойти.
Каждую точку приписать к маленькому кубику. Т.е. маленький кубик задает связку точек.
В итоге по прямой находим набор маленьких кубиков, в которых лежат точки-кандидаты, точки-кандидаты обсчитываем с нужной точностью.
Никаких особых Гб оперативной памяти тут не надо.
Связка точек задается Nбит*колво уровней.
Делим пространство на кусочки. Каждую координату на 2 части, чтоб по сторонам было примерно одинаковое количество точек.
Получаем кубики.
Прямая проходит через сколько-то кубиков.
Выбираем те, через которые она проходит.
С этими кубиками делаем то же что и с первым.
Предварительно (перед запуском алгоритма) нужно посчитать границы будущих кубиков, уровень, до которого хотим дойти.
Каждую точку приписать к маленькому кубику. Т.е. маленький кубик задает связку точек.
В итоге по прямой находим набор маленьких кубиков, в которых лежат точки-кандидаты, точки-кандидаты обсчитываем с нужной точностью.
Никаких особых Гб оперативной памяти тут не надо.
Связка точек задается Nбит*колво уровней.
Посмотри на HDF5. Может подойдет.
Это называется kd-tree. Я так понял вопрос не столько в организации хранения, сколько в последующемм рапределении этого по нескольким машинам.
И чего сложного в распределении?
Ну, например, для kd-tree, я не знаю как распределить так, чтобы вычисления более-менее равномерно ложились на все машины.
Но, может, автору этого и не нужно. Может, он готов херачить диск на каждый запрос. Ну, а если избавить от этого условия,
то задача-то уже давно известна, не нужно ничего изобретать.
Но, может, автору этого и не нужно. Может, он готов херачить диск на каждый запрос. Ну, а если избавить от этого условия,
то задача-то уже давно известна, не нужно ничего изобретать.
Ну, и тогда kd-tree - не лучшее решение по скорости, памяти и сложности построения.
В смысле, именно для разреженных матриц. Для них я бы как раз использовал 30-мерный двусвязный список (60-связный).
Правда, по памяти он может быть хуже, чем kd-tree. В зависимости от струтуры облака.
В смысле, именно для разреженных матриц. Для них я бы как раз использовал 30-мерный двусвязный список (60-связный).
Правда, по памяти он может быть хуже, чем kd-tree. В зависимости от струтуры облака.
Ну, например, для kd-tree, я не знаю как распределить так, чтобы вычисления более-менее равномерно ложились на все машины.Hadoop знает, правда непонятно причем тут kdtree.
то задача-то уже давно известна, не нужно ничего изобретать.
Ну ты почитай другие ответы в треде. И как раз задача с распределением известна, и весь фокус в том весь ли Тб на каждый чих обсчитывать.
ещё вопрос насколько mapreduce-ом удобно будет эти данные обрабатывать...
Оставить комментарий
dazzler
Вдруг кто сталкивался с подобной задачей? Хочу сэкономить время на поиске/разработке решения.Изначально задача такая:
1) Есть большое многомерное облако точек. Объём данных > 1000ГБ.
2) Координаты задаются числами с плавающей запятой.
3) Размерность пространства > 30.
4) Требуемая точность хранения координат для каждого измерения различается, но допустимое отклонение всегда > 0.
5) Точки распределены в пространстве очень неравномерно.
Нужно это добро как-то хранить.
С учётом пунктов 4 и 5 получается, что нужна структура вроде многомерной разреженной матрицы с интами в ячейках. Ячейка по сути представляет собой "ведро" со счётчиком попавших в эту область пространства точек.
Где можно почитать про существующие алгоритмы эффективного хранения таких структур?
Если существует готовая достаточно эффективная реализация, было бы вообще замечательно.