Dissertation Defence: Indexing on Memory-Constrained Embedded Devices

Nadir Ould-Khessal, supervised by Dr. Ramon Lawrence, will defend their dissertation titled “Indexing on Memory-Constrained Embedded Devices” in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science.

An abstract for Nadir Ould-Khessal’s dissertation is included below.

Examinations are open to all members of the campus community as well as the general public. This examination will be offered in hybrid format.  Registration is not required to attend in person, but please email ramon.lawrence@ubc.ca to receive the Zoom link for this defence.

---

ABSTRACT

Small devices used for agricultural, environmental, and industrial monitoring are typically built around embedded systems with limited computational power and memory. As these devices play a crucial role in data collection, there is a pressing need for optimizations to enhance on-device data processing, thereby reducing network transmissions, energy consumption, and data storage requirements. The most common type of data collected by these embedded devices is in the form of time series, encompassing environmental metrics like temperature and humidity, or operational data from sensors linked to machinery and electronics. Processing such time series datasets necessitates indexing both the sequentially increasing timestamps and the non-sequential data values. While database indexes such as the popular B-tree have been adapted to flash storage on servers and solid-state drives, these optimizations typically demand hardware and memory resources beyond what is available on embedded devices. This work introduces both index types for memory-constrained embedded devices. For sequential indexing, the Sequential Binary Index for Time Series (SBITS) is introduced and evaluated against prior embedded indexes that used sorted files, trees, and hashing. The other contribution of this work is the development and experimental evaluation of flash-based indexes including multiple storage-specific variants of the B-tree such as the VMtree. Experimental results demonstrate that even the smallest devices can perform efficient Btree indexing, and there is a significant performance advantage for using storage-specific optimizations.