Сборники трудов ИСП РАН


Исследование и развитие метода декомпозиции для анализа больших пространственных данных.

Золотов В.А., Семенов В.А.

Аннотация

Статья посвящена развитию метода декомпозиции для индексации, поиска и анализа больших пространственных данных. Главное внимание уделяется алгоритмам, основанным на регулярных октальных деревьях и обеспечивающим эффективное решение ряда вычислительных задач. Исследуемые алгоритмы определения столкновений и выборки по заданной области, в частности, применимы для моделирования сложных динамических пространственно-трехмерных сцен с объектами, имеющими протяженные границы. Для модельного набора данных на основе вероятностного анализа выводятся оценки сложности, которые обобщают и улучшают известные результаты и служат теоретическим обоснованием для применения алгоритмов к более широкому классу приложений.

Ключевые слова

Пространственные индексы, октальные деревья, вычислительная трудоемкость

Издание

Труды Института системного программирования РАН, том 25, 2013, стр. 131-166.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2013-25-8

Полный текст статьи в формате pdf Вернуться к содержанию тома