Porting disk-based spatial index structures to flash-based solid state drives

Author(s)

Carniel, Anderson Chaves ^[1] ; Roumelis, George ^[2] ; Ciferri, Ricardo R. ^[1] ; Vassilakopoulos, Michael ^[2] ; Corral, Antonio ^[3] ; Aguiar, Cristina D. ^[4]

Affiliation

^[1] Univ Fed Sao Carlos, Dept Comp Sci, BR-13565905 Sao Carlos, SP - Brazil

^[2] Univ Thessaly, Dept Elect & Comp Engn, Volos 38221 - Greece

^[3] Univ Almeria, Dept Informat, Almeria 04120 - Spain

^[4] Univ Sao Paulo, Dept Comp Sci, BR-13566590 Sao Carlos, SP - Brazil

• Document type: Journal article
• Source: GEOINFORMATICA; v. 26, n. 1 DEC 2021.
• Web of Science Citations: 0

Abstract

Indexing data on flash-based Solid State Drives (SSDs) is an important paradigm recently applied in spatial data management. During last years, the design of new spatial access methods for SSDs, named flash-aware spatial indices, has attracted the attention of many researchers, mainly to exploit the advantages of SSDs in spatial query processing. eFIND is a generic framework for transforming a disk-based spatial index into a flash-aware one, taking into account the intrinsic characteristics of SSDs. In this article, we present a systematic approach for porting disk-based data-driven and space-driven access methods to SSDs, through the eFIND framework. We also present the actual porting of representatives data-driven (R-trees, R{*}-trees, and Hilbert R-trees) and space-driven (xBR(+)-trees) access methods through this framework. Moreover, we present an extensive experimental evaluation that compares the performance of these ported indices when inserting and querying synthetic and real point datasets. The main conclusions of this experimental study are that the eFIND R-tree excels in insertions, the eFIND xBR(+)-tree is the fastest for different types of spatial queries, and the eFIND Hilbert R-tree is efficient for processing intersection range queries. (AU)

• FAPESP's process: 18/22277-8 - Processing of OLAP and SOLAP Queries on Parallel and Distributed Environments
• Grantee: Cristina Dutra de Aguiar
• Support Opportunities: Regular Research Grants