Preview

Труды Института системного программирования РАН

Расширенный поиск

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

Аннотация

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

Об авторах

В. А. Золотов
ИСП РАН
Россия


В. А. Семенов
ИСП РАН
Россия


Список литературы

1. M. Cai., P. Revesz, Parametric rectangles: an index structure for moving objects, в Proceedings of the 10th COMAD International conference on management of data, 2000.

2. V. Semenov, K. Kazakov, S. Morozov, O. Tarlapan, V. Zolotov и T. Dengenis, 4D modeling of large industrial projects using spatio-temporal decomposition, в eWork and eBusiness in Architecture, Engineering and Construction, London, UK, pp. 89-95, 2010.

3. В. Золотов и В. Семенов, Cовременные методы поиска и индексации многомерных данных в приложениях моделирования больших динамических сцен, Труды Института системного программирования, (24), pp. 381-416, 2013.

4. G. Kedem, The quad-CIF tree: a data structure for hierarchical on-line algorithms, в Proceedings of the 19th Design Automation Conference, pp. 352-357, 1992.

5. B. J. Finkel R.A., Quad trees: a data structure for retrieval on composite keys, Acta Informatica, 1(4), pp. 1-9, 1974.

6. V. Semenov, K. Kazakov, V. Zolotov, H. Jones и S. Jones, Combined strategy for efficient collision detection in 4D planning applications, в Computing in Civil and Building Engineering, Nottingham, UK, pp. 31-39, 2010.

7. S. Gottschalk, M. C. Lin и D. Manocha, OBB Tree: a hierarchical structure for rapid interference detection, в Proceedings of the SIGGRAPH'96 Conference, New Orleans, USA, pp. 171-180, 1996.

8. S. Gottschalk, Collision queries using oriented bounding boxes, Chapel Hill: The University of North Carolina, 2000.

9. H. Samet, Foundations of Multidimentional and Metric Data Structures, San Francisco: Morgan Kaufmann, 2006.


Рецензия

Для цитирования:


Золотов В.А., Семенов В.А. Исследование и развитие метода декомпозиции для анализа больших пространственных данных. Труды Института системного программирования РАН. 2013;25:131-166.

For citation:


Zolotov V.A., Semenov V.A. On application of spatial decomposition method for large data sets indexing. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2013;25:131-166. (In Russ.)



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


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