Spatial Partitioning Techniques in Spatial Hadoop

SpatialHadoop is an extended MapReduce framework that supp orts global indexing that spatial partitions the data across machines providing orders of magnitude speedup, compared to traditi onal Hadoop. In this paper, we describe seven alternative partit ioning techniques and experimentally study their effect on the qua lity of the generated index and the performance of range and spatial join queries. We found that using a 1% sample is enough to produce high quality partitions. Also, we found that the total area o f partitions is a reasonable measure of the quality of indexes when r unning spatial join. This study will assist researchers in cho osing a good spatial partitioning technique in distributed enviro nments. 1. INDEXING IN SPATIALHADOOP SpatialHadoop [2, 3] provides a generic indexing algorithm which was used to implement grid, R-tree, and R+-tree based p artitioning. This paper extends our previous study by introduci ng four new partitioning techniques, Z-curve, Hilbert curve, Quad tree, and K-d tree, and experimentally evaluate all of the seven techn iques. The partitioning phase of the indexing algorithm runs in thr ee steps, where the first step is fixed and the last two steps are customiz ed for each partitioning technique. The first step computes number of desired partitionsn based on file size and HDFS block capacity which are both fixed for all partitioning techniques. The second st ep reads a random sample, with a sampling ratio ρ, from the input file and uses this sample to partition the space into cells such that number of sample points in each cell is at most ⌊k/n⌋, wherek is the sample size. The third step actually partitions the file by as signing each record to one or more cells. Boundary objects are handle d using either thedistribution or replication methods. Thedistribution method assigns an object to exactly one overlapping cell and the cell has to be expanded to enclose all contained records. The replication method avoids expanding cells by replicating each record to all overlapping cells but the query processor has to employ a duplicate avoidance technique to account for replicated records . ∗This work is supported in part by the National Science Founda tion, USA, under Grants IIS-0952977 and IIS-1218168 and the University of Minnesota Doctoral Disseration Fellowship.  To view a cop y f this license, visit http://creativecommons.org/licenses/by-n c-nd/3.0/. Obtain permission prior to any use beyond those covered by the license. Contact copyright holder by emailing info@vldb.org. Articles fromthis volume were invited to present their results at the 41st Internatio l Conference on Very Large Data Bases, August 31st September 4th 2015, Koha la Coast, Hawaii. Proceedings of the VLDB Endowment, Vol. 8, No. 12  We use Hadoop 1.2.1 running on Java 1.6 and CentOS 6. Each machine is configured to run three mappers and two reduce rs. Tables 1 and 2 summarize the datasets and configuration param eters used in our experiments, respectively. Default parame ters (in parentheses) are used unless otherwise mentioned. In the fo llowing part, we describe the partitioning techniques, the quer ies we run, and the performance metrics measured in this paper.  This paper employsgrid and Quad tree as space partitioning techniques;STR, STR+, and K-d tree as data partitioning techniques; andZ-curve andHilbert curve as space filling curve (SFC) partitioning techniques. These techniques can also be grou ped, according to boundary object handling, into replication-based techniques (i.e., Grid, Quad, STR+, and K-d tree) and distributionbased techniques (i.e., STR, Z-Cruve, and Hilbert).  1 illustrates these techniques, where sample points and partition bou daries are shown as dots and rectangles, respectively. 1. Uniform Grid: This technique does not require a random sample as it divides the input MBR using a uniform grid of ⌈√n⌉ × ⌈√n⌉ grid cells and employs the replication method to handle boundary objects. 2. Quad tree: This technique inserts all sample points into a quad tree [6] with node capacity of ⌊k/n⌋, wherek is the sample size. The boundaries of all leaf nodes are used as cell boundaries. W use the replication method to assign records to cells. 3.  This technique bulk loads the random sample into an Rtree using the STR algorithm  and the capacity of each node is set to⌊k/n⌋. The MBRs of leaf nodes are used as cell boundaries. Boundary objects are handled using the distribution method where it assigns a record r to the cell with maximal overlap. 4.  This technique is similar to the STR technique but it uses the replication method to handle boundary objects. 5. K-d tree: This technique uses the K-d tree  partitioning method to partition the space into n cells. It starts with the input MBR as one cell and partitions it n − 1 times to producen cells. Records are assigned to cells using the replication method. 6. Z-curve: This technique sorts the sample points by their order on the Z-curve and partitions the curve into n splits, each containing roughly⌊k/n⌋ points. It uses the distribution method to assign a recordr to one cell by mapping the center point of its MBR to one of then splits. 7. Hilbert curve: This technique is exactly the same as the Zcurve technique but it uses Hilbert space filling curve which has better spatial properties. (a) Grid (b) Quad Tree (c) STR and STR+ (d) K-d Tree (e) Z-curve (f) Hilbert Curve  Partitioning Techniques. Examples of nearly-empty partitions are starred. Name Size Records Average Record Size All Objects 88GB 250M 378 bytes Buildings 25GB 109M 234 bytes Roads 23GB 70M 337 bytes Lakes 8.6GB 9M 1KB Cities 1.4GB 170K 8.4KB