On application of spatial decomposition method for large data sets indexing
Abstract
This paper is devoted to the elaboration of spatial indexing methods implemented by means of decomposition technique. Special attention is given to decomposition based on regular octrees, which is known to provide efficient solution for collision detection and spatial query problem and being applicable not only to sets of point data, but also to spatially extended objects. Based on probabilistic analysis, complexity estimations are evaluated for model set of data. They generalize previous results and serve as theoretical background to wide practical application of discussed methods.
About the Authors
V. A. Zolotov
ISP RAS, Moscow
Russian Federation
Russian Federation
V. A. Semenov
ISP RAS, Moscow
Russian Federation
Russian Federation
References
1. Cai M., Revesz P. Parametric rectangles: an index structure for moving objects. 2000. Proceedings of the 10th COMAD International conference on management of data.
2. Semenov V.A., Kazakov K.A., Morozov S.V., Tarlapan O.A., Zolotov V.A., Dengenis T. 4D modeling of large industrial projects using spatio-temporal decomposition. [ed.] K. Menzel и R. Scherer. London, UK : CRC Press, Taylor & Francis Group, 2010. eWork and eBusiness in Architecture, Engineering and Construction. pp. 89-95.
3. Zolotov V.A., Semenov V.A. Sovremennye metody poiska i indeksatsii mnogomernykh dannykh v prilozheniyakh modelirovaniya bol'shikh dinamicheskikh stsen [Advanced indexing methods for large multidimentional data in complex dynamic scenes]. Trudy ISP RАN [The Proceedings of ISP RAS], 2013, vol. 24, pp. 381-416. (in Russian)
4. Kedem G. The quad-CIF tree: a data structure for hierarchical on-line algorithms. 1992. Proceedings of the 19th Design Automation Conference. pp. 352-357.
5. Finkel R.A., Bentley J.L. Quad trees: a data structure for retrieval on composite keys. Acta Informatica. 1974, vol. 4, 1, pp. 1-9.
6. Semenov V.A., Kazakov K.A., Zolotov V.A., Jones H., Jones S. Combined strategy for efficient collision detection in 4D planning applications. [ed.] W. Tizani. Nottingham, UK : Nottingham University Press, 2010. Computing in Civil and Building Engineering. pp. 31-39. ISBN 978-1-907284-60-1.
7. Gottschalk S., Lin M. C., Manocha D. OBB Tree: a hierarchical structure for rapid interference detection. New Orleans, USA, 1996. Proceedings of the SIGGRAPH'96 Conference. pp. 171-180.
8. Gottschalk S. Collision queries using oriented bounding boxes. Chapel Hill : The University of North Carolina, 2000.
9. Samet H. Foundations of Multidimentional and Metric Data Structures. San Francisco : Morgan Kaufmann, 2006.
Review
For citations:
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.)
Email this article 