| Today, a large amount of spatial data is generated from a variety of sources, such as mobile devices, sensors, and satellites. Traditional spatial data processing techniques no longer satisfy the efficiency and scalability requirements for large-scale spatial data processing. Existing Big Data processing frameworks such as Hadoop and Spark have been extended to support effective large-scale spatial data processing. In addition to processing data in distributed schemes utilizing computer clusters for efficiency and scalability, single node performance can also be improved by making use of multi-core processors. In this thesis, we investigate approaches to parallelize line segment intersection algorithms for spatial computations on multi-core processors, which can be used as node-level algorithms for distributed spatial data processing. We first provide our design of line segment intersection algorithms and introduce parallelization techniques. Then, we describe experimental results using multiple data sets and speed ups are examined with varying numbers of processing cores. Equipped with the efficient underlying algorithm for spatial computation, we investigate how to build a native big spatial data system from the ground up. We provide a system design for distributed large-scale spatial data management and processing using a two-level hash based Quadtree index as well as algorithms for spatial operations. |
