Indexing on memory-constrained embedded devices
department or school: Science, Irving K. Barber Faculty of (Okanagan)
department or school: Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
data provider: DSpace
degree campus: UBCO
creator: Ould-Khessal, Nadir
issued: 2024-08-15T18:14:28Z
issued: 2024
related degree: Doctor of Philosophy - PhD
degree grantor: University of British Columbia
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.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/88947
note: Indexing on Memory-ConstrainedEmbedded DevicesbyNadir Ould-KhessalM.Eng., University of BoumerdesDiploˆme de Post Graduation Specialise DPGS, Centre de Developpment desSyste`mes Energe´tiques -C.D.S.EA DISSERTATION SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe College of Graduate Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)August 2024© Nadir Ould-Khessal, 2024The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a dissertation entitled:Indexing on Memory-Constrained Embedded Devicessubmitted by Nadir Ould-Khessal in partial fulfilment of the require-ments of the degree of Doctor of PhilosophyDr. Ramon Lawrence, Irving K. Barber Faculty of ScienceSupervisorDr. Yves Lucet, Irving K. Barber Faculty of ScienceSupervisory Committee MemberDr. Khalad Hasan, Irving K. Barber Faculty of ScienceSupervisory Committee MemberDr. Zheng Liu, School of EngineeringUniversity ExaminerDr. Ioanis Nikolaidis, University of AlbertaExternal ExamineriiAbstractSmall devices used for agricultural, environmental, and industrial mon-itoring are typically built around embedded systems with limited compu-tational power and memory. As these devices play a crucial role in datacollection, there is a pressing need for optimizations to enhance on-devicedata processing, thereby reducing network transmissions, energy consump-tion, and data storage requirements. The most common type of data col-lected by these embedded devices is in the form of time series, encompassingenvironmental metrics like temperature and humidity, or operational datafrom sensors linked to machinery and electronics. Processing such timeseries datasets necessitates indexing both the sequentially increasing times-tamps and the non-sequential data values. While database indexes such asthe popular B-tree have been adapted to flash storage on servers and solid-state drives, these optimizations typic…
has type: Thesis/Dissertation
date issued: 2024-11
is shown at: 10.14288/1.0445079
language: eng
degree discipline: Computer Science
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
contributor: Lawrence, Ramon
type: Text
identifier URI: http://hdl.handle.net/2429/88947