HGrid A Data Model for Large Geospatial Data Sets in HBase

Editor's Notes

• #3: Cloud Computing, is attracting business owners for the perceived benefits, Such as 1 Elasticity which provides on-demand service based on the fluctuating load -- example 2 Excellent system scalability -- there is no limit to storage 3 Low latency and high availability of service. -- latency is a strange thing to discuss… Given these advantages, some enterprises have been working on migrating the legacy applications to the cloud. Currently, the majority of applications deployed in the cloud include social networking, online shopping, monitoring system. In these applications, the data grows monotonously over time. In order to improve the existing services and discover new knowledge, business owners are committing substantial budgets on Analysis of these large time-series data, ranging from simple descriptive statistics to complex analytics. In this movement, the success adoption requires a new model of storage.
• #7: Therefore, to address these challenge in this migration, we aim to develop a systematic method for guiding data organization in NoSQL databases, given the data type, the data size and its usage pattern. We start our investigation with HBase, which is a NoSQL database offering. It is built on top of Hadoop. It provides two frameworks for parallel distributed computation. One is MapReduce, and the other one is Coprocessor. MapReduce is very effective for distributed computation over data stored within its tables, But in many cases, for example, simple additive or aggregating operations like summing, counting, Coprocessor can give a dramatic performance improvement over HBase’s already good scanning performance. Therefore, we used Coprocessor implementation in our experiment.
• #12: Both of them investigate how to access the multidimensional data efficient with spatial indices, which is a part of problem that we are addressing in this paper. Their methods demonstrate efficient performance with the spatial indices. However, both only focus on the row key design in HBase for data organization, there is little discussion about the column and version design. To work out an appropriate data model for geospatial datasets which can be easily and directly applied to the location-based applications, in addition of the row key, we also take column and version into account to model the data in HBase. Furthermore, we implemented the queries with HBase Coprocessor to harness the parallelism benefits, while the above studies processed the queries with HBase Scan.
• #14: It relies on a regular-grid index. The row key is the row index of the cell in the grid, the column is the column index of the cell, Version: counter of objects. So we can see the third dimension holds a stack of data points located in the same grid cell. Value: each storage cell represents one object in JSON format holding all other attributes and values
• #15: It relies on a trie-based quad-tree index. Applies Z-ordering to transform the two-dimensional spatial data into an one-dimensional array. In this model, the row key, is Z-value. The column is the object id which locates in the cell. Usually people encode the cells with binary digits. But as the row key should be short in HBase, we use decimal encoding here.
• #16: QT If the index is built in real time for each query, the construction cost dominates many small queries. If the index is maintained in memory, the granularity of the grid is limited by the amount of memory available, since the memory needed to maintain the index increases as the depth of the tree increases and the size of the grid cells becomes smaller. RG The third dimension holds a stack of data points located in the same grid cell, and an index is maintained to keep the count of objects in each cell stack in order to support updates.
• #17: 1) the data-set space is divided into equally-sized rectangular tiles T, encoded with their Z-value. 2) the data points are organized in a regular grid of continuous uniform fine-grained cells. In this model, each data point is uniquely identified in terms of its row key and column name.
• #18: The row key is the concatenation of the quad-tree Z-value and the Regular Grid row index. The column name is the concatenation of the Regular Grid column and the object id of the data point. The attributes of the data point are stored in the third dimension.
• #19: Range queries are commonly used in location based applications. Given the coordinates of a location and a radius, a vector of data points, located within a distance less or equal to the radius from the input location is returned. Relying on the HGrid data model, to answer this query the following process is followed:
• #20: In this example, four tiles are involved. If the query is computed in one call, the scan range is from 03 to 09, and it will include the irrelevant tiles “04,05,07,08,10,11”. Therefore, instead of triggering one query, we split them into four sub-queries, and each sub-query corresponds to one tile. The sub-queries are called in sequence, and in each sub-query, the query is executed by coprocessor in parallel.
• #21: In this example, four tiles are involved. If the query is computed in one call, the scan range is from 03 to 09, and it will include the irrelevant tiles “04,05,07,08,10,11”. Therefore, instead of triggering one query, we split them into four sub-queries, and each sub-query corresponds to one tile. The sub-queries are called in sequence, and in each sub-query, the query is executed by coprocessor in parallel.
• #22: In this example, four tiles are involved. If the query is computed in one call, the scan range is from 03 to 09, and it will include the irrelevant tiles “04,05,07,08,10,11”. Therefore, instead of triggering one query, we split them into four sub-queries, and each sub-query corresponds to one tile. The sub-queries are called in sequence, and in each sub-query, the query is executed by coprocessor in parallel.
• #23: In this example, four tiles are involved. If the query is computed in one call, the scan range is from 03 to 09, and it will include the irrelevant tiles “04,05,07,08,10,11”. Therefore, instead of triggering one query, we split them into four sub-queries, and each sub-query corresponds to one tile. The sub-queries are called in sequence, and in each sub-query, the query is executed by coprocessor in parallel. But still within a coprocessor tile, irrelevant regular-grid cells will be seen, so we filter them out
• #24: Have not got a better way to describe this algorithm
• #25: Our experiments were performed on a four-node cluster, running on four virtual machines on an Openstack Cloud. The virtual machines run 64bit Ubuntu 11.10 and have 2 cores, 4GB of RAM, and a 200 GB disk. We used Hadoop version 1.0.2, and HBase version 0.94. Hadoop and HBase were each given 2GB of Heap size in every running node. Configurations: 1) HDFS was configured with a replication factor of 2. 2) The data was compressed with gzip. 3) the ROWCOL filter was applied on each table. 4) The scan cache size was set to 5K and the block cache was set to true, for the query processing. We implemented the Range Query processing with the Coprocessor framework and KNN with Scan in order to examine the implications of these different implementations to performance.
• #26: Across these three data models, a common configuration parameter is the size of each cell, which determines the granularity of grid. This is a very important variable which substantially affects the query-processing performance. Therefore, before we compare the three data models against each other, we have explored the best cell configuration for each model. We varied the size of the cell to observe how the different sizes of cell affect the performance of each data model. Result: In our experiments, for the QT data model, the appropriate cell configuration was 1, while for the RG data model the acceptable cell size was 0.1.
• #27: We evaluated range query performance under three data models with both uniform and Zipf distribution data. The table shows the query response time of the three data models for various ranges when the system contains 100 million objects. As the radius increases, the size of irrelevant data vs the return-set size ration increases, the running time also increases because more data points are retrieved. Comparing the three models, we can see that the regular-grid data model outperforms the others. Because it supports better data locality, it demonstrates better performance since the percentage of irrelevant rows scanned is low. The HGrid data model is much better than quadtree data model and worse than the regular-grid data model. The same performance trends persist with both uniform and skewed data.
• #28: We now evaluate the performance for k Nearest Neighbor (kNN) queries using the same data set, under the three data models. This table shows the response time (in seconds) for kNN queries, where k takes the values 1, 10, 100, 1,000, and 10,000. As the density-based range estimation method is employed , there is only one scan operation in the query processing for uniform data, while for skewed data, more than one scan iterations are invoked to retrieve the data. That is why the performance with skewed data under all data models is a little worse than that with the uniform data set. For both uniform and skewed data, the Regular-grid data model demonstrates best performance among the three data models; the HGrid data model come second with slightly worse performance than the regular-grid data model; and the quadtree data model is outperformed by the other two. The poor locality preservation, due to the Z-order linearization method, contributes to the poor performance of the quadtree data model, and also impacts the performance of HGrid, albeit less strongly. For skewed data, with too many false positives, the query with the data points having more than 70% probability cannot get the result below the timeout threshold under all data models when k equals to 10K. To improve performance, a finer granularity is required to filter irrelevant data scanning.
• #29: In summary, the query performance of the HGrid data model is better than the quadtree data model and worse than the RG data model. Benefits the good locality of the second-tier regular-grid index, while at the same time suffering from the poor locality of the Zordering linearization at the first tier. Better performance can potentially be obtained with alternative linearization techniques. For skewed data, the HGrid behaves better with an appropriate configuration, while the regular-grid and QT data models are subject to memory constraints. Can be flexibly configured and extended 1) The quad-tree index can be replaced by the hash code of each sub-space 2) The point-based quad-tree index method is employed. 3) The granularity in the second stage can be varied from sub-space to sub-space based on the various densities. Therefore, HGrid is more scalable and suitable for both homogeneously covered and discontinuous spaces.
• #31: The row key and column name should be short, since they are stored with every cell in the row. It is better to have one column family, only introducing more column families in the case where data access is usually column scoped. The number of columns should be limited. A number in the hundreds is likely to lead to good performance. The amount of data in one row should be kept relatively small. The cost (in time) of retrieving a row has n data increases more than twice with n [12]. The row key should be designed to support pruning of unrelated data easily. When the third dimension is used for storing other information rather than time-to-live values, it is preferable to keep it shallow, and be limited to containing up to no more than hundreds of data points, as deep stacks lead to poor insertion performance. The Bloom Filter [10] should be configured as it can accelerate the performance by pruning the data from both row and column sides. Compression can improve the performance by reducing the amount of data transmission.
• #32: Scan operations are preferable to Get operations for retrieving discontinuous keys, even though the Scan result is bound to also include data points that are not part of the response data set. It is more efficient to Get one row with n data points than n rows with one data point each [12]. It is advisable to narrow the range of queried columns with the Filter mechanism. The number of rows to be scanned for a query should not exceed the scan cache size, which depends on client and server memory. Otherwise, it is better to split the query into several sub-queries. When there are too many unrelated rows within the defined scan range, splitting one query into multiple sub-queries with multiple Scan operations is more efficient than one query with Filter mechanism to retrieve rows one by one. The Scan operation is preferable for small queries, while Coprocessor should be used for large queries.
• #33: Can be flexibly configured and extended 1) The quad-tree index can be replaced by the hash code of each sub-space 2) The point-based quad-tree index method is employed. 3) The granularity in the second stage can be varied from sub-space to sub-space based on the various densities. Therefore, HGrid is more scalable and suitable for both homogeneously covered and discontinuous spaces.