A generic and efficient framework for flash-aware spatial indexing. (May 2019)

• Record Type: Journal Article
• Authors: Carniel, Anderson C.; Ciferri, Ricardo R.; Ciferri, Cristina D.A.
• Is Part Of: Information systems. Volume 82(2019)
• Page Start: 102
• Page End: 120
• Publication Date: 2019-05
• Subjects: Spatial indexing -- Spatial access methods -- Flash memory -- SSDs -- Flash-aware spatial index -- Spatial database systems; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2018.09.004
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: Spatial indexing on flash-based Solid State Drives (SSDs) has become a core aspect in spatial database applications, and has been carried out by flash-aware spatial indices . Although there are some flash-aware spatial indices proposed in the literature, they do not exploit all the benefits of SSDs, leading to loss of efficiency and durability. In this article, we propose eFIND, a new generic and efficient framework for flash-aware spatial indexing. eFIND takes into account the intrinsic characteristics of SSDs by employing (i) a write buffer to avoid expensive random writes, (ii) a flushing algorithm that smartly picks modifications to be flushed in batch to the SSD, (iii) a read buffer to decrease the overhead of random reads, (iv) a temporal control to avoid interleaved reads and writes, and (v) a log-structured approach to provide data durability . Performance tests showed the efficiency of eFIND. Compared to the state of the art, eFIND improved the construction of spatial indices from 43% to 77%, and the spatial query processing from 4% to 23%. Highlights: An efficient framework, called eFIND, that exploits the benefits of SSDs. eFIND transforms a disk-based spatial index into a flash-aware spatial index. A running example porting the R-tree to SSDs, creating the eFIND R-tree. An experimental evaluation to analyze the performance gains of eFIND. Performance tests that measure the effects of each design goal of eFIND.