Storing Massive TINs in a DBMS

Abstract

Solutions have been introduced to handle massive point clouds in Database Management Systems (DBMS), namely by Oracle in 2011 and postgreSQL in 2013. Many common operations on these massive point clouds require knowledge about the original surface in order to analyse them. A possible method to recreate a representation of the original surface is reducing a point cloud to a 2.5D structure such as a Triangular Irregular Network (TIN). This thesis explores the possibilities to store such massive TINs in a DBMS and presents criteria to define an efficient approach. The term ‘efficient’ is defined by the size of the data structure and the performance of spatial queries. Criteria for an efficient approach are developed by reviewing existing literature and comparisons of existing implementations. These criteria include: (1) the explicit storage of nodes of TIN, preventing duplicate information and resulting in small data structures. (2) the use of atomic functions such as slope, aspect and degree in order to enable analysis of the TIN inside the database. (3) the storage of topological relationships of the TIN, which is used for both atomic functions and spatial access to the TIN. (4) the use of buckets to split the TIN into non-massive sections that can be processed one at a time. A very large spatial index on each element of a TIN is therefore not needed. An index is only applied on the extents of the bucket. The TIN inside the bucket can be traversed using the topological relationships stored. The main problem encountered is to combine solutions for massive datasets with a TIN data structure, such as the use of buckets with a topological data structure. These problems are overcome by a novel data structure to store TINs in a DBMS called the Multistar. This data structure implements the aforementioned criteria for an efficient approach. The Multistar is compared in practice with the two existing database structures: the SDO_TIN by Oracle and the Simple Feature TIN type implemented in the PostGIS extension of PostgreSQL. This thesis shows that current implementations are not usable for both storing and accessing a massive TIN of 370M points. The Multistar is one of the smallest structures available and outperforms the other data structures significantly on massive TINs.