Search

Many large point clouds -- such as cosmological N-body simulations, intersections of road networks etc. -- are strongly clustered on a hierarchy of scales. In shared nothing distributed environments, optimized tiling of data is crucial to minimize cross-server communication and balance IO and processing load. We propose histogram-based tiling algorithms, a hierarchical tiling and a spectral clustering algorithm, that can be incorporated into the data extraction or transformation phase of a typical Extraction--Transformation--Loading (ETL) procedure. We define measures to characterize the performance of these tiling techniques with respect to typical spatial search operations, and evaluate the algorithms based on these measures using hierarchically clustered data sets.

We introduce the concept of the point cloud database, a new kind of database system aimed primarily towards scientific applications. Many scientific observations, experiments, feature extraction algorithms and large-scale simulations produce enormous amounts of data that are better represented as sparse (but often highly-clustered) points in a k-dimensional (k ≲ 10) metric space than on a multi-dimensional grid. Dimensionality reduction techniques, such as principal components, are also widely-used to project high dimensional data into similarly low dimensional spaces. Analysis techniques developed to work on multi-dimensional data points are usually implemented as in-memory algorithms and need to be modified to work in distributed cluster environments and on large amounts of disk-resident data. We conclude that the relational model, with certain additions, is appropriate for point clouds, but point cloud databases must also provide unique set of spatial search and proximity join operators, indexing schemes, and query language constructs that make them a distinct class of database systems.