An Efficient Geometry Data Allocation Algorithm in Cloud Computing Environments

Abstract

The number of location-based services is growing and developing. Usually, these services put a huge amount of effort into geometry data computation. Thus, their workload is generally high. By exploring cloud computing techniques, one could utilize a number of computing nodes to distribute the workload of the systems. However, the workload is usually not equally balanced across computing nodes, if data is not well-distributed. To make the best use of computing nodes, we propose a sophisticated data distribution technology for geometry computation processing. Intuitively, one can simply divide geometry data into tiles so that the geometry data in each tile can be stored on one computing node. Unfortunately, since data in a tile shares spatial-proximity, processing a geometry computation on spatial-proximity data still incurs a huge workload. To address this issue, we propose a new data distribution approach, Reversed K-means, to distribute geometry data that shares spatial-proximity across different computing nodes. In this way, we can use more computing nodes to process geometry computation and get better performance. To evaluate the performance of our proposed algorithm, we evaluate the utility of computing nodes and the response time when performing geometry computations. The experimental results show that the utility of the computing nodes is higher than existing methods, and the response time is the fastest of all methods.