Spatial Database Partitioning

The topic of the present study is aimed to investigate different techniques for partitioning data across multiple database nodes by multi-dimensional key. The objective of the project is to analyze existing methods of storing multidimensional data used in general purpose databases and custom in-house solutions to build a generic approach applicable to a set of spatial datasets. To measure the performance of any method two techniques can be used. Big O notation is essential to predict growth rates of algorithm's complexity and memory usage. The second approach is to measure the performance of well-known mutation operations and queries on open datasets or generated to be close to ones that require using multi-key queries as part of their business logic. The primary objective of the project is to reduce the growth rate of number database nodes from O(n) in a naive implementation of partitioning to O(log n) using a combination of traditional partitioning techniques with R family tree algorithms. The project activity will consist of analyzing datasets and operations on them that require multi-key partitioning due to their scalability requirements, implementing sophisticated and straightforward algorithms for this operations and measuring performance on that.