Back to search

University of British Columbia

Indexing on memory-constrained embedded devices

Abstract

dc:description

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 times tamps 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 B tree indexing, and there is a significant performance advantage for using storage-specific optimizations.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ould-Khessal, Nadir
Contributors dc:contributor
  • Lawrence, Ramon

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/88947

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Ould-Khessal, Nadir. Indexing on memory-constrained embedded devices. doctoral thesis, University of British Columbia, 2024. http://hdl.handle.net/2429/88947