On Managing Spatio-temporal Data Streams in NoSQL Databases

Abstract

This study is concerned with spatio-temporal streaming data management in NoSQL databases for IoT environments. An IoT system is a distributed wireless sensor network where smart objects, known as sensor nodes, are equipped with sensing and processing capabilities. These sensor nodes periodically capture the latest environmental signals and send the collected data to a central database, supporting various event stream monitoring and analytic applications.

We start by investigating the storage architecture for temporal data. When the number of sensor nodes is large and the sampling rate is high, the database faces a write-intensive workload. Log-structured merge trees (LSM-trees) are commonly adopted in many NoSQL systems in such scenarios because they significantly improve write performance. In many IoT applications, it is important to maintain both old and current versions of data. However, most proposed LSM-trees focus on storing a single version of data. In this study, we present our design and implementation of an enhancement to Google's LevelDB (an LSM-based single-node key-value store), called MVLevelDB, which efficiently supports temporal queries on multi-version streaming data. We formulate the log-structured multi-version tree (LSMV-tree) to be implemented in MVLevelDB. In LSMV-tree, each data version is associated with two timestamps to define its validity interval. Both data versions and components are time-sorted to improve search efficiency when processing temporal queries. To handle multi-component data versions, we design the data version duplication (DvD) method, in which a data key is duplicated in the next component if it is still valid while its component is being compacted. Extensive experiments using a benchmark program have been performed to compare the performance of MVLevelDB with LevelDB in both writing and reading data.

The study of MVLevelDB focuses on the storage layer's performance using a trivial IoT application-layer data model. It assumes data items arrive at the database in order, without loss or transmission delay. To explore temporal query semantics in an IoT environment, we introduce the concept of "temporal consistency of sensor data", which measures how consistent a sensor data item is with the real environment at a specific time instant. We then discuss how to provide relative consistency information for IoT application queries in the presence of transmission delays and potential data loss. We further extend MVLevelDB into MVLevelDB+, which includes four query processing methods that provide varying levels of relative consistency information or satisfy different query constraints. These methods are: Re-execution with Every Update (REU), Re-execution with Deadline (RED), Backward Execution Option (BEO) and Repeated BEO (RBEO). To support streaming data monitoring queries and implement the methods above, we designed the Query Pool with Execution State (QpES) mechanism. Experiments are conducted to show that the I/O performance is comparable to that of MVLevelDB, and various data temporal consistency related indicators of the REU, RED, BEO and RBEO methods are measured.

While MVLevelDB/MVLevelDB+ support only temporal data streams, we extend the study to efficiently index spatio-temporal data streams, which are common in IoT environments, such as GNSS trajectory data in Vehicle to Everything (V2X) systems. Given the potentially high frequency of location updates from multiple moving objects, the central database often operates under write-intensive conditions. Although many spatial index studies exist, few focuses on dynamically building the index in write-intensive scenarios in a real-time manner. This study introduces spatio-temporal index structures that can be constructed with low latency. Trajectories are categorized into two types for storage: "live" and "static". Live trajectories are indexed using the Dual-Key Encoding (DKE) scheme, where each data point is represented by two key-value entries, facilitating both ID-temporal and spatial queries. Static trajectories provide a more compact storage solution, reducing the overhead associated with live trajectories. Upon the completion of a trip, live trajectory data is transformed into a static trajectory entry through a compaction process. To enhance the efficiency of spatial index construction for static trajectories, we introduce a new encoding scheme, XS2, coupled with an adaptive segmentation policy, AdaptSeg, to optimize trajectory segmentation, thereby improving index building and query processing efficiency.

Date of Award	6 Jan 2025
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Kam Yiu LAM (Supervisor)