An effective spatial join method for blockchain-based geospatial data using hierarchical quadrant spatial LSM⁺ tree

The prevention of forgery and alternation of important data of blockchain technology is contributing widely to the expanding usage of this technology to areas and industries such as real estate and agriculture. Despite the high utilization of the blockchain, its write-intensive feature causes a large amount of disk I/Os when trying to index and process queries over the data. Among previous studies, the hierarchical quadrant spatial LSM tree (i.e., HQ-sLSM tree) was proposed as an effective structure to index large amounts of geospatial point data from the blockchain and process queries while triggering a low number of disk I/Os. However, geospatial data exist in forms such as lines and polygons inside cadastral maps and survey information. In this paper, we propose an extended version of the HQ-sLSM tree which indexes geospatial line and polygon data. The extended tree, named the HQ-sLSM\(^{+}\) tree, inherits and adapts some common features and the low disk I/O algorithms of the original HQ-sLSM tree, fitting them to the line and polygon data types. Furthermore, an algorithm to process the spatial join query over two HQ-sLSM\(^{+}\) trees is proposed. A concept of a spatial join filter is introduced to access disk components efficiently. Experiments confirmed that the number of disk I/Os triggered when spatially joining two HQ-sLSM\(^{+}\) trees was much less compared to existing baseline index trees such as the R-tree and the LSM R-tree.