Indexing Points on Flash-based Solid State Drives using the xBR+-tree

  • Anderson Chaves Carniel Federal University of Technology - Paraná
  • George Roumelis University of Thessaly
  • Ricardo Rodrigues Ciferri Federal University of São Carlos
  • Michael Vassilakopoulos University of Thessaly
  • Antonio Corral University of Almeria
  • Cristina Dutra de Aguiar Ciferri University of São Paulo


Spatial database systems and Geographic Information Systems often employ spatial indices to speed up the processing of spatial queries. Currently, they are also interested in exploiting the positive characteristics of flash-based Solid State Drives (SSDs) like fast reads and writes. However, designing spatial indices for SSDs, termed flash-aware spatial indices, has been a challenging task because of the intrinsic characteristics of these devices. Among existing works in the literature, FAST and eFIND distinguish themselves by proposing general approaches that can be employed to design flash-aware spatial indices. In this article, we apply these approaches to the xBR+-tree, an efficient spatial index for points. The goal is to understand how they should be adapted in order to deal with the particular properties of the xBR+-tree. As a result, we specify two novel flash-aware spatial indices for points, the eFIND xBR+-tree and the FAST xBR+-tree. We also conduct a performance evaluation to analyze their performance. As main conclusion, we point out that eFIND fits very well with the xBR+-tree and allowed to reduce the processing of the index construction from 30.8% to 91.4% and the execution of spatial queries from 22.5% to 46%.


Download data is not yet available.

Author Biography

Anderson Chaves Carniel, Federal University of Technology - Paraná

Anderson Chaves Carniel is Assistant Professor in the Federal University of Technology - Paraná since 2019. He received the System Analysis and Development degree from Federal Institute of Education, Science and Technology of São Paulo, Brazil, in 2011. In 2014, he received the MSc degree in Computer Science from Federal University of São Carlos, Brazil, and in 2018, he received his PhD degree from Department of Computer Science at University of São Paulo in São Carlos, Brazil. His main areas of interest are spatial databases, geographic information systems, fuzzy spatial databases, spatial indexing, and database management on flash memories.