Hierarchical Quadrant Spatial LSM Tree for Indexing Blockchain-Based Geospatial Point Data

Abstract

Blockchain technology is attracting attention for its high usability in various fields such as IoT and healthcare, and it is being used as an alternative to distributed databases. Despite their high usability, the techniques for efficiently indexing blockchain-based geospatial point data have not been studied much until now. In this paper, we propose a hierarchical quadrant spatial LSM tree(i.e., HQ-sLSM tree) which effectively indexes large amounts of geospatial point data from the blockchain by reflecting its write-intensive feature. The geospatial point data is linearized using Geohash before being inserted into our proposed HQ-sLSM tree. Furthermore, we present the concept of a spatial filter which enables low disk I/O generating algorithms to process range and $k$ NN queries over the HQ-sLSM tree. Experiments confirmed that the HQ-sLSM tree performed exceptionally well for the insertion of point data, and the performance of range and $k$ NN query processing resulted second to the best after the R-tree.

Keywords

• Blockchain
• component table
• hierarchical quadrant spatial LSM tree
• kNN query
• LSM tree
• range query