Loading [MathJax]/extensions/MathMenu.js
Joint Index, Sorting, and Compression Optimization for Memory-Efficient Spatio-Temporal Data Management | IEEE Conference Publication | IEEE Xplore

Joint Index, Sorting, and Compression Optimization for Memory-Efficient Spatio-Temporal Data Management


Abstract:

The wide distribution of location-acquisition technologies has led to large volumes of spatio-temporal data, which are the foundation for a broad spectrum of applications...Show More

Abstract:

The wide distribution of location-acquisition technologies has led to large volumes of spatio-temporal data, which are the foundation for a broad spectrum of applications. Based on these applications’ performance requirements, in-memory databases are used to store and process the data. As DRAM capacities are limited and expensive, modern database systems apply various configuration optimizations (e.g., compression) to reduce the memory footprint. The selection of cost and performance balancing configurations is challenging due to the vast amount of possible setups consisting of mutually dependent individual decisions. In this paper, we present a linear programming approach to determine fine-grained configuration decisions for spatio-temporal workloads. By dividing the data into partitions of fixed size, we can apply the compression, sorting, and index selections on a fine-grained level to reflect spatiotemporal access patterns. Our approach jointly optimizes these configurations to maximize performance under a given memory budget. We demonstrate on a real-world dataset that models specifically optimized for spatio-temporal data characteristics allow us to reduce the memory footprint (up to 60% by equal performance) and increase the performance (up to 80% by equal memory size) compared to established rule-based heuristics.
Date of Conference: 19-22 April 2021
Date Added to IEEE Xplore: 22 June 2021
ISBN Information:

ISSN Information:

Conference Location: Chania, Greece
Citations are not available for this document.

I. Introduction

Spatio-temporal data reflects the trajectories of moving objects and enables the analysis of movement patterns, which are increasingly used in various applications. A moving object’s trajectory is represented by a chronologically ordered sequence of timestamped geographical coordinates accumulated by various positioning systems (e.g., GPS). To store and process spatio-temporal data is not a trivial task due to the massive volumes of continuously captured data and the need for interactive response times. The increased performance requirements of spatio-temporal data mining applications have shifted the data management to in-memory architectures [1]. Especially for main-memory optimized databases that keep the most data in relatively limited and expensive DRAM, a more efficient utilization of the available resources can significantly affect the operating costs [2]. While removing auxiliary data structures (e.g., indexes) or applying compression techniques with higher compression rates reduce the memory footprint, they equally affect the runtime performance. Modern database systems support fine-grained decisions for these configurations [3]– [7]. This approach enables applying different optimizations such as compression, indexing, and ordering configurations for various partitions of the data independently. All single configuration decisions have an impact on the overall memory consumption and runtime performance. Additionally, they mutually influence each other, which makes the determination of performance-optimized and memory-efficient configurations difficult [8], [9]. There are several general approaches in existing work that optimize specific aspects like the compression schema selection [2] or the selection of optimized index structures [10], [11]. As the different configuration decisions mutually influence each other, we seek to jointly optimize the compression, index, and ordering configuration to determine the best runtime performance for a given workload, data characteristics, and memory budget. Note, each of those individual tuning problems is, in general, already challenging. We are still able to address a joint optimization of these dimensions, as we exploit the specific characteristics of spatio-temporal data and applications, i.e., a limited number of columns and few query types. Further, to obtain a manageable problem complexity, we focus on single-attribute indexes.

Cites in Papers - |

Cites in Papers - Other Publishers (5)

1.
Nadir Guermoudi, Houcine Matallah, Amin Mesmoudi, Seif-Eddine Benkabou, Allel Hadjali, "Selectivity Estimation for\\xa0Spatial Filters Using Optimizer Feedback: A Machine Learning Perspective", Web Information Systems Engineering – WISE 2024, vol.15439, pp.101, 2025.
2.
Maryam Mozaffari, Anton Dignös, Johann Gamper, Uta Störl, "Self-tuning Database Systems: A Systematic Literature Review of Automatic Database Schema Design and Tuning", ACM Computing Surveys, 2024.
3.
Qingyu Meng, Kejia Zhang, Haiwei Pan, Maocai Yuan, Baoying Ma, "Design and Implementation of Key-Value Database for Ship Virtual Test Platform Based on Distributed System", Data Science, vol.1879, pp.109, 2023.
4.
Martin Boissier, "Robust and budget-constrained encoding configurations for in-memory database systems", Proceedings of the VLDB Endowment, vol.15, no.4, pp.780, 2021.
5.
Keven Richly, "Memory-Efficient Storing of Timestamps for Spatio-Temporal Data Management in Columnar In-Memory Databases", Database Systems for Advanced Applications, vol.12681, pp.542, 2021.
Contact IEEE to Subscribe

References

References is not available for this document.