We live in the era of big data. Huge amounts of complex information, such as spatial data, are being generated daily by organizations, the industry and individuals at an increasing rate. At the same time, distributed and cloud computing systems are becoming more eficient, more available and with cheaper memory than ever. Thus, they are being established as the leading tool for big data management. The goal of this doctoral work is to research and design novel scalable techniques that will support fast query processing on spatial data in a distributed environment. First, we aim to create new techniques that will simplify operations performed when processing complex spatial objects such as polygons, while simultaneously retaining result accuracy. Additionally, we study memory management mechanisms for individual machines, while optimizing size and performance trade-ofs. Finally, we discuss the challenges of a distributed environment and provide ways to use optimized spatial data management techniques while ensuring scalability.
Spatial data management has been widely studied for the last forty years [1, 5], with an increased interest lately due to the large amounts of data that are generated daily. Spatial data refers to geometrical objects such as points, lines, polygons etc. that can be used to represent real world entities like buildings, lakes or points of interest (restaurants, banks etc.). They are usually generated and handled by Geographic Information Systems (GIS) that have to efectively organize and manage large quantities of such data, in order to use it commercially and scientifically.
Some of the most commonly used query types on spatial data include intersection joins (pairs of objects that intersect) [2], within joins (pairs of objects that the first is completely inside of the second), range queries (objects that intersect a given rectangular or polygonal area), distance joins (pairs of objects with less than a specified maximum distance between them) and -nearest neighbors (the geographically closest objects to the target object).
Resolving spatial queries is usually done in two steps: the filter and the refinement stages [1]. The ifrst step filters a large portion of the data through simple operations, so that only a small amount of candidates will move on to the expensive refinement phase. In the second step, the objects are geometrically checked with one another to identify their relationship, which can be proved costly for complex geometries such as polygons.
When dealing with such geometries, the filter step usually processes some approximation of the objects (instead of their original geometries) and they are usually stored into hierarchical indices such as R-tree [3] or quadtree [4]. For example, polygons can be processed roughly using their Minimum Bounding Rectangles (MBRs), which are far more simpler to operate upon. There have been many approximations throughout the years (Convex Hull, 5C, Maximum Enclosed Rectangle and more) [5, 6], each one with its own attributes and various applicability on diferent query types.
Additionally, the concurrent progress and increased availability of distributed and cloud computing systems in the last couple of decades, has rendered them a powerful tool for big data management [7]. Techniques that partition the data to worker nodes which in turn can process it independently and simultaneously with one another, enable processing huge volumes of data in an environment with larger collective memory.
and point-in-polygon tests (for intersection and con- 3.1. Raster Intervals Polygon tainment, respectively). Thus, being able to reduce Approximation the total refinement workload is crucial when attempting to improve query evaluation time. We have created a novel approximation technique
Additionally, tree-based spatial indices are not fit for polygons called Raster Intervals(RI) [8], which for highly dynamic data due to their large update has been proven to perform well in intersection and cost. Approximations other than the MBR, are within joins. Additionally, it has the prospect to usually not stored in such indices. Instead, they work well for range queries in which the window are used in an intermediate filter right after the may not only be a rectangle, but also a complex MBR-filtering stage, to further reduce the refine- polygon. ment candidates. However, not all approximation perform well and they are usually able to detect either true hits or true negatives, but not both.
Distributed commercial and scientific GIS (Apache Sedona, Spatial Hadoop, SIMBA, Magellan), cloud data warehousing services (Amazon Redshift) and companies that generate and use spatial data daily for their services (Twitter, Uber, Google), have an increasing demand for fast and scalable spatial data processing. Figure 1: How grids of diferent granularity create vari
To increase parallelism, distributed systems must ously detailed approximations. partition the data in a way that allows as much of the work as possible to be done independently RI are created through a pre-processing of the by the worker nodes. For diferent data types how- original data by rasterizing each object using a ever, this adds new challenges and is not always global grid and then ordering each cell using the clear what partitioning method performs best for Hilbert Curve [10]. Grid granularity not only afeach query type. Geometrical approximations can fects the detail of each approximation but also the be useful for data homogeneity and detecting true size in bytes it requires in memory (Figure 1). A negatives faster, but they can not always identify granularity of 216 × 216 is usually enough, however true positives so they tend to lack in accuracy. depending on data distribution and space, more
Additionally, most spatial data management sys- detailed grids may be necessary. Then, consecutive tems focus on partitioning the data efectively, with cell identifiers are merged to create the intervals. little to no optimization done on a single machine. Additionally, a cell may be only partially covered by Our ultimate goal is to study scalable ways to pro- the original geometry, so extra information about cess spatial data in a distributed environment and each cell has to be taken into account in order to to face the challenges it establishes. use the approximation for accurate results.
In this section we discuss the main goals of this doctoral research and how we deal with the previously mentioned challenges. It focuses on two individual aspects of distributed big data management: the techniques of processing queries on spatial data and the application of such methods in a distributed environment, while ensuring scalability.
The performance of single node query processing can benefit from novel indexing techniques and specialized data type-focused approaches [5, 8, 9], as well as certain polygon approximations that can speed up the query evaluation by reducing the amount of objects that need to be geometrically refined.
Inspired by the Raster Approximation [11], we use a modified classification for each cell, depending on the percentage of its area that overlaps with the original geometry: Full (100%), Strong (> 50% ), full strong weak Weak (≤ 50%), as seen in Figure 2. This means that two objects. However, this method is used as an only Strong-Weak, Weak-Strong and Weak-Weak intermediate filter in the pipeline, rather than the cases need to be further refined, while the rest of ifrst step of the whole process. It still depends on the cases can be safely either accepted or rejected. an MBR filter such as the Two-Layer Partitioning
In order to store this information in a compressed [9] to discard pairs of irrelevant objects. manner, a unique binary code is assigned to each To tackle the unavoidable added cost of the incase, depending on which one of the two data sets is termediate filter, we will also investigate a modified currently being processed (Table 1). We then glue version, in which we separate and duplicate the together the cell codes for each interval, creating a main intervals (ALL-intervals), so that we have single interval coding for it. Therefore each object any Full-Strong-only (FS -intervals) and Full-only is now represented by a set of intervals and a set of (F -intervals) cases as separate sets. Then, after their respective codings. detecting an overlap in a pair’s ALL-intervals, the iflter will check for overlaps in the SF -intervals, folinput input lowed by the ALL-F and F -ALL types of intervals respectively for each set.
RI can also be used in range queries on polygonal data, by creating the RI approximation of the selection window and efectively joining it with a collection of objects. Instead of comparing the window’s shape with the actual polygonal geometry, we detect interval overlaps between the window’s and the polygons’ approximations. Since the performance of a range query increases in relation to the window’s shape and complexity, the RI approximation works pretty well for complicated, polygonal windows by reducing it into a set of integer tuples.
RI may generate many intervals for large polygons or high granularity, which results in too much memory usage. By compressing the interval array we can save space, with low decompression overhead and without afecting the evaluation time too much.
Variable byte compression (Vbyte) is extremely popular and has been proven to achieve good ratio and decompression speed [12, 13]. It is a byte-aligned 3.2. Distributed Query Processing compression scheme for integers in which seven bits One of the major challenges found in distributed of a byte are used to represent a number and the spatial data management, is data partitioning. The eighth bit is used to indicate whether or not more worker nodes must be able to process queries on bytes follow for that same number (1 if yes, else 0). their assigned data with minimal dependence to The decompression is performed by removing the data partitioned across the other nodes. least (or in some versions the most) significant bit and concatenating the septets of bits together. 3.2.1. Partitioning
By employing SIMD instructions for faster binary operations, Vbyte can achieve even better perfor- Grid. Grid partitioning works quite well, since it asmance for large arrays of integers [14]. However signs diferent sections (cells) of the total geographic they are not particularly useful in our case, since area to nodes and they only process objects that lie an object will usually have a number of intervals on their designated areas. Nearby cells are usually ranging from dozens to a few hundreds, unless cre- assigned to diferent worker nodes, so that objects ated using a very high granularity grid (larger than concentrated in that area (and are thus likely to 217 × 217). participate as pairs in a query) are distributed to more than one worker nodes, enabling the system 3.1.2. Intersection/Within Joins to utilize more of its resources in each case. Trees. Similarly to a grid, trees can also be used The RI approximation can be used in intersec- to partition data. KD-trees [15] for points or R-trees tion/within joins for real world applications. Instead [3] for polygons successfully divide space and sameof comparing the original geometries of polygons, level areas can be partitioned across a collection which as described previously is really expensive, of nodes, so that each worker works on a specified possible interval overlaps are detected and their data region. However, load balancing on tree-based codes are compared to assess the situation between partitions is greatly depended on query type. For example, in intersection joins it might work well since the participating data sets are joined in their entirety. But in range queries, where a certain area is specified, all the workload might be put on a single machine, depending on data distribution.
Duplicate Detection. In both partitioning methods discussed, geometries usually intersect more than one of the designated sections, so duplicate entries are distributed across the system and may afect the final result and the total processing time. A duplicate detection mechanism must exist and it is usually done by either assigning each object to exclusively one section [16] through a pivot point or by minimizing the amount of checks for each object during the query processing[9].
Approximation Partitioning Considering that the de-duplication mechanism usually takes place in the MBR filter, we will focus on scalable intermediate filters for diferent types of queries and spatial data, since the refinement phase is what takes up 99% of the total evaluation time has the greatest room for improvement. For example, each node can use the Raster Intervals approximation in an intermediate filter, independently of how the data has been partitioned (i.e. the intermediate filter does not include the de-duplication mechanism).
Additionally, we will investigate how well the grid partitioning performs for diferent approximations and queries, since it achieves considerably better workload balancing than trees.