LB-Grid: An SSD efficient Grid File

Abstract

Recent advances in non-volatile memory technology have led to the introduction of solid state drives (SSD). NVMe SSDs are the latest development in flash based solid state drives and they were designed as a means of low latency and high bandwidth. Many research studies seek for taking advantage of this new technology to accelerate data management. Multidimensional indexes are fundamental for the efficiency of spatial query processing. In this work, we study the implication of high performance NVMe drives on spatial indexing. More specifically, we present an in-depth performance analysis of the Grid File in flash storage and we introduce LB-Grid, a write efficient variant of Grid File for flash based solid state drives. We present new query algorithms for both LB-Grid and Grid File that exploit the high internal parallelism and I/O bandwidth of NVMe SSDs. Experimental results unveil the efficiency of the proposed algorithms. Utilizing a test set of 500M points, LB-Grid appears to be up to 2.26 times faster than Grid File, up to 5.5 times faster than the R∗-tree, and up to 3.3 times faster than the FAST-Rtree in update intensive workloads. On the other hand, the Grid File presents better performance in read intensive workloads; exploiting a batch read operation, it achieves a speedup up to 10.2x in range queries, up to 1.56x in kNN and 4.6x in group point queries. © 2019 Elsevier B.V.