Spatial Indexing in Non-Volatile Memories: Proposal of an Efficient and Robust Spatial Index with Durability

• Grant number: 15/26687-8
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: June 01, 2016
• End date: December 31, 2018
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Cristina Dutra de Aguiar
• Grantee: Anderson Chaves Carniel
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Associated scholarship(s): 18/10687-7 - Porting disk-based spatial indices to flash-based solid state drives, BE.EP.DR

Abstract

Spatial database systems are largely used in the management of spatial objects that represent real-world phenomena by using points, lines, and regions. To improve the query processing involving spatial objects, spatial indices are used, such as the R-tree and its variants. These indices consider the magnetic disk as the main storage system. However, non-volatile memories, such as memories flash, have been adopted as the main storage system in mobile phones, laptops, and servers. Although the indices are easily portable to be applied to non-volatile memories, this approach would result in performance loss since it does not consider the unique characteristics of these memories, such as asymmetric performance between the write and read operations and high power consumption in write operations. Despite there are some spatial indices for non-volatile memories proposed in the literature, these indices have several limitations. The main one is the focus only on the efficiency of operations and the neglect to consider the durability of data, resulting in the possibility of data loss not persisted in non-volatile memory. Another limitation is that, to minimize the number of writes, existing indices introduce a great overhead in read operations, which may degrade the index robustness. Therefore, this PhD project aims to propose a spatial index that considers the unique characteristics of non-volatile memories and ensures efficiency, robustness, and durability in processing operations. Thus, we aim to propose an index with efficient processing time, low number of write operations, and durability. As a result, it is expected to advance the state of the art in spatial indexing corroborating the use of non-volatile memories as the main way to store spatial objects.

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

CARNIEL, ANDERSON C.; CIFERRI, RICARDO R.; CIFERRI, CRISTINA D. A.. A generic and efficient framework for flash-aware spatial indexing. INFORMATION SYSTEMS, v. 82, p. 102-120, MAY 2019. (15/26687-8, 18/22277-8)

CARNIEL, ANDERSON C.; CIFERRI, RICARDO R.; CIFERRI, CRISTINA D. A.. FESTIval: A versatile framework for conducting experimental evaluations of spatial indices. METHODSX, v. 7, 2020. (18/22277-8, 15/26687-8)

CARNIEL, ANDERSON CHAVES; CIFERRI, RICARDO RODRIGUES; DE AGUIAR CIFERRI, CRISTINA DUTRA; KIRIKOVA, M; NIRVAG, K; PAPADOPOULOS, GA. A Generic and Efficient Framework for Spatial Indexing on Flash-Based Solid State Drives. ADVANCES IN DATABASES AND INFORMATION SYSTEMS, ADBIS 2017, v. 10509, p. 15-pg., 2017-01-01. (15/26687-8)