Science, Irving K. Barber Faculty of (Okanagan)
Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
DSpace
UBCO
Ding, Yiming
Master of Science - MSc
University of British Columbia
To meet the demand for increasingly accurate sensor monitoring and forecasting, time series datasets have grown to take larger, more detailed samples with more frequent sampling rates. As a result, the size of time series datasets has grown larger and now require more efficient indexing methods to manage properly. Time series databases have unique traits that allow for efficient indexing structures to be used. The timestamps are always increasing in an append-only fashion, a characteristic which can be exploited to create more efficient indexing structures. In this research, two different indexing algorithms for time series databases are evaluated. The spline index model uses existing points of the time series data to form a series of linear approximations. The other index model examined is the piece-wise geometric model (PGM), which forms fully independent lines that approximate the underlying time series data. Experimental results show both the Spline and PGM learned indexes outperform conventional indexes for time series data. Performance metrics for binary search and simpler single line approximations are also included for comparison.
Applying Learned Indexing onEmbedded Devices for Time Series DatabyYiming DingB.Sc., The University of British Columbia, 2020A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe College of Graduate Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)July, 2023© Yiming Ding, 2023The following individuals certify that they have read, and recommend tothe College of Graduate Studies for acceptance, a thesis/dissertation entitled:Applying Learned Indexing on Embedded Devices for Time Series Datasubmitted by Yiming Ding in partial fulfilment of the requirements of thedegree of Master of Science.Dr. Ramon Lawrence, Irving K. Barber Faculty of ScienceSupervisorDr. Khalad Hasan, Irving K. Barber Faculty of ScienceSupervisory Committee MemberDr. Yong Gao, Irving K. Barber Faculty of ScienceSupervisory Committee MemberDr. Barb Marcolin, Faculty of ManagementUniversity ExamineriiAbstractTo meet the demand for increasingly accurate sensor monitoring andforecasting, time series datasets have grown to take larger, more detailedsamples with more frequent sampling rates. As a result, the size of timeseries datasets has grown larger and now require more efficient indexingmethods to manage properly. Time series databases have unique traits thatallow for efficient indexing structures to be used. The timestamps are alwaysincreasing in an append-only fashion, a characteristic which can be exploitedto create more efficient indexing structures. In this research, two differentindexing algorithms for time series databases are evaluated. The spline indexmodel uses existing points of the time series data to form a series of linearapproximations. The other index model examined is the piece-wise geometricmodel (PGM), which forms fully independent lines that approximate theunderlying time series data. Experimental results show both the Spline andPGM learned indexes outperform conventional indexes for time series data.Performance metrics for binary search and simpler single line approximationsare also included for comparison.iiiLay SummaryWireless sensor networks monitor and collect data in areas too large tobe covered by a single sensor, or in scenarios where it is impractical to runcables to every individual sensor device. Sensor network nodes are comprisedof battery-powered embedded devices with flash storage that communicateusing a wireless radio. Data gathered by sensor nodes can be transmitteddirectly to a base station where it is stored and processed, however, lowerenergy consumption (and longer battery life) can be achieved by processingthe data locally. Local data processing requires an efficient data indexingstructure optimized for flash memory with the limited CPU and memory re-sources available to an embedded device. In this work we modify two learnedindexing structures (Spline and PGM) to support the continuous appendingfunctionality required for continuously generated sensor data. Benchmarkresults on ordered data sets show performance advantages compared withconventional indexes.ivPrefaceThis work has been published in the following publication:David Ding, Ivan Carvalho, and Ramon Lawrence. Using Learned In-dexes to Improve Time Series Indexing Performance on Embedded SensorDevices. In Proceedings of the 12th International Conference on SensorNetworks, February 2023, ISSN 2184-4380, ISBN: 978-989-758-635-4, DOI:10.5220/0011692900003399, pages 23-31.Some components of this thesis are from this publication.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xiiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2: Background . . . . . . . . . . . . . . . . . . . . . . . 42.1 Database Systems . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Database Indexes . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Flash Indexes . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3.1 B-tree Based Flash Indexes . . . . . . . . . . . . . . . 132.3.2 Skip-List-Based Indexes . . . . . . . . . . . . . . . . . 152.3.3 Hash-Based Indexes . . . . . . . . . . . . . . . . . . . 162.3.4 Flash Indexes Performance Summary . . . . . . . . . . 182.4 Time Series Databases . . . . . . . . . . . . . . . . . . . . . . 212.4.1 LittleTable . . . . . . . . . . . . . . . . . . . . . . . . 212.4.2 Apache IoTDB . . . . . . . . . . . . . . . . . . . . . . 232.5 Embedded Databases and Sensor Networks . . . . . . . . . . 252.6 Design Considerations for Embedded Sensor Networks . . . . 30viTABLE OF CONTENTS2.7 Embedded Sensor Network Database Architectures . . . . . . 322.7.1 TinyDB . . . . . . . . . . . . . . . . . . . . . . . . . . 322.7.2 Antelope . . . . . . . . . . . . . . . . . . . . . . . . . 322.7.3 Cougar . . . . . . . . . . . . . . . . . . . . . . . . . . 332.7.4 LittleD . . . . . . . . . . . . . . . . . . . . . . . . . . 332.7.5 IonDB . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.7.6 SBITS . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.8 Conventional Indexes on Embedded Databases . . . . . . . . 362.8.1 Linear Hashing . . . . . . . . . . . . . . . . . . . . . . 362.8.2 B-Tree Index . . . . . . . . . . . . . . . . . . . . . . . 372.8.3 MaxHeap Index . . . . . . . . . . . . . . . . . . . . . . 372.8.4 Hash Index . . . . . . . . . . . . . . . . . . . . . . . . 382.8.5 Inline Index . . . . . . . . . . . . . . . . . . . . . . . . 382.8.6 Skip List Index . . . . . . . . . . . . . . . . . . . . . . 392.9 Time Series Indexes . . . . . . . . . . . . . . . . . . . . . . . 392.10 Learned Indexes . . . . . . . . . . . . . . . . . . . . . . . . . 402.10.1 RMI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422.10.2 PLA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432.10.3 PGM . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.10.4 Spline . . . . . . . . . . . . . . . . . . . . . . . . . . . 462.10.5 Comparison between Spline and PGM . . . . . . . . . 48Chapter 3: Methodology . . . . . . . . . . . . . . . . . . . . . . 503.1 Piece-wise Geometric Models . . . . . . . . . . . . . . . . . . 523.2 RadixSpline . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52Chapter 4: Implementation . . . . . . . . . . . . . . . . . . . . . 564.1 Radix Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . 564.2 Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584.3 SD Cards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584.4 Dataflash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584.5 SPI Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.6 FAT File System . . . . . . . . . . . . . . . . . . . . . . . . . 594.7 Data Transfer From SD Cards . . . . . . . . . . . . . . . . . . 594.8 Data Transfer to Dataflash using SPI . . . . . . . . . . . . . . 604.9 Build Environment . . . . . . . . . . . . . . . . . . . . . . . . 61Chapter 5: Results . . . . . . . . . . . . . . . . . . . . . . . . . . 635.1 Query Performance . . . . . . . . . . . . . . . . . . . . . . . . 655.2 Memory Space Efficiency . . . . . . . . . . . . . . . . . . . . . 68viiTABLE OF CONTENTS5.3 Insertion Performance . . . . . . . . . . . . . . . . . . . . . . 695.4 Results Discussion . . . . . . . . . . . . . . . . . . . . . . . . 71Chapter 6: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 736.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 74Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75viiiList of TablesTable 2.1 Relational Database Tables . . . . . . . . . . . . . . . 5Table 2.2 List of flash indexes and their performance [FABM20].− denotes a lack of available data, the r, w, s, bm sub-scripts stand for reads, writes, sequential and blockmerges respectively. Refer to Table 2.3 for a list ofsymbol definitions. . . . . . . . . . . . . . . . . . . . . 19Table 2.3 List of Symbols Used in Table 2.2 and Their Definitions 20Table 2.4 Relative Performance of the Data Structures Used inIonDB . . . . . . . . . . . . . . . . . . . . . . . . . . . 34Table 2.5 PGM Index Points . . . . . . . . . . . . . . . . . . . . 45Table 2.6 Spline Points . . . . . . . . . . . . . . . . . . . . . . . 47Table 5.1 Hardware Performance Characteristics . . . . . . . . . 64Table 5.2 Experimental Data Sets . . . . . . . . . . . . . . . . . 64Table 5.3 Memory consumption comparison among the learnedindexes for each dataset in the benchmark. . . . . . . . 69Table 5.4 Index Size in bytes, IOs per Timestamp Query, andQuery Throughput (queries/sec.) for Different ErrorBounds ϵ . . . . . . . . . . . . . . . . . . . . . . . . . . 70ixList of FiguresFigure 2.1 Database Keys . . . . . . . . . . . . . . . . . . . . . . 7Figure 2.2 Hardware Abstraction Layers for Database Storage . 8Figure 2.3 B-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 9Figure 2.4 Hash index . . . . . . . . . . . . . . . . . . . . . . . . 10Figure 2.5 R-Tree index . . . . . . . . . . . . . . . . . . . . . . . 11Figure 2.6 Sample Time Series Dataset . . . . . . . . . . . . . . 21Figure 2.7 Data Organization of Tuples on Disk . . . . . . . . . 22Figure 2.8 Wireless sensor network . . . . . . . . . . . . . . . . . 26Figure 2.9 TinyDB (a data collection architecture) . . . . . . . . 27Figure 2.10 Data logging architecture . . . . . . . . . . . . . . . . 28Figure 2.11 Data mule architecture . . . . . . . . . . . . . . . . . 29Figure 2.12 Learned Indexes . . . . . . . . . . . . . . . . . . . . . 41Figure 2.13 PGM Query . . . . . . . . . . . . . . . . . . . . . . . 46Figure 2.14 Spline Structure . . . . . . . . . . . . . . . . . . . . . 48Figure 2.15 Spline and PGM Models Fitted Over Time Series Data 49Figure 4.1 Radix Table Expansion . . . . . . . . . . . . . . . . . 57Figure 4.2 Custom Development Board With Integrated NORDataflash . . . . . . . . . . . . . . . . . . . . . . . . . 61Figure 4.3 Desktop Environment of Platform.io Extension on Vi-sual Studio Code . . . . . . . . . . . . . . . . . . . . . 61Figure 5.1 eCDFs for the experimental datasets. . . . . . . . . . 65Figure 5.2 Average query throughput among the indexes for eachdataset in the benchmark. Higher rates indicate bet-ter results. The RadixSpline and PGM consistentlyoutperform SBITS and binary search. . . . . . . . . . 66Figure 5.3 Average number of IOs per query among the indexesfor each dataset in the benchmark. Lower rates arebetter. Learned indexes significantly reduce the num-ber of required IOs. . . . . . . . . . . . . . . . . . . . 68xLIST OF FIGURESFigure 5.4 Average insertion throughput among the indexes foreach dataset in the benchmark. Higher rates indicatebetter results. The insertion throughout is slightlylower for the PGM, but overall learned indexes remaincompetitive. . . . . . . . . . . . . . . . . . . . . . . . 71xiAcknowledgementsI deeply appreciate the support and guidance that I have received fromDr. Ramon Lawrence over the course of my time at UBC, his enthusiasmfor teaching and genuine care for his students is obvious and continues to bean inspiration.Many thanks to Ivan Carvalho, whose contributions to the PGM imple-mentation and published paper are greatly appreciated and were instrumen-tal in helping to keep things on track.xiiDedicationThis work is dedicated to mom and dad, whose love and continued sup-port of my education made it possible for me to go as far as I’ve come.xiiiChapter 1IntroductionA time series is a set of data indexed using temporal information. Thistype of data set is generally sorted by their temporal indexes and are com-monly used to track metrics over a period of time. A typical time seriesdata point is comprised of a data segment, coupled with a temporal index.The data segment can contain arbitrary information and can contain mul-tiple fields. The temporal index must contain some descriptor of the timeassociated with the data segment. Data organized in this way can be usedto monitor changes, extrapolate trends, and find patterns that emerge whencomparing data points against themselves at different points in time.Time series databases are software solutions designed to handle timeseries data and provide the means to efficiently insert new data points andto query for existing data within a time series dataset. Time series databasesare commonly applied in fields such as meteorology, finance, and economicswhere time-dependent data such as stock prices, climate information, andmacroeconomic data can be stored and analyzed. These are fields in whichforecasting is a major point of interest, and in which significant value can beextracted from correct predictions of future trends.They are also used in a variety of other applications with a focus on mon-itoring. Examples include manufacturing, power grids, and retail. In thesescenarios, reacting to changing conditions in real time is a major interest,and time series databases are able to send out notifications to the end users ifproduction falls too far behind schedule, power demands spike unexpectedly,or if product inventory falls to a critical level. Generally, organizations usetime series databases to gain insights into their data, predict about futuretrends, and optimize ongoing operations.A notable use-case example of time series data logging is their applica-tions in agriculture. Deployments of embedded sensor devices could directlyreduce operating costs and increase profits from crop yields by continuouslysampling the environment to generate time series data. Soil moisture sensorscan enable the use of targeted irrigation, reducing costs by watering cropsonly in parts where it is necessary. Temperature, humidity, and precipitationdata can inform personnel of abnormal weather conditions so they have a1chance to take preventative measures for preventing crop loss.Time series data is typically collected with a consistent sampling interval,the result of which are timestamps that are equally spaced apart. These datapoints are then stored on disk for later retrieval. By applying a mathematicalmodel on top of the timestamps, it is possible to estimate the approximateindex of a specific data slice. Indexes can then be used to generate the disklocation of a specific data slice, which reduces the number of disk access andcomparison operations needed to complete a database search.When time series are sampled regularly with zero missed sampling points,a simple linear model would be sufficient to accurately predict the positionof any data point. However, time series datasets in practice often havemissed samples, or are only sparsely populated on demand. For example,meteorological stations may opt to skip certain reporting intervals due tomaintenance operations or equipment failure. Additionally, in applicationswhere energy efficiency is critical (such as with battery powered devices),a design decision may be implemented to only record new data sampleswhen noteworthy observations are made. With these sparsely populatedtime series, a more sophisticated indexing method is necessary.Machine learning models have seen significant research in recent years re-garding their applicability in the enterprise database area [KBC+17]. Thesemodels aim to improve upon the performance offered by traditional indexingmethods by fitting the patterns in the underlying distribution of the data.Piecewise linear functions are a type of learned indexes that have been ap-plied in the field of machine learning and big data as an efficient methodof approximating a Cumulative Distribution Function (CDF). The memoryefficiency of these models makes it possible to index massive datasets wherea conventional index may not fit in memory [ALAB+20], but it could alsolend itself well in situations where limited hardware resources are available.This work adapts learned indexing techniques, specifically the Spline andPGM piecewise linear functions, originally designed for server applicationsfor indexing time series data on embedded devices. A key contribution is sup-porting incremental appends as a sensor collects time series data over time.The performance of these index structures is benchmarked against other in-dexing methods using metrics such as memory consumption, IO count, andthroughput. We demonstrate the advantages of applying a learned indexfor time series data supported by our experimental benchmarking results onreal-world datasets.The contributions of this thesis are:− A C implementation of the Spline and PGM learned indexes for limited2memory embedded systems− The addition of append support for the Spline and PGM indexes− Performance evaluations of the Spline and PGM learned indexes againstthe SBITS conventional index for multiple real-world sensor data setsThe organization of this thesis is as follows. Chapter 2 provides back-ground on database systems and indexing with specific details on uniquechallenges and solutions for indexing on embedded devices and sensor net-works. Chapter 3 describes the methodology for adapting existing learnedindexes to support embedded time series data and incremental appends.Implementation details are described in Chapter 4. Experimental results inChapter 5 demonstrated improved performance of learned indexes comparedto the state of the art. The thesis closes with conclusions and future work.3Chapter 2Background2.1 Database SystemsAfter the introduction of random access storage, the Relational Modelpopularized the notion that applications should query for data by content.This requires data to be organized in a way such that their semantic purposewas integrated into the structure. The concept of the database “table” wascreated to fulfill this purpose, with each table being designated to containdata of a specific type and function. A table consists of rows and columns,where each row represents a record and each column represents a field withinthe record. Records are also commonly referred to as tuples. The columnsdefine the type of data that can be stored in each field, such as text, numbers,or dates. For example, a table that holds student records for the purposeof school administration might have a text column to contain the student’sname, a number column that contains the student’s grade number, a numbercolumn to hold the student’s age, and another number column containinga unique identifier tied to the student. A populated table following thisstructure is shown in Table 2.1(a). The data types defined by the columnsmust be met for all student information to be inserted into the table. Aformatted piece of information with the correct number of fields containingthe correct data types as defined by the database table can then be inserted asa “row” in the database. A database row can only be inserted into a databasetable if and only if the row has the correct number of fields required by thetable, with each field containing the correct data types. Tables within adatabase can be related to one another through common keys and indexes,which allow for the retrieval of data from multiple tables based on commonvalues. Tables are the building blocks of relational databases and are usedto store and manage large amounts of structured data.Software used to manage and organize relational databases (as well asother types of databases) are called Database Management Systems (DBMS).They provide tools and features for creating, maintaining, and accessingdatabases, including data modeling, data manipulation, data security, anddata retrieval. The DBMS acts as an interface between the database and the42.1. DATABASE SYSTEMSStudentID StudentName Grade Age0 David 1 61 John 1 72 Joseph 1 73 Alex 1 64 Lisa 1 65 Allie 2 76 Jessica 2 87 Jake 2 88 Chris 2 79 George 2 710 Polly 3 911 Brock 3 812 Shawn 3 813 Jeff 3 814 Peter 3 915 Jason 4 1016 William 4 917 Danny 4 1018 Zack 4 919 Bill 4 9(a) Students TableTeacherID TeacherName Subject0 Emma Math1 Gerald English2 Molly Science3 Harold Social Studies(b) Teachers TableGrade TeacherID1 02 13 24 3(c) Homeroom TableStudentName TeacherNameJohn EmmaJoseph EmmaAllie GeraldChris GeraldGeorge Gerald(d) Query Result For Age 7 StudentsAnd Their Homeroom TeachersTable 2.1: Relational Database Tablesapplications that use it, allowing users to interact with the database withouthaving to understand the underlying data structures. DBMSs can be rela-tional, NoSQL, or a combination of both, and they are essential for managinglarge amounts of data in organizations and businesses. Examples of popularDBMSs include Oracle, Microsoft SQL Server, MySQL, and PostgreSQL.To interact with relational databases, a querying language is needed.SQL (Structured Query Language) is a standard programming language formanaging relational databases. It is used to create, modify, and query re-lational databases. SQL is used to interact with a relational database man-agement system (DBMS) and perform tasks such as:− Creating and modifying database structures, including tables, views,indexes, and constraints.− Inserting, updating, and deleting data in a database.− Retrieving data from a database, using SELECT statements to retrievespecific data based on criteria.− Grouping and aggregating data, using aggregate functions such asSUM, AVG, and COUNT.52.1. DATABASE SYSTEMS− Joining data from multiple tables using join operations to combine datafrom multiple tables into a single result set.SQL is a declarative language, meaning that you specify what you wantto do, and the database management system takes care of the details of howto do it. This makes it a high-level language that is easy to use, even fornon-programmers. SQL has been widely adopted as the standard for rela-tional database management and is supported by a wide range of databasemanagement systems. It is widely used in various industries and has becomea standard language for accessing and managing data in relational databases.Using the school administration example, we can write a specific SQL queryto show the names of students and their homeroom teachers. We can thenapply a filter to only show students of age 7. The full SQL query of thisexample is:SELECTStudentName, TeacherNameFROMHOMEROOMNATURAL JOIN STUDENTSNATURAL JOIN TEACHERSWHERESTUDENTS.Age = 7;The result set from executing this query is shown in Table 2.1(d).To uniquely differentiate all entries stored within a database table, eachdatabase tuple contains a unique identifier. This unique identifier is referredto as the primary key. It is used to enforce referential integrity, which en-sures that all records in a database are individually addressable and that re-lationships between database tables are maintained. Database keys are alsoused to enforce constraints between tables in a relational database. Theseconstraints ensure the accuracy and consistency of data in the database.Primary keys belonging to other tables are referred to as foreign keys. Someexamples of keys are: a timestamp/datecode, a numerical ID generated bythe database software, or a text field containing some unique data descrip-tor. On our school administration example, the TeacherID column on theHomeroom table is a foreign key that corresponds to the primary key on theTeachers table. These keys represent a relationship between the two tables,and allow them to be joined into a combined table like shown on Figure 2.1.To store data within a physical storage medium, the DBMS must typ-ically interact with the host operating system. The operating system then62.2. DATABASE INDEXESFigure 2.1: Database Keysinterfaces with the storage device, creating an abstraction layer which is il-lustrated in Figure 2.2. When data is stored on a disk, it is stored in blocksconsisting of a contiguous number of bytes. Operating systems may chooseto use any arbitrary block size, but it is typically between 4 KiB and 64KiB. By using a larger block size, the operating system needs to index fewerblocks for the entire size of the storage device, which greatly benefits memoryconstrained devices.2.2 Database IndexesTo improve querying and general database performance, indexes are oftenused in conjunction with a search algorithm to reduce the number of com-parisons and disk access operations. As noted previously, storage devicesmust be written to in blocks. All tuples stored within the database must bedistributed into these blocks before they can be written to storage. Storageblocks are not guaranteed to be contiguous and may be spread throughoutthe storage media. This presents problems in the context of a database ap-72.2. DATABASE INDEXESFigure 2.2: Hardware Abstraction Layers for Database Storageplication, where a query operation searching for a specific piece of data mustsearch through the storage device block by block until the correct query re-sult is found. This means that to fulfill certain database queries, all the diskblocks containing database information must be read, and no search algo-rithm can be used. Indexes solve this issue by creating an organized datastructure that stores database keys along with the corresponding pointersto the physical addresses of the data block stored on disk. This can reducethe total number of disk access operations necessary for most database op-erations by determining the correct pointer to the storage block containingthe needed data instead of reading and searching through multiple blocks.According to [Gra93], there are several indexing approaches.82.2. DATABASE INDEXESFigure 2.3: B-TreesB-trees [Com79] are the most common and widely used database index.Many derivatives of the B-tree implementation are also in use, including B+trees which have improved scan speed, and B* trees which have superiorspace utilization for random inserts. The base implementation of a B-tree ismade up of several different types of nodes: internal nodes, leaf nodes, andthe root node. These different node types are shown in Figure 2.3. All nodescontain index keys and pointers to the physical storage block that containsthe relevant database tuple that correspond with their index key. The rootnode acts as the point of entry for all querying operations. This node caneither be a leaf node, or have links to one or more child nodes. Child nodescan be either leaf nodes or internal nodes. Leaf nodes are nodes that do nothave any children, and just contain an index key and pointer. Internal nodesare nodes that have one or more child nodes but are not the root node. Thesenodes contain keys known as pivots which determine the value ranges thattheir child nodes are split upon. On our B-tree example shown in Figure 2.3,the root node contains a single pivot with a value of 5. Consequently, thismeans that all child nodes on the left of the root node contain values lessthan 5, and all child nodes to the right of the root node contain values largerthan 5. This same logic applies recursively for all nodes with child nodes tothe left and right. Nodes that contain more than one pivot also have morethan two child nodes. On our B-Tree example, the root node’s right childcontains two pivot values of (009, 011). As such, it accommodates a total ofthree child nodes. Left child nodes are smaller than the smallest pivot (009),middle child nodes are values between 009 and 011, and right child nodescontain values larger than 011. Nodes containing more pivots accommodateeven child nodes that have values between the pivots.Linear hashing [FOKM+20] is another indexing method that aims toreduce the number of disk lookups by determining the physical address of92.2. DATABASE INDEXESFigure 2.4: Hash indexan indexed database tuple by using a hashing method. Hashing algorithmsare able to deterministically generate a hash for an arbitrary input key.This is illustrated in Figure 2.4. Note that collisions are possible wheretwo input keys generate the same hash. When hashes are used correctlyand collisions are minimized, hashing can be very fast for individual valuelookups. A trade-off for this performance is that the index does not supportrange operations.R-trees are another type of tree that are specially suited for multi-dimensional querying. R-trees operate by organizing data into a series ofminimum bounding rectangles (MBRs), where each rectangle fully encap-sulates its children with the smallest possible margins. These MBRs arethen used as the pivot points in a tree structure, where coordinates can besearched according to the bounding region that the point is located in. Anexample of an R-Tree structure is shown in Figure 2.5, along with its spatialrepresentation. Note that all child elements are fully encapsulated in the102.3. FLASH INDEXESFigure 2.5: R-Tree indexMBR of the parent element.2.3 Flash IndexesThe indexing strategies discussed thus far were developed primarily forthe spinning magnetic hard disk. In recent years, Solid State Drives (SSDs)have become increasingly popular. SSDs use NAND flash as the storagemedium rather than spinning magnetic disks, offering performance, durabil-ity, and power consumption advantages, but also some unique characteristicsnot present on magnetic hard disks [FABM19]. One such idiosyncrasy is that112.3. FLASH INDEXESpages can be individually updated on magnetic storage disks, whereas NANDmemory must perform an erase and a write to complete the same operation.This is because pages stored on NAND flash cannot be directly overwrittenlike they can on a magnetic hard drive. Instead, groups of pages called an(erase) block must be erased before new data can be written (erase-before-write). This presents two problems, one of performance, and the other ofdevice longevity. The performance problem is intuitive to understand, whereupdating a single page may require a block erase consisting of multiple pages.A update-in-place operation is extremely costly requiring reading the blockof pages into memory, erasing the block, then writing back all pages includ-ing the updated page. In practice, an update to an existing page is writtensomewhere else in storage and a flash translation layer (FTL) used to maplogical page addresses to physical locations. The longevity problem stemsfrom the fact that NAND flash cells have a limited number of erases it canperform before the cell can no longer reliably hold data. Performing re-peated updates on a single page (with each update involving an erase andwrite cycle) quickly wears down flash cells which can result in reliabilityproblems. Manufacturers of SSDs know about these issues and have imple-mented firmware solutions to help mitigate them. These mitigations ofteninvolve writing an updated block (along with the rest of the page that theblock resides in) in a new page and marking the old page as “deleted” witha tombstone marker in the drive’s internal lookup table. This alleviates theimmediate performance penalty of having to perform a page-wide erase butwill need a garbage collection process to clear the tombstone pages when theSSD is idle. These mitigations are packaged together into the interface thatmanages the NAND flash on the storage drive and handles communicationwith the host device. This firmware is known as the Flash Translation Layer(FTL) and is able to spread the wear of the flash cells on an SSD evenlybetween the available flash packages instead of wearing out a single flashcell prematurely. However, it is still imperative to explore indexing methodsthat address the shortcomings of NAND storage, as the FTL cannot perfectlymitigate the issues associated with an indexing scheme that was originallydesigned to be used with a different storage technology. The existing flashindexing schemes can be broadly separated into three different categories:B-tree based indexes, skip list based indexes, and hash-based indexes.122.3. FLASH INDEXES2.3.1 B-tree Based Flash IndexesBFTL [WKC07], IBSF [LL10], RBFTL [XYLW08]BFTL was the first index designed for SSDs that utilized B-trees. Thisindex combines an LSM tree [OCGO96] with a write buffer (called the “reser-vation buffer”) to cache disk operations in the form of “IU records”. LSMtrees are able to batch random writes together to create blocks of sortedsequential writes before they become IU records. Each IU record containsinformation on the type of operation, the key used, and the tree nodes af-fected. When the reservation buffer fills up, IUs are organized by the nodesthey affect, then written to NAND. This organization process may result inIUs from different nodes sharing a NAND page. Thus, this index uses anaccompanying Node Translation Table (NTT) to reconstruct the tree struc-ture from the data contained on the NAND. Improvements to BFTL such asIBSF and RBFTL employ better buffer management schemes to avoid split-ting up nodes into different flash pages, and in the case of RBFTL, employsthe usage of a small NOR flash cache to backup IUs before inserting theminto the buffer.Lazy-Update B+tree [OHLX09], MB-tree [RKKP09], uB+tree[Vig12], PIO B+tree [RPSL14]These indexes also aim to delay update operations by buffering themin memory using a tree structure. Lazy-Update B+tree achieves this bybuffering updates using the leaf nodes of a tree structure. This process isresource intensive, requiring CPU and memory resources to repeatedly querythe tree nodes. MB-Tree attempts to address this by using fat leaves on thetree structure. These fat leaves require the use of additional nodes, which alsoneeds hardware resources to query. The uB+tree (short for unbalanced tree)forgoes the tree balancing operation for as long as possible, thereby savingon write operations. Tree nodes are assigned additional overflow nodes asneeded, until they are read a specified number of times, at which point thenodes are finally split and balanced in a regular fashion. The PIO B+treefurther improves performance by batching multiple IO operations to performat once, exploiting the parallelization capabilities of modern SSDs.FD-tree [LHY+10]FD-tree has the additional capability to transform many small randomwrites into sequential reads and writes. As sequential reads and writes are132.3. FLASH INDEXESmuch faster than random reads and writes, this transformation has signifi-cant performance advantages when applied to SSDs. However the FD-treehas only been experimentally validated, and it is uncertain whether it canbe used on real systems.BF-tree [AA14]Utilizing bloom filters, the key-memberships within B-tree nodes arerecorded and stored alongside the values. This has good search performance,with the trade-off of costly insert performance. As such, it is designed to beused as a bulk index, with little flexibility for updates.AB-tree [JWZ+15]AB-trees employ the use of buckets that serve as storage structures fordata, and buffers for IO operations. This allows delete, insert, and updateoperations to be processed in batches when a buffer fills. The size of thebuckets and buffers within each tree node can also be sized dynamicallyaccording to the workload being conducted.FB-Tree [JRvS11]This index tree performs all updates out-of-place, appending the updatedblock in its entirety to the end of the file. As such, the newly written blocksdo not have space to accommodate additional updates. This may reduce theoverall lifespan of the SSD as it is less write-efficient for update operations.Flash B-Tree Indexes SummaryB-Tree indexes designed for flash memory aim to reduce or eliminate thein-place updates used by conventional B-Trees, as these operations are ineffi-cient on flash-based storage devices. The BFTL, IBSF, and RBFTL indexesaccomplish this using a write buffer to cache disk operations before they arewritten to NAND as IU records. An accompanying Node Translation Tableis used to reconstruct the tree structure from the stored IU records when theB-Tree needs to be read.− The Lazy-Update B+Tree, MB-Tree, uB+Tree and PIO B+Tree bufferupdate operations in memory, grouped together according to the leafnodes that they affect. When the buffer overflows, a policy is used toselect groups to be written to disk such that overall disk writes arereduced.142.3. FLASH INDEXES− The FD-Tree uses a separate structure to handle updates, which is usedto turn random writes into sequential writes to improve performance.− The BF-Tree utilizes bloom filters to record key-memberships, exhibit-ing improved search performance at the cost of insertion performance.− AB-Trees use buckets in-place of nodes to batch NAND update oper-ations. The size of the buckets can be sized dynamically according tothe workload.− FB-Trees write all updates to the end of the file, which has goodthroughput performance but may reduce the overall lifespan of thestorage device, as the newly written data pages do not have space toaccommodate additional updates.2.3.2 Skip-List-Based IndexesSkip-lists operate using a probabilistic model, where the most commonlyaccessed regions of the list have “shortcuts” that make them easily accessiblewithout needing to go through an extensive search process. Skip lists arecomposed of multiple levels, where the base level is simply a sorted linkedlist of nodes containing all data elements. Levels built on top of the baselayer are also sorted linked lists, the difference being that nodes within upperlists contain additional pointers to other nodes from a list in a lower level.All pointers to nodes in lower lists are accompanied by a key containing thelowest-valued element of the node being pointed to. These keys are referredto as “pivots” as they divide the lower levels into discrete search ranges.Upper levels of a skip-list “skip” multiple entries in the layer below it toallow for quick traversal to the most commonly accessed entries, skippingover the entries that rarely get accessed. For example, the upper level ona two-level skip list with 5 elements may choose to only have pointers tothe 3rd and 5th element on the base level list if the 2nd and 4th elementsare rarely accessed. Policies on the construction of the skip list layers varybetween implementations, some examples of which are listed below.FlashSkipList [WF17]FlashSkipList uses an in-memory buffer to store incoming write opera-tions. When the buffer overflows, it is flushed to flash where it is dynamicallyassociated with an element in a skip-list search structure. An online com-petitive algorithm adjusts the distribution of the write buffers within the152.3. FLASH INDEXESskip list whenever an upper size bound is reached, or a search operationis conducted. FlashSkipList has been experimentally demonstrated to de-liver superior performance than the BFTL, FlashDB, LA-Tree and FD-Treeindexes.Write-Optimized Skip List [BFCJ+17]Like the FlashSkipList, the Write-Optimized Skip List implementationalso uses in-memory buffers to store incoming write operations. However,the Write-Optimized Skip List allocates additional space inside its buffersinside the nodes of the skip-list structure for insert operations. Nodes alsocontain a write buffer which splits its elements into buffers on lower levelsupon overflowing, while a new pivot is inserted into the layer above. The per-formance of Write-Optimized Skip List has only been theoretically analyzed,real-world performance remains un-tested.Flash Skip-List Indexes SummarySkip lists are able to use probabilistic models to optimize search queriesto the most commonly accessed entries. Both FlashSkiplist and Write-Optimized Skip List have unique policies to determine how pointers withinthe dataset should be organized, but Write-Optimized Skip List also incor-porates a buffer area within the data nodes to accommodate additional datainserts.2.3.3 Hash-Based IndexesHash-based indexes are built around the hash table data structure, wherea hashing algorithm is able to evenly and deterministically distribute anincoming stream of keys into a collection of data buckets. Pointers to the databuckets and the hash value they are associated with are organized in a tabletermed as the “directory”. When searching for a value, the key is evaluatedwith the hashing algorithm, where the returned hashed value is referencedusing the directory to locate the bucket containing the value associated withthe un-hashed key. This search structure is very read efficient, as it can returna specific pointer to the data bucket containing the desired search value oftenin only one access. There are several types of hash tables including linearhash, extendable hashing, and bloom filters. Linear hashing handles bucketoverflows by linking additional overflow buckets from the base bucket tostore overflow value entries. By comparison, extendible hashing does not useoverflow buckets. Instead, overflows are handled by increasing the size of162.3. FLASH INDEXESthe directory so that it can point to a new bucket to contain overflows. Thisensures that extendible hashing will have a O(1) worst-case access time, thetrade-off being that the directory will have a super-linear size. The bloomfilter data structure uses multiple hashing functions to generate a combined,compound hash value. The number of hashing functions used is determinedby the desired overall error rate, since the bloom filter is able to answer setmembership queries with a chance for false-positives but zero false negatives.This results in a very space and time efficient index. In the context of flashmemory, operations like inserting values and bucket splitting often involve in-place updates and random writes which are detrimental for SSD performanceand longevity. The following are a selection of flash-aware hashing indexesthat attempt to remedy this problem.LS Linear Hash [LDM08]LS Linear hash handles bucket splitting by constantly monitoring searchperformance, and only performing the bucket splitting operation when per-formance levels fall below a threshold. Bucket splitting is then done inbatches that optimize writes in return for increased reads.HashTree [CJY10]HashTree uses a bounded-height FD-tree (a B-Tree structure designedfor flash) as storage buckets. The sorted values in the FD-Tree can then bewritten to flash with sequential writes rather than random writes.SAL-Hashing [JYW+18]The buckets in SAL-Hashing are arranged together into units that arebatched together and written to disk simultaneously, taking advantage ofthe fast parallel IO characteristics of SSD storage. This scheme introducesan online algorithm to split and merge logs into buckets, which introduces apenalty in search performance.BBF [CMB+10], BloomFlash [DSl+11] and FBF [LDD11]Both BFF and BloomFlash are bloom filter derivatives that use similarapproaches to incorporating bloom filters on SSD storage. Bloom filters aresplit up into smaller sub bloom filters that are exactly one page in size, suchthat write operations can be done without conducting any in-place updates.A limitation of both BBF and the BloomFlash index is an upper bound172.3. FLASH INDEXESon the number of elements that can be stored. FBF solves this issue byorganizing the sub bloom filters hierarchically such that when a level reachescapacity, a new level is generated wherein each element in the new levelincorporates a predetermined number of blocks from the previous level.Flash Hash Indexes SummaryHash based indexes use hashing algorithms to split up incoming keys intoa collection of data buckets.− LS Linear hash defers bucket splitting until performance falls below athreshold.− HashTree uses B-tree structures as buckets to speed up querying per-formance.− SAL-Hashing groups buckets together to be written to disk simultane-ously. An online algorithm determines how to split and merge writelogs into buckets.− BBF and BloomFlash utilize bloom filters to index pages stored onflash. The limitation of both these indexes is the an upper bound onthe total number of elements that can be stored.2.3.4 Flash Indexes Performance SummaryThis section summarizes the performance characteristics of the indexesdiscussed along with their space efficiency (if available).182.3. FLASH INDEXESTree-Based IndexesIndex Search Insertion/Deletion SpaceBFTL h ∗ c 2( 1M−1 + N˜split + N˜merge/rotate) n ∗ c+BIBSF h 1niu (N˜split + N˜merge/rotate) N +BRBFTL − − −Lazy-Update B+Tree − − −MB-Tree 2 + ⌈logM 2∗nM∗nl ⌉ [3/nf ]w + [(nl + ⌈ 2∗nM∗nl ⌉)/nf ]r N +BuB+Tree − − −PIO B+Tree h− 1 + tL [∑h−2l=⌊6⌋1G(l) − 1/M′(6%1)G(logM′ (µ−B)−1)+ 1G(h−1) ]r + [1G(h−1) ]wn+ µFD-Tree logkn [ kf−k logkn]srw c ∗ nBF-Tree h+ [pfp ∗ npl]sr − n ∗ nplAB-Tree∑hl=1M ′l−1Nll h/sn nFB-Tree − − −Skip-List-Based IndexesIndex Search Insertion/Deletion SpaceFlashSkipList − − −Write-Optimized Skip List − − −Hash-Based IndexesIndex Search Insertion/Deletion SpaceLS Linear Hash − − −HashTree − − −SAL-Hashing 2 + nlp ∗ pfp (r+4)∗gnB∗sp−2∗gn ∗ (2 +gn + pu ∗ g) nBBF & BloomFlash 1/nbf , 1 1/nbf n+BFBF logbn 1/B n+BTable 2.2: List of flash indexes and their performance [FABM20]. − denotesa lack of available data, the r, w, s, bm subscripts stand for reads, writes,sequential and block merges respectively. Refer to Table 2.3 for a list ofsymbol definitions.192.3. FLASH INDEXESSymbol Definitionb Number of child structures introduced to each block after false positive limit is reachedB Size of reservation filterc Predefined threshold before tree reorganizationf Number of entries per pageg Number of buckets in a groupgn Number of groupsG(i) Average number of update operations that read a node at level ih The height of the treek Logarithmic ratio between the size of adjacent levelsl Variable that denotes a specific level in a treeL Size of leafMNumber of keys per node in the context of B-Trees.Number of IUs (write logs) per flash page in the context of hashing.M ′ Average number of entries in a nodeµ Amount of available memoryn Number of nodesnbf Number of buffered operationsnf Number of flushesniu Number of buffered IUsnl Number of leavesnlp Number of pages a log areanpl Number of pages per leaf node6 Expands to logM ′ nL(µ−b) − 1N Number of keysN˜ Number of operations denoted in the subscriptpfp Probability of false positivespu Probability that a particular record resides in a particular log arear Record sizesn Average size of a nodesp Page sizetL 6Time to read a leaf of size LTable 2.3: List of Symbols Used in Table 2.2 and Their Definitions202.4. TIME SERIES DATABASES2.4 Time Series DatabasesFigure 2.6: Sample Time Series DatasetA time series dataset consists of a number of key-value tuples, with atimestamp as the key and a piece of arbitrary data as the value. Thesetimestamps are stored in ascending order such that the data represents atemporal progression of values over time. Each data recording is assignedthe current timestamp and inserted into the time series dataset in the order ofwhich they are collected. An example of a time series dataset depicting datapage numbers that contain information pertaining to specific timestamps areshown in Figure 2.6. Note the increasing and sorted order of the timestamps.Tuples of time series datasets are stored on-disk, with each physical pageon the disk containing multiple tuples. Figure 2.7 shows the general datahierarchy of how tuples are stored on disk. Many database systems designedto contain time series data exist and have different approaches on how bestto store time series data. Some examples are explored here.2.4.1 LittleTableLittleTable [RWW+17] is a time series database system used by CiscoMeraki to store usage statistics, event logs, and other time-series data col-lected from customer devices. This data is used to generate data visualiza-212.4. TIME SERIES DATABASESFigure 2.7: Data Organization of Tuples on Disktions like bar graphs and tables displayed with an online dashboard, but canalso be used to perform diagnostic tasks like root-cause analysis and dataforensics. From the database design perspective, this means that:− Frequent queries retrieving the same data must be very fast. This isbecause the most common data visualizations only request the mostrecent data (e.g. The number of bytes transferred by a client in thelast hour, rankings of top network users of the past month, etc.).− Queries retrieving older data must also be quick, as data forensics androot-cause analysis applications benefit from the ability to look backfurther in time.− The database system should be optimized for use with magnetic diskhard drives as the storage medium. Storing a longer history of logstakes up a larger amount of space, so magnetic disks are preferredover solid state media for economic reasons as the latter still has aconsiderably larger cost per byte than magnetic disks.Taking these considerations into account, LittleTable was designed usinga B-tree indexing system that iteratively adds new records in chunks called‘tablets’ as they are recorded. As with any time series, the keys are times-tamps sorted in ascending order. LittleTable intelligently combines a deviceID with the timestamp to form a new key, such that devices that are related222.4. TIME SERIES DATABASESto each other (eg. in the same network) have contiguous keys. This hasthe result of making it likely that data for related devices are also stored oncontiguous blocks on disk. Since data for related devices are often requestedsimultaneously, the hard drive does not need to incur a seek penalty to readdata for related devices. As new data is inserted, it is first inserted into atablet. Each tablet contains a B-tree index to speed up queries and reduceoperational latency. This index only takes up 0.5 percent of the total sizeof the tablet, and is cached on main system memory. The minimum andmaximum timestamps of each tablet is also cached on system memory andis accessed using binary search. This means that lookups of newer data takesroughly the same amount of time as lookups of older data. Cisco runs Lit-tleTable using powerful servers, which they call ‘shards’. Shards are able torely on system memory to cache index data and speed up data queries, buton lower power devices with limited memory, a different approach may berequired.2.4.2 Apache IoTDBApache IoTDB [WHQ+20] is a time series database developed to addressthe shortfalls of NoSQL when working in the context of Industrial Internet ofThings (IIOT). The increasing popularity of IoT devices motivated the cre-ation of a time series management system optimized for high-throughput andlow-latency with support for common operations used in time series analysis.Additionally, IoT devices are diverse in their implementation, from consumerapplications like wearables, smart-home devices, to industrial and enterpriseapplications like connected healthcare and monitoring. This wide gamut ofapplications necessitates the creation of scalable and portable software withwide hardware support. For this reason, IoTDB supports both cloud andedge deployment models. On the cloud side, IoTDB can be deployed indistributed computing clusters housed in data centers. On the edge side,IoTDB can also be scaled down to be hosted on a standalone workstationPC, or even on an embedded edge device like a Raspberry Pi.Regardless of the deployment model, IoTDB has been optimized for par-ticular use cases and features most relevant for IoT devices, namely:− Edge computing. With the capabilities of edge devices quickly risingin recent years, the practice of conducting data analysis on the edge-side has gained prevalence. This requires IoTDB to be run on boththe cloud side and the edge side, with an organizaiton structure thatsupports data synchronization between the two.232.4. TIME SERIES DATABASES− Long-life and large volume historical data. Industrial IoT applicationscan generate a large amount of data that must maintain high avail-ability for extended periods of time. A Boeing 787 jetliner was usedas an example in the original publication. Its monitoring sensors canproduce more than 500 GB of data over the course of a single flight.Additionally, long historical data logs must be maintained to identifytrends and monitor the life-cycle of safety-critical components.− High throughput data ingestion. With the large volume of data beinggenerated by industrial IoT devices, high throughput data ingestion isrequired to absorb all the data without dropping data samples.− Low latency and complex queries. Applications that require real-timemonitoring require low latency query fulfillment to quickly identifypotential equipment faults. Additionally, deeper delves into the databy data-scientists can be complex and require flexibility on the typesof queries that must be supported.− Advanced data analytics. Advanced data analysis techniques like ma-chine learning must compute certain metrics after processing chunks ofhistorical data using a costly ETL (Extract, Transform, Load) method.The common operations used in such data analysis techniques must bedone efficiently.To accommodate these design goals, IoTDB was designed with a uniformdesign across the edge and cloud implementations which allow it to be runon ARM7 processors with as little as 32MB of memory. Data can also beeasily synchronized with cloud instances of IoTDB using a File Sync mod-ule. Support for long life, high throughput, low latency and advanced datamanagement is handled using a combination of the TsFile data format andintelligent indexing methods. The TsFile format is composed of two primarycomponents, the data content, and the index. The data portion is partitionedinto pages, which are the smallest storage unit on disk. These pages forma chunk of data, with each chunk containing time series data for a specifictime range specified by the index portion of the file. Additionally, a Sum-mary Info section is present in each chunk of data to store commonly usedaggregate information such as the max/min values and timestamps of eachchunk, the average value, data count, etc. These commonly used metricsare pre-calculated at the time of insertion and greatly improve performanceto enable complex, low latency querying over a large pool of data. Addi-tionally, IoTDB uses write-ahead logging to facilitate high write throughput242.5. EMBEDDED DATABASES AND SENSOR NETWORKSperformance. This streamlines the time-ordering process, and leverages thefaster sequential write performance of the storage device. IoTDB’s designlends itself greatly in applications where flexibility of data retrieval and per-formance is the primary focus. In applications where embedded devices aredeployed on battery power, energy consumption becomes a very importantmetric to optimize to prolong the lifespan of the device. For these scenarios,alternatives to IoTDB are worth consideration.2.5 Embedded Databases and Sensor NetworksAccording to Wolf [Wol02], embedded systems are devices which act asa component in a larger system, and rely on its own CPU. Embedded CPUsalso require their own memory, which it uses to perform a predefined taskas part of a larger process. This decouples hardware design and softwaredesign, allowing for the same software to be reused in future products thatperform similar functions. As electronic devices become more sophisticatedand perform more functions, they incorporate more embedded devices tofacilitate the added functionality. Common examples of embedded devicesthat are part of a bigger whole include:− The Digital Signal Processors (DSPs) on mobile phones that translateradio signals into digital data signals, or convert digital data signalsinto analogue wave forms that can be perceived as sound.− The engine management computers in internal combustion vehicleswhich control spark and ignition timing to ensure optimal fuel burnand increase fuel efficiency.− The co-processors found in inkjet printers that handle typesetting andenable real-time control of the print head, so that pulses of ink areapplied at the exact moment the print head reaches the correct pointon the page.Embedded devices can also be networked together wirelessly to form alarger collection of devices that are able to exchange data with one another.These devices are often used in locations where direct communication linksare impracticable, or impossible all-together. This means that these devicesoften run on battery power or scavenged energy, and have all the resourcesthey need to function semi-autonomously. By attaching a sensor to thesedevices, a sensor network is created.252.5. EMBEDDED DATABASES AND SENSOR NETWORKSFigure 2.8: Wireless sensor networkSensor networks are used in scenarios where data must be collected overan area larger than what a single sensor can reliably service. In such sce-narios, a collection of networked sensors must be distributed to sufficientlycover the area with their combined sensor ranges. These sensor networks areoften used in applications such as environmental monitoring, surveillance,and traffic management. Individual sensor nodes are equipped with capa-bilities to observe and record sensor data and are often run by very smalland efficient embedded microprocessors. All sensor nodes communicate witha base station to report their sensor readings, where it is aggregated intoa centralized database. Figure 2.8 shows an example sensor network con-taining a collection of nodes and a base station. During operation, nodesgather data from attached sensors and must store it locally or transmit tothe base station. The storage and transmission actions are candidates foroptimization, as performing such actions are costly in terms of energy con-sumption. In the context of a battery powered device where the total avail-able power is limited, energy consumption becomes the forefront of prioritiesof things to be optimized in service of prolonging the service life of sensornodes without requiring user maintenance. Examples of successful wirelesssensor networks deployments include the Great Duck Island project [DB10],in which underground sensors were used to monitor the nests of storm petrelswhere they collect health data and relay the information to a gateway node262.5. EMBEDDED DATABASES AND SENSOR NETWORKSplaced nearby. They have also been used as a safety tool in the mining sec-tor, where they monitor the surrounding air quality for traces of hazardousgases to minimize the risk of explosion, contamination, and inhalation injury[CFT07].The three types of sensor data networks defined by Tsiftes and Dunkels[TD11] are as follows.Figure 2.9: TinyDB (a data collection architecture)Data collection networks were one of the first sensor network architecturesto be introduced. In this type of sensor deployment, all sensor nodes submittheir data to designated data sinks, using a data collection protocol. Thoughdata collection networks theoretically can support data aggregation, it is nottrivial to implement and as a result the feature is rarely used in practice. Anotable example of a data collection network architecture is TinyDB shownin Figure 2.9. This architecture streams data from sensor nodes behind an272.5. EMBEDDED DATABASES AND SENSOR NETWORKSabstraction layer that orchestrates the data flow around sensor nodes. Tothe user, only an SQL-like database querying interface from a designateddata gateway node is exposed.Figure 2.10: Data logging architectureData logging networks are another prominent sensor node architecturewhere all sensor nodes log their readings onto a bank of onboard storage tobe retrieved in bulk at a later time. The Golden Gate bridge network isan example of a successful deployment of this type of sensor network. Inthis example, the network was outfitted with 40 sensors to monitor bridgeconditions. The stored sensor data is collected regularly using the Flushdata transfer protocol. Data logging networks are suitable in cases wherethe complete dataset must be gathered from all nodes. The top down viewof a data logging network is shown in Figure 2.10Data mule networks (also called disruption tolerant networks) aim tooperate under circumstances where a reliable network is not available. Inthis network architecture, data transfer is achieved by first uploading thedata onto an interim storage device (sometimes referred to as data mules),which is then physically moved into an area where network access is possi-ble. The data is then offloaded from the storage device onto the networkwhere it is finally routed to the collection point. The top down view of adata logging network is shown in Figure 2.11. This sensor architecture is282.5. EMBEDDED DATABASES AND SENSOR NETWORKSFigure 2.11: Data mule architectureuseful in remote or rural areas where network infrastructure is sparse, or indisaster areas where the network infrastructure is offline. The trade-off forthis type of sensor network is the significant latency introduced by needingto physically move the data mule between the data collection site and thenetwork connection site.When considering the energy cost of sending wireless transmissions, sen-sor network architectures are optimized to reduce the usage of the onboardradio to save power. In the case of the data collection architecture, the userinitiates the data collection command, and thus triggers the transmission ofsensor data into the designated collection point. In this architecture, thedata transmissions are triggered on demand and is thus difficult to optimize.On the other hand, the data logging and data mule sensor network architec-tures operate by recording sensor data onto a local storage device as they arecollected, then sending the data in bulk at predetermined intervals. Thesearchitectures retrieve data from their storage devices at the time of datatransmission, and use indexing methods to ensure that the retrieval oper-ation happens in a timely manner. By introducing more efficient indexingschemes for embedded devices, sensor networks are allowed more flexibilityon their data transmission intervals. This has the potential to allow forfurther network optimization, like longer sampling intervals between datatransfers to lower energy consumption and extend the operational lifetimeof the sensor network.292.6. DESIGN CONSIDERATIONS FOR EMBEDDED SENSOR NETWORKS2.6 Design Considerations for Embedded SensorNetworksTsiftes and Dunkels [TD11] lay out the technological considerations thatmust be factored into the design of an embedded wireless sensor network de-ployed in a real-world operation. Firstly, energy resources of the embeddeddevice are limited. This is the result of powering such embedded devicesusing batteries, which have limited energy reserves. In most cases, the life-time of the sensor network is directly determined by the amount of energyreserves available to the device. In practice, such small, embedded devicesare often placed in difficult to service areas, so battery replacement is sel-dom done. Therefore once the onboard energy reserves have been depleted,the device becomes inoperable. With this in mind, system designers choosehardware that minimizes power draw to increase the battery life (and thusthe lifespan) of the device. Even in scenarios where energy is captured con-tinuously from the environment, such energy sources often have low poweroutputs that still constrain the power draw of the embedded device. For de-vices that are powered from a stable power source, the power consumptionof such devices directly affect the operational cost of keeping a deploymentof such devices active. For example, in a deployment of a million devices, thesmall individual power consumption of the device all add together to form aconsiderable cost that must be weighed against the benefits from operatingthe fleet of embedded devices. This limitation on power draw also limits thetype of hardware that can be powered. High performance CPUs and largepools of system memory have elevated power consumption compared to theirlow-power counterparts, meaning that embedded devices are often heavilyconstrained in terms of CPU, memory, and IO. This hardware limitationhas ramifications on the querying operations and indexing schemes that canbe successfully deployed. Historically, database software have first been de-veloped for usage on the enterprise side, running on powerful servers whichprovide the performance needed to satisfy enterprise customers. These enter-prise software packages are then adapted down to run lower power devices,but often they inherit some of the low-level design decisions made to optimizeperformance on large powerful machines at the detriment of performance onlower power machines. Examples of which include memory hungry hash in-dexing schemes which are incredibly fast on powerful machines with ampleaccess to memory, but are not viable on low power embedded devices withoutsuch resources. Secondly, the bandwidth to communicate with the embeddeddevice is also limited. The transfer speed to and from the embedded device302.6. DESIGN CONSIDERATIONS FOR EMBEDDED SENSOR NETWORKSis tied to power consumption, where higher transmission rates require morepower. This is due to the higher modulation and demodulation speeds re-quired, higher clock speeds and wider bus widths of the onboard electronics,which all contribute to higher energy usage. Though some optimization ispossible, the general trend of higher energy consumption hardware remains.Thirdly, the storage capabilities of the device is functionally infinite. Con-trary to the restricted availability of power and communication bandwidth,the storage capabilities of an embedded device is not a limiting factor. Stor-age devices are a static component, and as such, larger capacity storagedevices still fit into the same standardized form factor, and do not incur anyincreased energy cost. The proliferation of cheap and large storage devicesmeans that embedded devices effectively have unlimited storage space forrecord keeping. Modern flash devices have enough capacity to fit the entiredataset an embedded device is expected to generate within its lifetime. Forexample, an 8-byte value recorded every second for a period of 10 years willonly be 2.5 GB in size. This dataset can easily be contained by a commodity4GB SD card, which can be purchased for less than a few dollars. It is alsoworth mentioning that the comparative power usage of writing data to stor-age is much lower than the power usage of using the radio to send the samedata to a neighboring node. The experiments done by the Antelope team[TD11] show that the energy cost of sending a 100 byte packet of data is 20times more than the energy cost to write the same data onto a flash storagedevice. In summary, embedded devices exhibit the following characteristics:− Extremely energy constrained. Embedded devices are often batterypowered, which limits the amount of power that the device can draw.In many cases, the service life of the battery also determines the servicelife of the device. This means that energy efficiency is paramount toprolong the operating life of the device.− CPU and memory constrained. The limited power available from thebattery also limits the processing capabilities and the memory amountsthat can be put onto an embedded device without negatively impactingefficiency.− Bandwidth is limited. Wireless transmission speeds are also tied toenergy consumption. Faster switching and signal modulation requireshigher transmit power and more powerful electronics.− Storage is functionally infinite. Advancements in flash memory havemade commodity flash storage cheap, reliable, and dense. Inexpensive,312.7. EMBEDDED SENSOR NETWORK DATABASE ARCHITECTURESoff-the-shelf SD cards are available in capacities that have more thanenough space to fit the entire dataset an embedded device is expectedto generate over its lifetime.2.7 Embedded Sensor Network DatabaseArchitecturesSeveral database systems designed for use on sensor networks have beendeveloped and have been successfully deployed in commercial operations.The design of these systems are mindful of the hardware and energy con-straints that characterize the embedded devices which form the sensor net-work nodes.2.7.1 TinyDBThe TinyDB sensor network [MFHH05] popularized the idea to thinkabout sensor networks as a database to be queried rather than a set of basicsensors whose only function is to relay information to a collection station,where all the data processing happens. TinyDB advocates for AcquisitionalQuery Processing (AQP) where data is retrieved as needed whenever a querycalls for it. TinyDB introduces a query processor that functions as a front-end interface for developers to interact with the sensor network withoutneeding to query individual sensor nodes manually. The query processor alsoimplements filtering and aggregation capabilities within the sensor nodes tominimize radio usage and thus improve energy efficiency.2.7.2 AntelopeIn the Antelope sensor network model [TD11], each individual sensornode contains a database supporting dynamic querying and continuous datainsertion. Contrary to many sensor network models that came before it,Antelope stores data on sensor nodes which can be used to optimize datacollection operations. This is useful in sensor network use cases that donot rely on real time data to be sent at the time of querying, and insteadaggregate data from multiple rounds of sensor samples together. This processof data aggregation where multiple data samples are sent to the head node atthe same time has been demonstrated to reduce network usage and therebylower the power consumption of the sensor node [TD11]. The data storedinside the sensor nodes are not only limited to storing sensor readings. Theycan also be used to store network performance metrics and routing tables322.7. EMBEDDED SENSOR NETWORK DATABASE ARCHITECTURESthat can be used to further optimize data transmission throughout the sensornetwork. Antelope also introduces a SQL-like language called AQL to querythe stored data. Antelope has three types of indexes that it uses, dependingon the scenario. A novel MaxHeap index designed for use on NOR flash,an inline index that makes use of a linear function, and a hashing index.Additional details of these indexing methods can be found in Section 2.8.2.7.3 CougarThe Cougar sensor database system [BGS01] was developed to integratedata taken from embedded sensor devices into a larger relational database.This is achieved through the use of Abstract Data Types (ADTs), with everyADT type representing a specific type of sensor (temperature, humidity,seismic, etc), and every ADT object representing a physical sensor in thereal world. These ADTs are used to perform signal processing on the sensornode, and transmit the resulting data back to the base station. Virtualrelations are also used to encapsulate the results of ADTs along with thetimestamps at which they were returned. This allows for data acquisition andprocessing to happen asynchronously, alleviating concerns of data collisionswhen collecting readings from multiple sensors at once, and also removes thelatency associated with wireless data acquisition.2.7.4 LittleDLittleD [DL14] is a database system designed specifically with low powerembedded devices in mind. Like the database used in the Antelope sensornetwork model, the individual IO operations for the underlying memoryis abstracted. Developers are able to interact with the database using aquerying language instead of needing to manually access and process dataprogrammatically. Where Antelope introduced a bespoke querying languagecalled AQL, LittleD implements a SQL-compliant query engine. While AQLis simple to learn and can streamline certain database operations, it has somerestrictive query processing limitations that limit the type of queries that canbe executed, and does not benefit from the ubiquity and standardization ofSQL. LittleD has also been demonstrated to use significantly less memorythan Antelope when running a benchmark of queries, with Antelope usingat least 500% more memory on intensive queries [DL14]. The drasticallylowered memory footprint of LittleD is thanks in large part to its novelquery parser that was written with the specific intent to lower energy cost,coupled with a query translation system that can build query execution332.7. EMBEDDED SENSOR NETWORK DATABASE ARCHITECTURESplans directly from the query itself without performing memory-consumingintermediate steps like building parse trees and logical query trees.2.7.5 IonDBSimilar to LittleD, IonDB [FHD+15] is a database system that was de-signed for use on embedded systems. However, IonDB implements a key-value storage system instead of an SQL-compliant database like the one inLittleD. Key-value databases (also called NoSQL databases) do not imple-ment the relational logic present in SQL databases, but are more memoryefficient and streamlined as a result. Values stored in a NoSQL databaseare accessed using the key that was provided to the database at the time ofinsertion. Developers who do not need the additional features provided bya relational database may instead choose to use a NoSQL database for theirsimplicity and lower hardware overhead. In the context of an embedded sys-tem running on battery power, the lower overhead of a NoSQL may reduceenergy consumption and thus extend the operating life of the device.IonDB implements four different data structure options under a unifieddatabase API. These data structures are:− Skip List− Open Address Hash Map− Flat File: This option does not use a data structure and appends datain no particular order onto a flat file structure (for scenarios wheredata values exceed or almost exceed the amount of available memory).− File Based Open Address Hash MapIonDB documentation provides a list of relative performance metrics usedto compare its included indexes (listed in Table 2.4), however it does notinclude any performance comparisons to indexing structures that are unsup-ported by IonDB.Data Structure Memory Utilization RuntimeSkip List Fair ExcellentOpen Address Hash Map Excellent GoodFlat File Good FairFile Based Open Address Hash Map Excellent FairTable 2.4: Relative Performance of the Data Structures Used in IonDB342.7. EMBEDDED SENSOR NETWORK DATABASE ARCHITECTURESAdditional details of these indexing methods can be found in Section 2.8.2.7.6 SBITSIn pursuit of faster response times, reduced network transmissions andlower energy usage on IoT sensor networks, edge-side querying and dataanalysis has been gaining in popularity. The Sequential Bitmap Indexingfor Time-series Technique (SBITS) [FOL21] is an index structure optimizedfor the embedded devices commonly used as edge nodes in sensor networks.SBITS prioritizes the efficiency of its index structure to ensure it can runon embedded devices with limited memory and processing resources. Com-pared to general database servers, the queries performed on an embeddeddatabase are very well defined, and are known ahead of time. Outlier detec-tion (determining if a value falls outside a specified range), and aggregationoperations (average, max, min, etc) are the two types of queries that aretypically fulfilled by embedded sensor nodes. This knowledge can be ex-ploited to implement an indexing structure optimized for these queries. InSBITS, each data page includes a header that describes pertinent aggregateinformation about the records within the page. The items stored within theheader include:− The largest and smallest timestamp values− The minimum and maximum values− The summed total of all values within the page− A bitmap describing the general distribution of valuesThe page-level aggregate values are used to fulfill aggregation queries forlarger ranges without needing to read each stored value at query executiontime. The bitmap is capable of informing the existence of records that fallwithin a configurable value range. If the bitmap is configured beforehand toidentify values that fall outside of an expected range, outlier detection queriescan use the bitmap to quickly process data pages without needing to readeach individual data value. When querying by timestamp, the ordered natureof the dataset enables page retrieval to be calculated in O(1) time. This ismade possible by the use of consistent record sizes such that it is knownhow many records fit into a data page. By applying a linear regression, thelocation of any given timestamp can be calculated without conducting anyreads. When analyzing memory consumption and querying performance,SBITS is able to match the memory footprint of the Antelope index, while352.8. CONVENTIONAL INDEXES ON EMBEDDED DATABASESadding support for value-based queries. SBITS can also lookup timestampindexes in constant time, whereas Antelope uses a binary search methodwhich has a complexity of O(log2N).2.8 Conventional Indexes on Embedded DatabasesFor many database operations such as joins and other operations usingcomparisons, indexes play a major role in the optimization and performanceof query execution. The TinyDB and Cougar architectures are purely ac-quisitional, meaning that only the most recent data tuple is gathered at thetime of query execution. This architecture has no need for an index sincesensor nodes only hold a single tuple at a time. However, with architecturesthat store relations filled with a large number of tuples, the existence of anordered index on an unordered list of data tuples can speed up performancedrastically. We can see this in the experimental benchmark results that wereperformed in the work for LittleD [DL14], where Antelope outperforms Lit-tleD due to its better indexing support, but exhibits equivalent performanceto LittleD when indexes are removed for both Antelope and LittleD. Thevarious indexes applied by Antelope, LittleD, IonDB, and SBITS will beexplored in this section, along with the rationale behind their usage.2.8.1 Linear HashingThe linear hashing data structure [FOM+19] has the desirable attributeof being able to expand one data "bucket" at a time, compared with ex-tendible hashing which must double its capacity at every expansion. This isaccomplished by splitting data buckets individually, so only one new bucketis needed to store the split contents (assuming no overflow buckets). In[FOM+19], two ways of optimizing the linear hashing data structure for useon embedded devices have been evaluated against the base implementation.− The Bucket Map optimization removes the need for a secondary fileto store overflow buckets by always appending overflow buckets to theend of the file. An in-memory array is then used to map these overflowbuckets to their associated top-level bucket.− The Serial Writing optimization expands upon the Bucket Map im-plementation by also writing changed buckets to the end of the file inaddition to the overflow buckets. A similar in-memory array to keeptrack of the top-level buckets is used.362.8. CONVENTIONAL INDEXES ON EMBEDDED DATABASESSurprisingly, the flash-aware optimizations did not result in a consistentperformance improvement over the base implementation. The increased in-sert performance of the Bucket Map optimization led to a trade-off in otherareas, and the Serial Writing optimization resulted in large file sizes whichled to increased random writes (costly on the FAT16 file system used on theembedded test platform).2.8.2 B-Tree IndexB-Trees are a commonly used indexing structure in high performancedatabase applications, however they have large memory footprints that makethem impractical for used in an embedded system. An adaptation of the B-Tree data structure to optimize memory usage [OFL21] aims to address thisissue while also maintaining indexing performance. This adaptation alsorecognizes the possibility of unexpected power cycling that often occurs inembedded environments, and thus stores data in persistent storage ratherthan in RAM. This implementation of the B-Tree only requires two buffers,one for reading pages, and the other for writing pages. The entire B-Treeimplementation can occupy less than 1.5 KB of memory and requires onlyaround 10 KB of storage, making it practical for use in embedded systems.Additional memory buffers can also be used in this implementation for in-creased performance, though it is not necessary to do so.2.8.3 MaxHeap IndexMaxHeap is a general purpose index developed for use on SD cards andNOR flash. Previous index types typically rely on balanced tree data struc-tures, which must intermittently perform maintenance rebalancing opera-tions. This operation requires rearranging elements on the tree structure,which is unsuitable for the write restrictions of NAND flash. Consequently,these structures use log structures which can have large memory footprintsthat are hard to fit inside the limited RAM found on embedded devices.MaxHeap aims to address this design consideration by implementing a datastructure designed for fewer writes. The binary maximum heap structure fitsthese specifications, and it is used in the MaxHeap index to naturally mapa dynamically expanding dataset. The MaxHeap structure uses two files forevery indexed attribute. One file, called the bucket set container, containsthe key-value pairs that form the index. The other file, called the heap de-scriptor, contains nodes that describe the range of keys stored inside thenodes inside the bucket set container. The MaxHeap structure is populated372.8. CONVENTIONAL INDEXES ON EMBEDDED DATABASESfrom the top down, with new elements being inserted into the bucket thathas the narrowest range around the key to be inserted. Whenever a bucketis filled to capacity, it is split into two separate buckets that are inserted aschildren to the original bucket that reached capacity. This scheme can be-have problematically when keys are presented in an ascending or descendingorder, resulting in an unbalanced tree. This issue is addressed by using ahashing function to generate the binary heap keys, but storing the un-hashedkey in the actual bucket. MaxHeap indexes accomplish their goal of beinga memory efficient indexing scheme that works well for general datasets andcan be operated within the RAM constraints of an embedded device.2.8.4 Hash IndexAntelope and IonDB both implement hash indexes, which store a hashtable in RAM to quickly look up commonly accessed attributes that haverelatively low row counts. This approach is extremely fast, but is also verymemory hungry so it must be used sparingly and only in circumstances wherea few keys are accessed very frequently. The exact limit on the numberof keys that this index can successfully accommodate varies depending onhardware and design limitations, so Antelope designates a default maximumnumber of 100 tuples for its hash index. IonDB’s "Open Address Hash Map"takes a different approach to hashing that stores buckets of data in flashrather than keeping an dense table of tuple pointers in memory. This datastructure is discussed in detail in Section 2.3.3. In summary, a deterministichashing algorithm is used to assign incoming key-value pairs into buckets,which allows other buckets to be omitted when querying using a search key.IonDB can also use "File Based Open Address Hash Map" which is similarto the regular Open Address Hash Map implementation, except the hashmap structure is stored in storage rather than memory.2.8.5 Inline IndexWhile the MaxHeap and hash indexes implemented in Antelope cover awide range of usage scenarios, they assume that the distribution of keys tobe inserted will be in random order. This is useful when indexing attributesthat follow a normal distribution of values such as temperature sensor data,however with embedded sensor networks the data collected tend to be timeseries datasets resulting from the repeated sampling of a sensor throughouta reporting period. Time series datasets have the unique characteristic ofusing timestamps as index keys, which are generated in ascending order. A382.9. TIME SERIES INDEXESset of constantly increasing keys (such as the ones in a time series index) canbe exploited using the inline indexes found in Antelope and SBITS, whichdo not use any data structure. Instead, the inline index uses the orderednature of the indexed keys to perform a binary search over the entire rangeof keys when conducting a search. This results in a O(1) space overheadwhile maintaining a O(logN) time complexity for search operations [TD11].SBITS used a single linear approximation of the time series values to predictthe location of a given timestamp.2.8.6 Skip List IndexIonDB includes the option to use skip list indexes in scenarios where theaverage access time for all tuples is important. Additionally, skip list indexesdo not require in-place updates like balanced tree data structures. Imple-mentations of tree structures on devices using flash storage also incorporateseparate data structures (usually a log structure [RO92]). This structure isused to delay or batch writes together for the purpose of reducing expen-sive in-place updates. These auxiliary data structures also take up valuablememory within a memory-constrained embedded device, which leaves lessmemory available for the tree structure itself. Skip lists do not require aux-iliary data structures, as they can be implemented as append-only fashionin scenarios where inserted data has keys that are monotonically increas-ing. The skip list data structure is discussed in detail in Section 2.3.2. Insummary, skip lists use probabilistic models that link to the most commonlyaccessed sections within a list, "skipping" over the less-frequently accessedelements.2.9 Time Series IndexesWhen retrieving the data associated with a certain timestamp, the loca-tion of the page containing the correct tuple must be determined.A naive approach of conducting a binary search through all the datapages will accomplish this, however this tends to be an expensive searchoperation as each IO requires reading a data page and checking its contents,which takes a considerable amount of time, adding to the overall latencyof the data retrieval operation. To minimize the number of required IOoperations needed to find the correct data page, an indexing structure canbe applied to the timestamps of the time series database.One of the simplest database indexes is the linear approximation. Thisis a simple linear regression that is fitted over the timestamps of the dataset.392.10. LEARNED INDEXESDespite its simplicity, this index has seen success in applications where thetime series records are equally spaced apart, such as in embedded sensornetworks configured to generate records with consistent sampling rates. TheSBITS [FOL21] index for embedded sensor networks applies a linear indexover its collected data, and the simplicity of the linear approximation indexallows it to run efficiently on an embedded device.More conventional indexes are used in applications where the timestampsare not guaranteed to be evenly spaced apart. B-Tree indexes are a well stud-ied topic, and are commonly used in database management software. TheLittleTable [RWW+17] time series database makes good use of B-Tree in-dexes, allowing it to group relevant data together so that it can be readsequentially to improve performance. B-Tree indexes have a larger mem-ory footprint than indexes based on a linear regression, making them moredifficult to implement on low power devices. B-Tree implementation forembedded devices [OFL21] has good performance but is not optimized forsorted timestamp keys.Learned indexes attempt to retain the flexibility of conventional indexeswhile reducing the memory footprint so that they can be used on a widervariety of devices. In recent years, learned indexes have seen considerableresearch, resulting in a number of different approaches which will be exploredin the following section.2.10 Learned IndexesConventional database indexes typically utilize data structures that havebeen optimized for a large variety of dataset types to ensure database perfor-mance remains adequate in a wide range of usage scenarios. Contrarily, someother database indexes use data structures that are optimized for a specifictype of dataset. These specialized database indexes outperform their moregeneral-use counterparts in specific use cases, but may have other use casesin which they perform much worse or are wholly inapplicable. Learned in-dexes seek to combine the versatility of general-use database indexes withthe performance of specialized indexes by devising an indexing scheme thatdynamically optimizes for each individual dataset, rather than a type ofdataset or a wide range of datasets. Machine Learning (ML) techniques arecommonly used in learned indexes, as they can train on samples of datasetsto learn the patterns and trends within a specific dataset. Database indexescan be reformulated into common ML problems which have already seen ex-tensive research and development, such that existing ML techniques can be402.10. LEARNED INDEXESapplied. For example, B-Tree indexes can be reformulated as a regressiontree problem, as the main point of such indexes is to map keys to a positionwithin a larger range of values [KBC+17]. Figure 2.12 shows the structure ofa typical regression tree with ML models forming the nodes. ML models arealso able to train on the type of queries that are most commonly executedin deployment. This allows for the model to further optimize for a specificusage scenario by optimizing the indexing structure to favour the parts of thedataset that are most frequently accessed in addition to the overall structureof the dataset itself. The resulting generated model takes the place of thedata structure used in conventional database indexes.Figure 2.12: Learned IndexesMathematical models can also be used in learned indexes. These modelscan be built with guarantees of error and transparency of functionality thatare difficult to achieve with ML models. Learned indexes can be built fromthe bottom up, or from the top down. Models created from the top down aretrained to capture the overall trend of a dataset as the top layer, then lowerlayers are used to narrow down the search range and reduce error until therequired specificity is achieved. This has the benefit of being able to closelyoptimize for datasets, but tend to be inflexible to changing data trends andmay need periodic retraining to maintain performance. Models created fromthe bottom up first fit the bottom layer to the points within the dataset towithin a tuneable error bound. Additional upper layers are then built ontop of the bottom layer to optimize querying performance when searchingthe bottom layer. Certain bottom up approaches have the capability todynamically fit their models to suit new data points as they are inserted412.10. LEARNED INDEXESinto the database, resulting in a model that is more flexible to changing datatrends. In this work, the PGM and RadixSpline indexes will be benchmarkedand compared to gather performance data using real-world datasets.2.10.1 RMIThe creation of the Recursive Model Index (RMI) [KBC+17] was moti-vated by the lacklustre performance of implementing a learned index usingexisting tools in Tensorflow and Python. These tools were designed to runlarge, complex models and have significant invocation overhead when run-ning the relatively simple models used in learned indexes. Additionally, naivelearned indexes composed of ReLU nodes are good at generalizing the overalltrend of an index distribution, but struggle when asked to produce preciseresults with a narrow error range.RMI addresses these limitations by incorporating a streamlined systemfor executing learned models without the overhead associated with Tensor-flow, Python, and other existing tools. Dubbed the Learning Index Frame-work (LIF), this framework is capable of extracting the weights of a trainedTensorflow model, and execute it efficiently in C++ without invoking anactual instance of Tensorflow. Using this framework, a recursive hierarchy oflearned models is built, with each model selecting the next model to be usedon the next level down the hierarchy of models. The general structure ofRMI is shown in Figure 2.12. This approach recursively appoints a segmentof indexes that a single model is responsible for. Compared to using a larger,more complex model to predict indexes with the same granularity and ac-curacy, a hierarchical collection of models is able to decouple its overall sizeand complexity from the execution cost. This is partially attributed to thefact that only a few select models are evaluated with any given index query,whereas a monolithic model must be evaluated in its entirety to fulfill anindex query. Additionally, the upper level models of the hierarchy are stillable to learn the overall shape of the distribution of indexes. This exploitsthe ability of neural networks to fit general trends in the data and still retainaccuracy by leaving the precise predictions to other models that are trainedseparately.The RMI model is created using a recursive method from the top-down,starting with a model trained on the complete dataset. Using the predictionsgenerated from this root-level model, the models to be used on the next leveldown are chosen and the keys that this lower-level model is responsible forare added to a list. This list is then used to perform the actual training onthe lower-level model. This process is repeated recursively for a specified422.10. LEARNED INDEXESnumber of models per level and total number of levels. The errors for themodels on the last levels are also stored so that the errors can be comparedagainst the error threshold set by the user. In the case of an exceptionallyhard-to-learn data distribution where a model’s error exceeds the threshold,that model is replaced with a B-tree.This recursive structure of models are able to significantly outperformconventional B-tree indexes on a dataset composed of 200M log entries forrequests to a university website while being a fraction of the size of the B-tree. While this is impressive, this indexing structure was developed with thedatacenter in mind, requiring the sequential computation of multiple neu-ral networks with numerous hidden layers each. For systems with heavilyconstrained hardware resources, other options are also available for consid-eration.2.10.2 PLAThe PLA (Piece-wise Linear Approximation) functions [EEC+09a] area set of two filtering techniques that are applicable to time series indexing.These filters aim to compress the space requirements needed to store a timeseries dataset within a given error bound, while minimizing memory usageand maximizing the compression ratio. The two filters introduced are namedthe Swing filter and the Slide filter. They are both approaches that utilizelinear functions to compress an input stream of data. This is similar to thesegmented linear regression problem, where linear functions of least squarederror are fitted to sub-divided segments of a larger data set. Ways to de-termine the best segment sub-partitions have been the subject of previousresearch in the past, where it has been solved using dynamic programmingtechniques [Fed75]. However, unlike the segmented linear regression prob-lem, an important distinction of PLAs is that it does not minimize the errorof the linear functions. PLAs fit the underlying data points with a guaran-teed error bounds set by the user, and thus allow for more flexibility for useas an index.The Swing filter implementation proposed by the authors uses a seriesof continuous linear line segments that approximate the input data. Thefirst element to be inserted into the swing filter forms the origin point of thefirst linear line segment. After the first point is inserted, a pair of boundingslope lines are created with their origins at the inserted point. One linerepresents the maximum slope that the current line segment can possesswhile still keeping the guaranteed error bounds, and the other line representsthe minimum slope. Subsequent points entered into the swing filter are432.10. LEARNED INDEXESevaluated to see if they land within the region bounded by these lines. If thenew point lands within the region, then this point is not recorded as it can berepresented by the current linear segment. Instead of recording the segment,the slope lines “swing” up or down to reflect the new maximum and minimumslopes of the current line segment (that now incorporates the newly insertedpoint). If the new point falls outside of the region, the current line segmentends. An optimization process determines the best slope that minimizes themean square error of all the points covered by the current line segment, thenensures that it falls in between the upper and lower bounding slope lines.This process uses a procedural summation process that can be generatediteratively and does not require the buffering of any points. The generatedslope is then extrapolated to form an optimized point to be recorded. It isalso used as the starting point for the creation of a new line segment to coverfuture insertions.Similar to the Swing filter, the Slide filter maintains a set of upper andlower hyperplanes. However unlike the Swing filter, the Slide filter is notguaranteed to generate a set of continuous linear segments. This meansthat the starting point of a given line and the ending point of the pre-vious line are not guaranteed to be the same point. The Slide filter de-scribes a method on how to choose upper and lower bounding hyperplanes.In summary, given a set of points to be covered by a single line segment(tk, xk), (tk+1, xk+1), (tk+2, xk+2), (tk+3, xk+3) . . . (tn, xn) the lines that passthrough (tk, xk), and (tk+1, xk+1) for all points such that i >= 1, and allpoints are within ϵ in the x-axis should be considered as candidate boundingupper and lower bounding lines. The candidate line with the lowest slopeshould be chosen as the bounding line for the upper bound, and the linewith the highest slope should be chosen as the bounding line for the lowerbound. Another process further optimizes bounding line selection by provingthat only the points belonging to the outer hull of the points encounteredneed to be evaluated for the bounding line candidacy, while the other pointscan be safely added without selecting new upper and lower bounding lines.Furthermore, the Slide filter also attempts to create continuous lines by off-setting the starting point of a new line. This is only possible if an intersectbetween the current line starting at (tk, xk) and the previous line ending at(tk−1, xk−1) occurs between tk and tk−1. The slide filter algorithm uses theseupper and lower bounds to calculate an optimal series of lines using the sameslope optimization method used in the Swing filter. These line segments arethen recorded in place of points.442.10. LEARNED INDEXES2.10.3 PGMThe PGM index [FV20] operates in a similar manner to the PLA Slidefilter, as it also dynamically creates a series of linear models which gives anapproximate page location within a configurable guaranteed error margin.However, instead of maintaining the minimum and maximum slope lines foreach linear segment, the PGM index forms linear line approximations usinga greedy method which attempts to fit a bounding box with a height of 2ϵaround the incoming data points. This bounding box can be rotated to orientitself along any slope to fit points. When PGM encounters a new point thatdoes not fit within the bounding box containing the previously encounteredpoints, the line representing the previous bounding box is added to the indexas a PGM linear segment, and a new bounding box is created. This processalso forgoes the optimization process described in the Slide filter, resulting ina less optimal but also less resource intensive indexing scheme that is bettersuited for resource constrained embedded devices. PGM linear segmentsare represented by three components, a slope (float), a key (int), and a x-intercept (int). The float and the x intercept are used to define the lineitself, and the key is used to specify the starting range when the linear linesegment should be used. To query this index, we conduct a binary search onthe keys of the PGM linear segments to find the correct linear segment thatservices the range of timestamps being requested. After the correct linearsegment is found, the slope and x-intercept of the line segment are combinedwith the queried timestamp to generate a page number that is guaranteedto be within ϵ of the real page number. A PGM model fitted to a time seriesdataset is shown in Figure 2.13, note the disjointed line segments generatedby the PGM model. Table 2.5 shows the approximate values of the linearsegments generated by PGM, and the calculations on Figure 2.13 uses thistable to compute the approximate page location of the record recorded witha timestamp of 610k. The slope and intercept of the PGM entry with thenext lowest key (compared to the search key) is used to compute the lineequation which generates an approximate page location of the search key.Key Intercept Slope588k 0 6.63 ∗ 10−4600k 9 9.87 ∗ 10−4606k 16 1.37 ∗ 10−3620k 37 1.83 ∗ 10−3Table 2.5: PGM Index Points452.10. LEARNED INDEXESFigure 2.13: PGM Query2.10.4 SplineIn the original work for the Radix Spline indexing model [KMvR+20],the argument was made that an efficient build process is sufficient to replacethe functionality for supporting insert operations. This efficiency is veryadvantageous in an embedded environment such as a distributed sensor net-work, and the lack of insert support can be averted since the sensor networkwill only append the latest readings into a time-series database. Like thePGM model, the Spline model also creates a series of linear segments thatapproximate the page locations for a certain timestamp with a configurableguaranteed error. Unlike the PGM, spline does not create independent linesthat are fit over a defined range of timestamps. Rather, spline forms linearline segments by connecting points to one another similar to the contigu-ous linear segments generated by the PLA Swing filter. Unlike the Swingfilter, Spline does not keep track of the minimum and maximum boundingslope lines. Instead, Spline points are chosen using a greedy method thatevaluates whether a new point would violate the error guarantees defined bythe user. Starting with a single origin point, a line is drawn from the originpoint to each new point as they are entered indexed by the spline model. Ifthe new point violates the error bounds, a spline linear segment is createdthat connects the origin point with the last point which did not violate the462.10. LEARNED INDEXESerror constraint. The last point then also becomes the new origin point, anda new spline line segment is started. Much like PGM, the Spline processalso forgoes the optimization process described in PLA which attempts tominimize the mean square error of the generated line, but also results in asimpler algorithm that is well suited to run on hardware constrained embed-ded devices. A Spline model fitted to a time series dataset is shown in Figure2.14, note the continuous line segments generated by the Spline model. Ta-ble 2.6 shows the approximate values of the linear segments generated by theSpline index, and the calculations on Figure 2.14 uses this table to computethe approximate page location of the record recorded with a timestamp of610k. The two bounding spline points of the search key are located in thespline table, and the slope between them are calculated. This slope is thenmultiplied by the offset of the search key from the lower spline point, andthe min value is added as the intercept to generate the approximate pagelocation of the search key.Key Min Value599k 7601k 10605k 12611k 24616k 29621k 39627k 48Table 2.6: Spline PointsIn the original work, a Radix indexing scheme was applied on top of theSpline model. This additional index is used to speed up access times onvery large datasets that generate a large number of spline points. In theuse case benchmarked in this work, the speed increases were minimal andnot worth the additional memory overhead required to store the radix index.The querying process for the spline index is similar to that of the PGMindex. First, a binary search is conducted on the keys of the spline linesegments to find the correct segment that services the range of timestampsthat the queried timestamp resides within. The slope between the currentspline point and the next spline point is computed. This slope is then usedas a linear interpolation to return a page number guaranteed to be withinϵ of the true page number which contains the data corresponding with thequeried timestamp.472.10. LEARNED INDEXESFigure 2.14: Spline Structure2.10.5 Comparison between Spline and PGMBoth Spline and PGM create a series of linear line segments that providean approximate page number that contains the data for a given input key.The advantage of PGM lies in the fact that it can create completely inde-pendent line segments to represent the underlying data. The Spline model,by comparison, must create lines that are formed by drawing lines betweenexisting data points of the data set. This generates less optimal linear linesegments compared to the lines generated by PGM, but in return, Spline isable to use less data to store each individual line segment as it only needsto store a key and a page number. By comparison, PGM must store a keyand page number, plus an additional slope variable for each line segment. Inthe later experimental sections, we will explore the real world performanceof both indexing methods, along with the performance of binary search anda simple linear model across the entire dataset.When applied to time series datasets, both indexes are able to generatea series of linear approximations fitted to the underlying data. A graphicalcomparison between the two models is shown in Figure 2.15. Note the dis-jointed nature of the PGM approximation, and the continuous nature of theSpline approximation. This is a result of the PGM model being capable ofgenerating completely independent lines for each linear segment, whereas the482.10. LEARNED INDEXESlinear segments generated by the Spline model must originate and terminateon existing data points.Figure 2.15: Spline and PGM Models Fitted Over Time Series Data49Chapter 3MethodologyTo create an index structure for use in embedded sensor nodes, it isimportant to understand the data operations that sensor nodes perform whilethey are in use. Embedded sensor nodes collect sensor values and storethem for future retrieval and processing. Attached sensors are periodicallypolled to generate new readings, which are stored in sequential order on astorage device. This generates a dataset of sensor records that are naturallyordered by the timestamp at which they were taken. These sensor recordsare iteratively appended to storage as they are taken and are never modified,resulting in an append-only database. An index applied on this data willalways access an ordered dataset, but will need to support iterative appendsas new sensor readings are taken at subsequent sampling intervals.A learned index model adapted for use in embedded sensor nodes mustsupport append operations while keeping memory consumption low. Further,learned indexes only apply to indexing the sensor data by timestamp asrecords are stored in a sorted file by timestamp as they are collected. Learnedindexes do not directly apply to indexing the data (sensor values) in therecord, which are not stored in sorted order.We focus on adapting bottom-up, eCDF based learned indexes. Indexesthat are built bottom-up such as the RadixSpline do not require all the datain advance, in contrast to top-down modeling approaches such as RMIs thatrequire all data in advance and cannot be easily deployed for the time seriesuse case. We adapt and deploy two structures for indexing: the RadixSplineand the PGM Index.An ϵ value of 1 was chosen for both the PGM and Spline learned indexes.This error bound represents a balance between memory usage and accuracy,where a ϵ of 0 is very strict and generates a large number of index entries.The size of the data sets used to generate experimental results (shown inTable 5.2) did not necessitate any further reductions in memory consump-tion. Further relaxations of the error bounds do translate into an additionalreduction in memory consumption, but these reductions are not as large asthe initial memory reduction from changing ϵ from 0 to 1 (as demonstratedusing the SEA data set in Table 5.4). The radix table was omitted from the50RadixSpline index, as relatively small number of spline index points gener-ated did not benefit from using an additional radix table to speed up lookupoperations for spline points. These tuning decisions will be further exploredin Section 5.The indexing approach is based on SBITS [FOL21] and proceeds as fol-lows:− Each data record containing collected sensor values is stored in abuffered page in memory until the page is full.− A full data page is written to the sorted data file in sequential order.− After the page is written, an index record is created storing the times-tamp of the smallest record on the data page and the data page index.− The index algorithm must maintain its index structure in memory witha bounded size (often less than 1 KB) and may periodically flush indexpages to storage for persistence.This procedure was implemented with efficiency in mind. By bufferingdata records in memory until a full page can be written, we avoid needingto update the same data page on the storage multiple times for multipledata records, which helps to minimize the erase-before-write characteristicsof flash storage. These data pages are then stored in the order which theyare created, which is ordered by timestamp. This ordered set of pages arethen inserted into the indexing algorithm, which uses the minimum times-tamp of each page as the search bounds for queries returned by the index.Generated indexes often have less than 1 KB due to the efficiency of learnedindexing structures. This is beneficial to scale down hardware requirementsfor deploying learned indexing structures on lower power embedded deviceswhich may have power consumption and cost advantages.SBITS has been demonstrated to outperform conventional B-tree andhashing indexes in time series data [OKFL22b], so comparisons with thosedata structures are not performed. Additionally, when inserting records in anordered, ascending manner, the self-balancing characteristic of B-tree datastructures means that it must perform frequent re-balancing operations toavoid becoming right-heavy. These re-balancing operations incur significantoverhead compared with linear indexes and the Spline and PGM learned in-dexes being evaluated, since they are generated iteratively and do not requiresuch operations. Querying by timestamp is performed by using the index.Querying by data value is unchanged from the previous SBITS implementa-tion as learned indexes do not apply to the unsorted data values.513.1. PIECE-WISE GEOMETRIC MODELS3.1 Piece-wise Geometric ModelsThe Piece-wise Geometric Model index (PGM) is a learned index thatapproximates the CDF via piecewise linear approximations (PLA) [FV20].At the heart of the PGM lies a hyperparemeter ε that controls the errorbounds for the linear approximations.The original PGM index is built from the bottom-up recursively. At thefirst level, the PGM builds a PLA over the set of points {(xi, i)}i=0...n usingthe optimal algorithm proposed by [O'R81] and rediscovered by [EEC+09b].For subsequent levels, the PGM applies the same linear approximation strat-egy using the keys from the previous level {(kj , j)}j=0...s as points for thePLA. The recursion halts when there is a level with exactly one line.We adapt the PGM by creating an append method described in Algo-rithm 1. Notice that the method does not know the number of levels for thePGM in advance and starts by appending a key to the linear approximationat the bottom level and propagating the updates to the upper levels if nec-essary. Another modification of our implementation is the use of the SwingFilter algorithm also proposed by [EEC+09b]. The Swing Filter does notyield an optimal number of lines, but requires only O(1) time and memoryto process a point. This is a benefit in the sensor use case, as the optimalSlide Filter requires O(h) memory in its worst-case where h is the numberof points in the convex hull, which might not fit in-memory. Even thoughwe adapted the PGM to support appends, its procedure for finding a keyremains unchanged from the original PGM (see Algorithm 2).3.2 RadixSplineThe RadixSpline is a learned index that approximates the CDF via alinear spline and a radix table storing spline points [KMvR+20]. The twohyperparameters that shape the RadixSpline are ε, the error bound for thespline approximation, and r, the size of the prefix of the radix table entries.The RadixSpline builds an error-bounded linear spline over the empiricalCDF using the greedy algorithm proposed by [NM08]. After the spline isbuilt, the prefixes of the spline points are inserted in a radix table. The radixtable is a flat array of size 2r where each entry in the table maps to a rangein the spline.Querying for a point in a RadixSpline is done in three steps. The firststep is to look for the prefix of the key being searched in the radix table,and find the corresponding spline point. Given the spline point, calculate a523.2. RADIXSPLINEAlgorithm 1: AppendPGMAdd(pgm, x)L← pgm.countLevels();K ← x;for i← 0 to L− 1 doc← pgm.levels[i].countPoints();pgm.levels[i].add(K); // add implements the Swing Filterif pgm.levels[i].countPoints() > c thenK ← pgm.levels[i].getLastKey();elsereturn;endend/* If the algorithm reached this step create a new level */pgm.levels[L] = newPGMLevel();firstK ← pgm.levels[L-1].getFirstKey();lastK ← pgm.levels[L-1].getLastKey();pgm.levels[L].add(firstK);pgm.levels[L].add(lastK);return;Algorithm 2: QueryAppendPGM(pgm, x)if x < pgm.levels[0].getFirstKey() thenreturn NotFound ;endL← pgm.countLevels();m← 0; // index of the model at the i-th levelfor i← L− 1 to 1 doa← pgm.levels[i].getSlope(m);b← pgm.levels[i].getIntercept(m);pos ← ⌊a · x+ b⌋;lo ← max{0, pos− ε− 1};hi ← min{pgm.levels[i].countKeys()− 1, pos+ ε+ 1};m ← smallest value of j such that x ≥ pgm.levels[i-1].getKey(j) andlo ≤ j ≤ hi;enda← pgm.levels[0].getSlope(m);b← pgm.levels[0].getIntercept(m);pos ← ⌊a · x+ b⌋;lo ← max{0, pos− ε− 1};hi ← min{pos+ ε+ 1, pgm.levels[0].countKeys()− 1, };/* Search is an implementation of binary search or linearsearch over the original array containing the keys */return Search(x, lo, hi);533.2. RADIXSPLINEnarrow range of size 2ε where the key could be using linear interpolation.The last step is to find the key in the range using linear or binary search,which is a quick operation because 2ε is constant.We adapted the RadixSpline to support appends by implementing astreaming version of the GreedySpline proposed in [NM08], as describedin Algorithm 3. After appending a point, we check if we can adjust the lastspline segment to correctly approximate the point position within ε. If thatis not the case, we create a new spline segment covering the new point andpropagate the new spline point to the radix table (see Algorithm 4).Algorithm 3: RadixSplineAdd(rs, x)c← rs.spline.countPoints();rs.spline.add(x); // Add implements GreedySplineif rs.spline.countPoints() > c thenK ← rs.spline.getLastKey(); RadixTableInsert(rs, K, c); // seeAlgorithm 4return;endreturn;543.2. RADIXSPLINEAlgorithm 4: RadixTableInsert(rs, K, pos)r ← rs.r; // radix prefix sizeK ← K - rs.minKey;nB ← mostSignificantBit(bitShiftRight(K, rs.shiftSize)); // number ofbits required to fit on the table∆← max(nB - r, 0); // difference between the available andrequired number of bitsif ∆ > 0 then/* New key triggers table rebuild with new prefix size inorder to fit; we merge the old radix entries consideringthe new bit shift */rs.shiftSize ← rs.shiftSize + ∆;newTable ← allocateTable( 2r );for i← 0 to 2r doj ← bitShiftRight(i, ∆);newTable[j] ← min(rs.table[i], newTable[j]);endfor i← 2r−∆ to 2r donewTable[i] ← INT_MAX;endrs.table ← newTable;end// Update entry of the radix table with the new posT ← bitShiftRight(K, rs.prefixSize);rs.table[T] ← min(rs.table[T], pos);return;55Chapter 4Implementation4.1 Radix AdaptationAs discussed, append support for the RadixSpline was implemented us-ing the streaming GreedySpline [NM08]. To accommodate this feature, theRadix portion of RadixSpline was also modified to support appends. TheRadix structure operates over a set of key-value pairs, mapping a specifiednumber of leading bits from keys to the values associated with the keys.This results in a mapping structure where the value of the first encounteredkey with a certain bit prefix is mapped to all subsequently encountered keysthat share the same bit prefix. Time series data is well suited for the Radixstructure as it naturally maps timestamps to the bounding search index in anarray of time series data. The approach for supporting appends on Radix wassimilar to the approach for GreedySpline. In the base Radix implementation,the first point inserted into the Radix structure is stored as the ‘minKey’value that will be subtracted from future incoming values. Future incomingpoints will then have minKey deducted from their values, the resulting valuewill have its leading zeroes counted. This count is used to verify whetherthe number of significant bits of the incoming key will fit within the numberbits that the Radix table was initialized with. The resulting value with theleading zeroes removed is called the ‘prefix’, which will then be checked tosee if it will fit within the specified number of Radix bits and indexed accord-ingly if it is. If the prefix does contain more bits than the specified numberof Radix bits, the least significant bits are discarded from the prefix (right-shifted) until the prefix fits inside the Radix index. The base implemen-tation of the Radix table did not support continuous appends, and as suchdid not account for a variable number of significant bits from incoming keys.This variability changes the number of right-shifts required on incoming keysbefore they are indexed. To remedy this, the current number of right-shiftsare stored in memory and compared against the right shifts required by fu-ture keys. If an incoming key has a higher number of significant bits, arefactoring process is executed on the existing Radix table. This processshifts all existing values in the Radix table by the difference in significant564.1. RADIX ADAPTATIONbits of the incoming key and the stored right-shift value. After this process,all keys which share significant bits within the Radix table are discarded,only leaving the first key-value mapping that matches the updated prefix.This process repeats each time a new key is inserted into the Radix structurewith a higher number of significant bits, allowing for a continual insertionof increasing keys. Figure 4.1 illustrates the refactoring process that occurswhen a new data entry (8 in this example) is inserted into a fully populatedradix table. Note the shifted prefixes, and how the radix becomes a sparseindex (having been a dense index before). A dotted line is used to indicatethat the new maximum value that can be stored using the refactored radixtable is 15, while the previous maximum value was 7.Figure 4.1: Radix Table Expansion574.2. MEMORY4.2 MemoryThe PGM and Radix Spline index structures are both stored in a dy-namically allocated block of contiguous memory. The location estimatesgenerated by the indexing mechanisms are then applied as byte offsets tothe storage pointer, where the corresponding index value can be retrieved.4.3 SD CardsSD cards are a popular choice for embedded devices due to their low costand compatibility with the SPI data communication interface. SD cardsconsist of a NAND package, and a controller chip to handle FTL operationswithin the chip that converts block addresses to physical flash addresses. SDcards can be configured to operate in SPI mode, which eliminates the needfor an external SD controller to interface with the storage device. In thismode, SD cards operate like a standard block device, using standardizedSPI commands for reading and writing data. In the sensor hardware testplatform, the test datasets are loaded from an SD card to be inserted into theon-device database where the performance of the PGM and Spline indexesare evaluated.4.4 DataflashThe sensor hardware platform used to gather experimental results recordsall inserted data points onto dataflash storage1. Dataflash storage consistsof NOR memory instead of the NAND memory found in conventional flashstorage. NOR memory differs from NAND in its structure, which allowsfor each data page to be individually cleared whereas NAND flash mustclear an entire block (consisting of multiple pages) at once [FPL16]. Thedata inserted into storage in testing is append-only, and inserted data isimmutable. This storage type allows for records to be inserted one pageat a time as they are taken, whereas NAND implementations must bufferan entire flash block at once before writing to storage to avoid incurring theoverwrite penalty associated with in-place updates. Like SD cards, Dataflashalso communicates with the sensor device using the SPI protocol.1https://www.dialog-semiconductor.com/products/memory/dataflash-spi-memory584.5. SPI PROTOCOL4.5 SPI ProtocolFiles stored on SD cards attached to the embedded device accessed viaSerial Peripheral Interface (SPI) are managed by the SdFat library. TheDataflash storage are also attached using the SPI protocol.4.6 FAT File SystemThe FAT file system is named after the File Allocation Tables it uses tokeep track of data clusters on a disk. It is a popular choice for embeddedapplications due to its simplicity, maturity, and cost-effectiveness.Compared with other file systems like NTFS or HFS, FAT has a sim-pler design that is easy to implement, has a smaller memory footprint, andrequires less processing power. These characteristics make FAT very wellsuited for low power embedded devices with limited hardware resources.The FAT file system is also supported by most modern operating systems,owing to its widespread usage as the default file system of the MS-DOS fam-ily of operating systems. This wide support-base makes inter-compatibilitybetween different operating systems and devices much more convenient.FAT is also open-source and royalty free, meaning that developers lookingto implement the FAT file system do not have to pay licensing fees to agoverning body. This makes FAT a cost effective solution for embeddeddevices that are typically deployed in large fleets.The FAT file system was chosen to facilitate cross compatibility andeasy transfer of datasets onto the hardware test platform when conductingexperiments.4.7 Data Transfer From SD CardsThe full process for reading the contents of a file from an SD card isas follows, all read operations are performed using the standardized SPIcommands.1. The boot sector of the SD card is read to find the location of the FileAllocation Table (FAT).2. The root file directory is read using the FAT table to find all the clustersthat the root file occupies, then reading those clusters.594.8. DATA TRANSFER TO DATAFLASH USING SPI3. The root file directory contains information (including the location oftheir first clusters) on all the files and sub file directories stored in theroot directory.4. If the file of interest is not located in the root directory, sub file directo-ries are traversed recursively until the correct sub directory is reached.5. The file directory is read to find the starting cluster of the file of inter-est, and the FAT table is again used to locate all the clusters pertainingto the file being read.6. Clusters are read one at a time into the host device, since limitedresources are available and it is not advisable to read the entirety of afile into memory.These operations are handled by the SdFat library. The process forwriting a file onto the SD card using SPI is similar to the process for readinga file, the main difference being that the SPI command for write operationsare used instead of read operations when the correct file is located.4.8 Data Transfer to Dataflash using SPINo file system is used on Dataflash to maintain simplicity and reduceoverhead on the embedded device. Drivers for the Dataflash storage werecreated as part of the IonDB project [FHD+15] which had the capabilityto use the same type of NOR flash storage. The Dataflash drivers includefunctions for:− Initializing the flash structure− Erasing the entire flash chip− Reading bytes from a flash data page− Writing bytes into a flash data pageSince only a single file was used to store records, a file system is notnecessary on the Dataflash storage. Compared to FAT, this streamlined rawstorage system is easy to implement and reduces overall overhead.604.9. BUILD ENVIRONMENT4.9 Build EnvironmentAll code is implemented in C due to its low abstraction, allowing directaccess to pointers for manipulating data structures. C is also widely sup-ported by the majority of major hardware platforms, enabling portability tosystems manufactured by different vendors.Figure 4.2: Custom Development Board With Integrated NOR DataflashFigure 4.3: Desktop Environment of Platform.io Extension on Visual StudioCode614.9. BUILD ENVIRONMENTTests were evaluated on a SAMD21 processor and a development boardthat has been modified to include onboard NOR dataflash storage (shownin Figure 4.2). Compilers and build setup for this platform is handled byPlatform.io, which has a plugin for Visual Studio Code (pictured in Figure4.3). It includes a library of compilers and needed build scripts for a varietyof embedded platforms (Atmel SAM, Raspberry Pi, Espressif32, etc). In thecase for the SAMD21 processor, the ARM GCC compiler is used.62Chapter 5ResultsWe choose to evaluate querying performance using the Spline and PGMlearned indexes as well as the linear index implemented in SBITS. The ex-periments measure four core metrics: the query throughput, the number ofIOs per query, memory consumption, and insertion throughput. These met-rics are relevant to common use cases of sensors such as querying by times-tamp and ingesting new data. We report the average of the metrics basedon three separate runs. The real-world data sets evaluated are in Table 2.The data sets cover a variety of sensor use cases including environmentalmonitoring, smart watches, GPS phone data, and chemical concentrationmonitoring. The environmental data sets sea and uwa were originally from(Zeinalipour-Yazti et al., 2005) and have been used in several further exper-imental comparisons (Fazackerley et al., 2021; Ould-Khessal et al., 2022).We also present the eCDF for the datasets in Figure 1.The experiments evaluated sensor time series indexing for multiple real-world data sets. The sensor hardware platform has a 32-bit MicrochipARM® Cortex® M0+ based SAMD21 processor with clock speed of 48MHz, 256 KB of flash program memory and 32 KB of SRAM. The hardwareboard has several different memory types including a SD card and serial NORDataFlash2 which supports in-place page level erase-before-write. This plat-form is representative of embedded devices with commonly used 32-bit ARMprocessors. The serial NOR DataFlash was used to test performance on rawmemory without a flash translation layer (FTL). Testing on raw memoryinsures no overhead with FTL maintenance operations and allows for thehighest read performance. Platform performance characteristics are in Ta-ble 5.1.The experiments benchmark four indexes:− Binary Search: A binary search over the sorted data. This is thebaseline for the benchmark and requires no additional memory.2https://www.dialog-semiconductor.com/products/memory/dataflash-spi-memory63− SBITS: SBITS using linear interpolation requires 8 bytes to maintainlinear approximation. SBITS was optimized to default to binary searchif its predictions were off significantly.− PGM: A modified version of the PGM Index with support for appendsand error-bound of ε = 1.− RadixSpline: A modified version of the RadixSpline with support forappends, error-bound set to ε = 1 and radix prefix size of r = 0 thatoffered the best performance with smallest memory usage.The experiments measure four core metrics: the query throughput, thenumber of IOs per query, memory consumption, and insertion throughput.These metrics are relevant to common use cases of sensors such as queryingby timestamp and ingesting new data. We report the average of the metricsbased on three separate runs. The real-world data sets evaluated are in Table5.2. The data sets cover a variety of sensor use cases including environmen-tal monitoring, smart watches, GPS phone data, and chemical concentrationmonitoring. The environmental data sets sea and uwa were originally from[ZYLK+05] and have been used in several further experimental comparisons[FOL21, OKFL22a]. We also present the eCDF for the datasets in Figure5.1. From the eCDF graphs, the phone and watch datasets are of particu-lar interest since they have the most variable sampling rates out of all thedata sets used. Considering the ability of learned indexes to better fit anunderlying eCDF compared with conventional indexes, experimental resultsgenerated using these data sets should be closely examined.Reads (KB/s) Writes (KB/s)Seq Random Seq Random Write-Read RatioM0+ SAMD21 (DataFlash) 475 475 38 38 12.5Table 5.1: Hardware Performance CharacteristicsName Points Points Used Sensor Data Sourcesea 100,000 100,000 temp, humidity, wind, pressure SeaTac Airportuwa 500,000 500,000 temp, humidity, wind, pressure ATG rooftop, U. of Wash.hongxin 35,064 35,000 PM2.5, PM10, temp [ZGD+17]ethylene 4,085,589 100,000 ethylene concentration [FSHM15]phone 18,354 18,000 smartphone X/Y/Z magnetic field [BCRP16]watch 2,865,713 100,000 smartwatch X/Y/Z gyroscope [SBB+15]Table 5.2: Experimental Data Sets645.1. QUERY PERFORMANCE0.00.20.40.60.81.0Proportionuwa0.00.20.40.60.81.0Proportionsea0.00.20.40.60.81.0Proportionwatch0.00.20.40.60.81.0Proportionhongxin0.00 0.25 0.50 0.75 1.00Normalized Keys0.00.20.40.60.81.0Proportionethylene0.00 0.25 0.50 0.75 1.00Normalized Keys0.00.20.40.60.81.0ProportionphoneEmpirical Cumulative Distribution FunctionsFigure 5.1: eCDFs for the experimental datasets.5.1 Query PerformanceOne common use case of processing data in edge devices is to querytimestamps. We measure the query throughput for searching timestamps.After the sensor data was inserted, 10,000 random timestamp values werequeried in the timestamp range. Data was collected on the time to executeall queries and the number of IO operations performed.655.1. QUERY PERFORMANCE0 200 400 600 800Queries Per SeconduwaseawatchhongxinethylenephoneComparison of Query Throughput for the IndexesBinary Search SBITS PGM RadixSplineFigure 5.2: Average query throughput among the indexes for each dataset inthe benchmark. Higher rates indicate better results. The RadixSpline andPGM consistently outperform SBITS and binary search.The query throughput results are in Figure 5.2. Applying learned indexesto sensor time series is very effective. The PGM and the RadixSpline alwaysoutperform SBITS with significant improvements on highly variable datasets.For the hongxin and uwa datasets, the gains are more modest rangingfrom 1.05x-1.20x for the PGM and 1.06x-1.31x for the RadixSpline. Thesedatasets are highly linear such that an interpolation search achieves its best-case scenario. Since the PGM and RadixSpline use PLAs to model thedataset, they also perform well just like the interpolation search.However, datasets such as watch, ethylene, and phone prove to bemore challenging for SBITS. Its performance is affected and becomes closer to665.1. QUERY PERFORMANCEthe throughput of the binary search baseline. Learned indexes, on the otherhand, extend their lead and stay resilient to the change in data distribution.The performance gains range from 1.8x-8.9x for the PGM and 1.8x-10x forthe RadixSpline. This indicates that the learned indexes have more flexiblemodels that describe the data distribution better. For the smart watch andsmartphone devices that generated the watch and phone data sets, thisincrease in querying speeds will help enable more complex applications to runon these devices to efficiently process larger amounts of data. Additionally,this enables event driven and threshold driven data sampling, which haspower consumption benefits as the device can remain in a low power statewhen it is not taking sensor readings. This is in contrast to fixed sampling,where the device must periodically take sensor readings at specified timesregardless if the gathered data is meaningful. Learned indexes are able toindex data sets with highly variable sampling rates, so a fixed samplingrate (that works best with conventional indexes) is no longer necessary toefficiently process data.The query throughput difference between RadixSpline and PGM is within10% for all data sets. Since both approaches use linear approximations, thedifference relates to how the linear approximations are themselves indexed.For these experiments, the radix table for RadixSpline was allocated nospace, and only a binary search was used on the spline points. This iseffective as there are very few points. Performance testing with using aradix table of size r = 4 and r = 8 demonstrated no query performancebenefit while consuming precious RAM. This makes sense as the radix tableis only saving a few comparisons when searching the spline points in memory,and the search time is dominated by the IOs performed to the flash memory.PGM produces a multi-level index, which takes some more space and a littlelonger to query. Overall, both approaches are effective and greatly improveon binary search or single linear interpolation. The trade-off between thequery performance and memory space is discussed further in Section 5.2.Another relevant metric for querying is the number of IOs per query. Thenumber of IOs performed dominates the query response time and is especiallyimportant in embedded systems were predictable real-time performance isdesirable. Figure 5.3 displays the average number of IOs performed pertimestamp query. Binary search performs O(logN) IOs and has significantlymore IOs than the other approaches. SBITS’ single linear interpolation iseffective in many cases, however data sets like phone are poorly approximatedby one linear approximation and the algorithm frequently defaults to binarysearch due to poor prediction accuracy. Both PGM and RadixSpline haveguaranteed error bounds in their construction. With ε = 1, at most 2 IO675.2. MEMORY SPACE EFFICIENCY0 2 4 6 8 10I/Os per QueryuwaseawatchhongxinethylenephoneComparison of I/Os for the IndexesBinary Search SBITS PGM RadixSplineFigure 5.3: Average number of IOs per query among the indexes for eachdataset in the benchmark. Lower rates are better. Learned indexes signifi-cantly reduce the number of required IOs.are performed for any lookup with the average often around 1.3 to 1.5. Thispredictable performance is a major benefit for using these learned indexes.5.2 Memory Space EfficiencyIt is critical for learned indexes to have a small memory footprint in or-der to be useful for embedded systems. Many traditional techniques cannotbe applied to embedded systems because of the RAM constraints [FOL21],which prompts adaptations that trade memory and performance. The mem-ory results are in Table 5.3.685.3. INSERTION PERFORMANCEMemory Consumption (in KB)PGM RadixSplineuwa 0.04 0.09sea 1.88 0.96watch 7.80 2.43hongxin 0.10 0.07ethylene 0.40 0.12phone 1.09 0.25Table 5.3: Memory consumption comparison among the learned indexes foreach dataset in the benchmark.All indexes fit in memory, with the maximum amount of memory usedbeing 7.80 KB. The results indicate that the RadixSpline consumes less mem-ory than the PGM. This is to be expected, as both the spline and the bottomlevel of the PGM contain a very similar set of linear approximations. Thekey difference between the two is their approach to finding the linear ap-proximation to use. The RadixSpline uses a small radix table to index splinepoints. The PGM uses a recursive approach building additional PLAs. Sincethe size of the table from the RadixSpline is parametrized by r, it is possibleto sacrifice a little query performance to achieve less memory usage.For our choice of r = 0, the difference in memory consumption is signif-icant, and the difference in query performance is negligible as performanceis dominated by the number of IOs not comparisons in memory. The PGMuses two to four times the amount of memory as the RadixSpline for five outof the six datasets, with the exception being the easiest dataset uwa.By modifying the error bound (ϵ), both approaches can reduce their mem-ory footprint at the sacrifice of more query IOs and lower query throughput.Table 5.4 shows statistics on the index size in bytes, IOs performed perquery, and query throughput in queries/second for the sea data set for mul-tiple different values of ϵ. There is a quite significant index size reduction forincreasing ϵ to 2 or 3. Even though the IOs per query increases, it is alwaysbounded by ϵ. This allows designers to determine the exact performancetrade-offs in terms of space and query IOs in a predictable fashion.5.3 Insertion PerformanceAdding indexes benefits query performance, but they can also impactthe insertion time. It is critical for sensors to keep ingesting data; hence the695.3. INSERTION PERFORMANCERadixSpline PGMTest Index Size Query IO Throughput Index Size Query IO ThroughputSEA ϵ = 1 932 1.40 588 1920 1.42 557SEA ϵ = 2 436 1.85 461 856 1.91 440SEA ϵ = 3 260 2.23 386 664 2.26 376SEA ϵ = 5 212 3.12 281 496 3.41 256SEA ϵ = 10 132 5.37 166 232 4.94 179Table 5.4: Index Size in bytes, IOs per Timestamp Query, and QueryThroughput (queries/sec.) for Different Error Bounds ϵneed to monitor the insertion throughput to ensure they match the sensorsrequired sampling rate. For insertion performance, the N records used foreach data set were inserted at the maximum possible rate of the hardware.The insertion performance is dominated by the IOs for writing the datapages to storage, but the index construction time may have some overhead.The insertion rates in Figure 5.4 show the maximum rates possible on thehardware for each data set and index.The baseline for insertion performance is the binary search case whichconsists of a simple data record append and no indexing overhead. The aver-age throughput was 1967 inserts per second. Since the incoming timestampsare strictly increasing and because binary search does not store any addi-tional information to help on the search, this represents the upper bound forinsertion performance.SBITS and RadixSpline were the indexes that had the highest insertionthroughput at 1966 and 1965 inserts per second, respectively. They almostmatch the scenario with no index at all. The results are consistent withearlier experiments for SBITS [OKFL22a], showing that the number of IOsto keep the index up to date is minimal. Perhaps the most surprising resultis for the RadixSpline, because it needs to calculate spline points and updatethe radix table. Our benchmark shows that the overhead for these operationsare small.On embedded devices, an insertion rate of 2000 is high for the limitedhardware resources available. As shown in Figure 5.4, both the learned in-dexes support >1951 inserts per second which represents a less than 1%overhead. This small overhead indicates that the PGM and RadixSplinelearned indexes were implemented efficiently, without straining the limitedprocessing capacity of the embedded device. The PGM has a slightly lowerinsert rate because some insertions trigger changes on multiple levels of thePGM, while RadixSpline triggers at most one change in the spline and radixtable. The PGM insertion throughput remains competitive beating tradi-705.4. RESULTS DISCUSSIONtional embedded indexes such as B-Trees [OKFL22a].0 250 500 750 1000 1250 1500 1750 2000Inserts per SeconduwaseawatchhongxinethylenephoneComparison of Insertion Throughput for the IndexesBinary Search SBITS PGM RadixSplineFigure 5.4: Average insertion throughput among the indexes for each datasetin the benchmark. Higher rates indicate better results. The insertionthroughout is slightly lower for the PGM, but overall learned indexes re-main competitive.5.4 Results DiscussionOverall, the experimental results demonstrate that there are significantadvantages to using learned indexes adapted for embedded time series data.The most significant advantage is the predictable and bounded timestampquery performance. By specifying a given error bound (ε), the maximumnumber of IOs per query is 2ε + 2. The query performance is significantlyhigher than SBITS linear interpolation search or binary search. The overhead715.4. RESULTS DISCUSSIONof the index in terms of insertion throughput is minimal. To handle thelimited memory, the index size can be reduced by increasing the error bound.In the experiments tested, the index size was usually less than a few KB.The index algorithms support real-time sensor data collection of almost 2000records/second on the experimental hardware, which is significantly abovecollection rates for most applications.72Chapter 6ConclusionDatabases employ indexes to improve query performance. Many indexeswere originally developed before the prevalence of commercially viable flashstorage, and thus their original implementations do not account for the hard-ware characteristics that flash storage exhibits.Embedded devices use flash memory as the storage medium of choice,thus database systems running on embedded devices must also adopt designprinciples suitable for flash memory. These devices also have their own designconsiderations that must be accounted for, in addition to the considerationsfor flash memory.By adapting the PGM and Spline learned indexes to support continuousappends, we demonstrate that learned indexes are well-suited for time seriesindexing. Learned indexes have traditionally been developed in the con-text of being used as in-memory indexes running on large data centers, butthis work demonstrates the viability of such indexing methods on hardware-constrained embedded systems performing frequent append operations. Ex-perimental results further express the practicality of using learned indexes inan embedded environment, where we observe lower memory footprints andIO load compared with conventional indexes.The PGM and Spline indexes both easily fit within the 256 KB of avail-able memory on our embedded development platform (typical of commer-cially available embedded devices), with 7.8 KB being the largest recordedmemory consumption (used to index 100,000 entries in the watch dataset).As both the PGM and Spline indexes use linear approximations for their in-dexing structures, they also exhibit similar performance. The querying per-formance of the Spline and PGM indexes are within 10% of each other, withthe difference mainly being due to the multi-level structure of the PGM indextaking slightly longer to search. Insertion performance was also impressive,with both PGM and Spline demonstrating an almost negligible performanceimpact versus the simple linear index used in SBITS. This demonstrates ap-plicability in scenarios where a high throughput is required, such as real timemonitoring with high sampling rates.736.1. FUTURE WORK6.1 Future WorkFuture work will explore methods for auto-tuning the hyperparametersof the learned indexes to optimize performance with less user input. Anadditional challenge presents itself when considering the limited hardwareresources available to embedded devices, as any tuning operation must notconsume impractical amounts of memory or processing power. It may alsobe worth investigating whether a system can continuously monitor the pat-tern of the data being inserted. This could potentially allow for the systemto automatically recognize when the indexing method it is currently usingbecomes sub-optimal and change the indexing method used for future datasamples to one that is better suited to fit the detected data pattern. Thisfunctionality would also be subject to the limited hardware resources avail-able, and care should be placed to minimize the burden on memory usage.74Bibliography[AA14] Manos Athanassoulis and Anastasia Ailamaki. Bf-tree: Ap-proximate tree indexing. Proceedings of the VLDB Endowment,7:1881–1892, 10 2014. → pages 14[ALAB+20] Hussam Abu-Libdeh, Deniz Altınbüken, Alex Beutel, Ed H.Chi, Lyric Doshi, Tim Kraska, Xiaozhou, Li, Andy Ly, andChristopher Olston. Learned indexes for a google-scale disk-based database, 2020. → pages 2[BCRP16] Paolo Barsocchi, Antonino Crivello, Davide La Rosa, and Fil-ippo Palumbo. A multisource and multivariate dataset for in-door localization methods based on WLAN and geo-magneticfield fingerprinting. In 2016 International Conference on IndoorPositioning and Indoor Navigation (IPIN), pages 1–8. IEEE,October 2016. → pages 64[BFCJ+17] Michael A. Bender, Martín Farach-Colton, Rob Johnson, Si-mon Mauras, Tyler Mayer, Cynthia A. Phillips, and HelenXu. Write-optimized skip lists. In Proceedings of the 36thACM SIGMOD-SIGACT-SIGAI Symposium on Principles ofDatabase Systems, PODS ’17, page 69–78, New York, NY, USA,2017. Association for Computing Machinery. → pages 16[BGS01] Philippe Bonnet, Johannes Gehrke, and Praveen Seshadri. To-wards sensor database systems. In Proceedings - 2001 2nd In-ternational Conference on Mobile Data Management, volume1987, 01 2001. → pages 33[CFT07] Abdellah Chehri, Paul Fortier, and Pierre-Martin Tardif. Secu-rity monitoring using wireless sensor networks. In Fifth AnnualConference on Communication Networks and Services Research(CNSR ’07), pages 13–17, 2007. → pages 2775Bibliography[CJY10] Kai Cui, Peiquan Jin, and Lihua Yue. Hashtree: A new hybridindex for flash disks. In 2010 12th International Asia-PacificWeb Conference, pages 45–51, 04 2010. → pages 17[CMB+10] Mustafa Canim, George Mihaila, Bishwaranjan Bhattacharjee,Christian Lang, and Kenneth Ross. Buffered bloom filters onsolid state storage. Proceedings of the 1st International Work-shop on Accelerating Data Management Systems Using ModernProcessor & Storage Architectures (ADMS), pages 1–8, 2010.→pages 17[Com79] Douglas Comer. Ubiquitous b-tree. ACM Comput. Surv.,11(2):121–137, jun 1979. → pages 9[DB10] Atanu Das and Rajib Bag. Wireless sensor network basedmonitoring systems: A review and state-of-the-art appli-cations. INTERNATIONAL JOURNAL OF COMPUTERAPPLICATIONS IN ENGINEERING, TECHNOLOGY ANDSCIENCES (IJ-CA-ETS), 3:142–151, 10 2010. → pages 26[DL14] Graeme Douglas and Ramon Lawrence. Littled: A sql databasefor sensor nodes and embedded applications. In Proceedings ofthe 29th Annual ACM Symposium on Applied Computing, SAC’14, page 827–832, New York, NY, USA, 2014. Association forComputing Machinery. → pages 33, 36[DSl+11] Biplob Debnath, Sudipta Sengupta, Jin li, David Lilja, andDavid Du. Bloomflash: Bloom filter on flash-based storage. In2011 31st International Conference on Distributed ComputingSystems, pages 635–644, 06 2011. → pages 17[EEC+09a] Hazem Elmeleegy, Ahmed K. Elmagarmid, Emmanuel Cecchet,Walid G. Aref, and Willy Zwaenepoel. Online piece-wise linearapproximation of numerical streams with precision guarantees.Proc. VLDB Endow., 2(1):145–156, aug 2009. → pages 43[EEC+09b] Hazem Elmeleegy, Ahmed K. Elmagarmid, Emmanuel Cecchet,Walid G. Aref, and Willy Zwaenepoel. Online piece-wise linearapproximation of numerical streams with precision guarantees.Proc. VLDB Endow., 2(1):145–156, aug 2009. → pages 5276Bibliography[FABM19] Athanasios Fevgas, Leonidas Akritidis, Panayiotis Bozanis, andYannis Manolopoulos. Indexing in flash storage devices: a sur-vey on challenges, current approaches, and future trends. TheVLDB Journal, 29:273–311, 2019. → pages 11[FABM20] Athanasios Fevgas, Leonidas Akritidis, Panayiotis Bozanis, andYannis Manolopoulos. Indexing in flash storage devices: a sur-vey on challenges, current approaches, and future trends. TheVLDB Journal, 29, 01 2020. → pages ix, 19[Fed75] Paul I. Feder. On asymptotic distribution theory in segmentedregression problems– identified case. The Annals of Statistics,3(1):49–83, 1975. → pages 43[FHD+15] Scott Fazackerley, Eric Huang, Graeme Douglas, Raffi Kudlac,and Ramon Lawrence. Key-value store implementations for ar-duino microcontrollers. In 2015 IEEE 28th Canadian Confer-ence on Electrical and Computer Engineering (CCECE), pages158–164, 2015. → pages 34, 60[FOKM+20] Andrew Feltham, Nadir Ould-Khessal, Spencer MacBeth, ScottFazackerley, and Ramon Lawrence. Linear hashing implemen-tations for flash memory. In Joaquim Filipe, Michał Śmi-ałek, Alexander Brodsky, and Slimane Hammoudi, editors,Enterprise Information Systems, pages 386–405, Cham, 2020.Springer International Publishing. → pages 9[FOL21] Scott Fazackerley., Nadir Ould-Khessal., and Ramon Lawrence.Efficient flash indexing for time series data on memory-constrained embedded sensor devices. In Proceedings of the10th International Conference on Sensor Networks - SENSOR-NETS,, pages 92–99. INSTICC, SciTePress, 2021. → pages 35,40, 51, 64, 68[FOM+19] Andrew Feltham, Nadir Ould-Khessal, Spencer MacBeth, ScottFazackerley, and Ramon Lawrence. Linear Hashing Implemen-tations for Flash Memory. In 21st International ConferenceEnterprise Information Systems Selected Papers, volume 378 ofLecture Notes in Business Information Processing, pages 386–405. Springer, 2019. → pages 3677Bibliography[FPL16] Scott Fazackerley, Wade Penson, and Ramon Lawrence. Writeimprovement strategies for serial nor dataflash memory. In 2016IEEE Canadian Conference on Electrical and Computer Engi-neering (CCECE), pages 1–6, 2016. → pages 58[FSHM15] Jordi Fonollosa, Sadique Sheik, Ramón Huerta, and SantiagoMarco. Reservoir computing compensates slow response ofchemosensor arrays exposed to fast varying gas concentrationsin continuous monitoring. Sensors and Actuators B: Chemical,215:618–629, August 2015. → pages 64[FV20] Paolo Ferragina and Giorgio Vinciguerra. The PGM-index: afully-dynamic compressed learned index with provable worst-case bounds. PVLDB, 13(8):1162–1175, 2020. → pages 45,52[Gra93] Goetz Graefe. Query evaluation techniques for large databases.ACM Comput. Surv., 25(2):73–169, Jun 1993. → pages 8[JRvS11] Martin V. Jørgensen, René B. Rasmussen, Simonas Šaltenis,and Carsten Schjønning. Fb-tree: A b+-tree for flash-basedssds. In Proceedings of the 15th Symposium on InternationalDatabase Engineering & Applications, IDEAS ’11, page 34–42,New York, NY, USA, 2011. Association for Computing Ma-chinery. → pages 14[JWZ+15] Zhiwen Jiang, Yongji Wu, Yong Zhang, Chao Li, and ChunxiaoXing. Ab-tree: A write-optimized adaptive index structure onsolid state disk. Proceedings - 11th Web Information Systemand Application Conference, WISA 2014, pages 188–193, 032015. → pages 14[JYW+18] Peiquan Jin, Chengcheng Yang, Xiaoliang Wang, Lihua Yue,and Dezhi Zhang. Sal-hashing: A self-adaptive linear hashingindex for ssds. IEEE Transactions on Knowledge and DataEngineering, PP, 12 2018. → pages 17[KBC+17] Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and NeoklisPolyzotis. The case for learned index structures, 2017. → pages2, 41, 4278Bibliography[KMvR+20] Andreas Kipf, Ryan Marcus, Alexander van Renen, MihailStoian, Alfons Kemper, Tim Kraska, and Thomas Neumann.RadixSpline: a single-pass learned index. In Proceedings of theThird International Workshop on Exploiting Artificial Intelli-gence Techniques for Data Management, pages 1–5, 2020. →pages 46, 52[LDD11] Guanlin Lu, Biplob Debnath, and David Du. A forest-structured bloom filter with flash memory. In 2011 IEEE27th Symposium on Mass Storage Systems and Technologies(MSST), pages 1 – 6, 06 2011. → pages 17[LDM08] X. Li, Z. Da, and X. Meng. A new dynamic hash index for flash-based storage. In Web-Age Information Management, Interna-tional Conference on, pages 93–98, Los Alamitos, CA, USA, jul2008. IEEE Computer Society. → pages 17[LHY+10] Yinan Li, Bingsheng He, Jun Yang, Qiong Luo, and Ke Yi.Tree indexing on solid state drives. Proceedings of the VLDBEndowment, 3:1195 – 1206, 2010. → pages 13[LL10] Hyun-Seob Lee and Dong-Ho Lee. An efficient index buffermanagement scheme for implementing a b-tree on nand flashmemory. Data & Knowledge Engineering, 69:901–916, 09 2010.→ pages 13[MFHH05] Samuel R. Madden, Michael J. Franklin, Joseph M. Heller-stein, and Wei Hong. Tinydb: An acquisitional query process-ing system for sensor networks. ACM Trans. Database Syst.,30(1):122–173, mar 2005. → pages 32[NM08] Thomas Neumann and Sebastian Michel. Smooth interpolat-ing histograms with error guarantees. In Lecture Notes in Com-puter Science, pages 126–138. Springer Berlin Heidelberg, 2008.→ pages 52, 54, 56[OCGO96] Patrick O’Neil, Edward Cheng, Dieter Gawlick, and ElizabethO’Neil. The log-structured merge-tree (lsm-tree). Acta Inf.,33(4):351–385, jun 1996. → pages 13[OFL21] Nadir Ould-Khessal, Scott Fazackerley, and Ramon Lawrence.An efficient b-tree implementation for memory-constrained em-79Bibliographybedded systems. In The 19th Int’l Conf on Embedded Systems,Cyber-physical Systems, and Applications (ESCS’21), 2021. →pages 37, 40[OHLX09] Sai Tung On, Haibo Hu, Yu Li, and Jianliang Xu. Lazy-updateb+-tree for flash devices. In Proceedings - 2009 10th Interna-tional Conference on Mobile Data Management, pages 323–328,October 2009. 2009 10th International Conference on MobileData Management: Systems, Services and Middleware, MDM2009 ; Conference date: 18-05-2009 Through 20-05-2009. →pages 13[OKFL22a] Nadir Ould-Khessal, Scott Fazackerley, and Ramon Lawrence.Performance Evaluation of Embedded Time Series Indexes Us-ing Bitmaps, Partitioning, and Trees. In Invited and revised pa-pers of SENSORNETS 2021, volume 1674 of Sensor Networks,pages 125–151. Springer, 2022. → pages 64, 70, 71[OKFL22b] Nadir Ould-Khessal, Scott Fazackerley, and Ramon Lawrence.Performance evaluation of embedded time series indexes us-ing bitmaps, partitioning, and trees. In Andreas Ahrens, Ran-gaRao Venkatesha Prasad, César Benavente-Peces, and NirwanAnsari, editors, Sensor Networks, pages 125–151, Cham, 2022.Springer International Publishing. → pages 51[O'R81] Joseph O'Rourke. An on-line algorithm for fitting straight linesbetween data ranges. Communications of the ACM, 24(9):574–578, September 1981. → pages 52[RKKP09] Hongchan Roh, Woo-Cheol Kim, Seung-Woo Kim, andSanghyun Park. A b-tree index extension to enhance responsetime and the life cycle of flash memory. Inf. Sci., 179:3136–3161, 08 2009. → pages 13[RO92] Mendel Rosenblum and John K. Ousterhout. The design andimplementation of a log-structured file system. ACM Trans.Comput. Syst., 10(1):26–52, feb 1992. → pages 39[RPSL14] Hongchan Roh, Sanghyun Park, Mincheol Shin, and Sang-WonLee. Mpsearch: Multi-path search for tree-based indexes toexploit internal parallelism of flash ssds. IEEE Data Eng. Bull.,37:3–11, 2014. → pages 1380Bibliography[RWW+17] Sean Rhea, Eric Wang, Edmund Wong, Ethan Atkins, and NatStorer. Littletable: A time-series database and its uses. In Pro-ceedings of the 2017 ACM International Conference on Man-agement of Data, SIGMOD ’17, page 125–138, New York, NY,USA, 2017. Association for Computing Machinery. → pages21, 40[SBB+15] Allan Stisen, Henrik Blunck, Sourav Bhattacharya, Thor SiigerPrentow, Mikkel Baun Kjærgaard, Anind Dey, Tobias Sonne,and Mads Møller Jensen. Smart devices are different: Assessingand mitigating mobile sensing heterogeneities for activity recog-nition. In Proceedings of the 13th ACM Conference on Embed-ded Networked Sensor Systems, SenSys ’15, page 127–140, NewYork, USA, 2015. ACM. → pages 64[TD11] Nicolas Tsiftes and Adam Dunkels. A database in every sen-sor. In Proceedings of the 9th ACM Conference on Embed-ded Networked Sensor Systems, SenSys ’11, page 316–332, NewYork, NY, USA, 2011. Association for Computing Machinery.→ pages 27, 30, 31, 32, 39[Vig12] Stratis D. Viglas. Adapting the b+ -tree for asymmetric i/o.In Tadeusz Morzy, Theo Härder, and Robert Wrembel, editors,Advances in Databases and Information Systems, pages 399–412, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. →pages 13[WF17] Huiying Wang and Jianhua Feng. Flashskiplist: Indexing onflash devices. In Proceedings of the ACM Turing 50th Cele-bration Conference - China, ACM TUR-C ’17, New York, NY,USA, 2017. Association for Computing Machinery. → pages 15[WHQ+20] Chen Wang, Xiangdong Huang, Jialin Qiao, Tian Jiang, LeiRui, Jinrui Zhang, Rong Kang, Julian Feinauer, Kevin Mc-Grail, PengWang, Diaohan Luo, Jun Yuan, JianminWang, andJiaguang Sun. Apache iotdb: time-series database for internetof things. Proceedings of the VLDB Endowment, 13:2901–2904,08 2020. → pages 23[WKC07] Chin-Hsien Wu, Tei-Wei Kuo, and Li Ping Chang. An efficient81Bibliographyb-tree layer implementation for flash-memory storage systems.ACM Trans. Embed. Comput. Syst., 6(3):19–es, jul 2007. →pages 13[Wol02] W. Wolf. What is embedded computing? Computer, 35(1):136–137, 2002. → pages 25[XYLW08] Xiaoyan Xiang, Lihua Yue, Zhanzhan Liu, and Peng Wei. Areliable b-tree implementation over flash memory. In Proceed-ings of the 2008 ACM Symposium on Applied Computing, SAC’08, page 1487–1491, New York, NY, USA, 2008. Associationfor Computing Machinery. → pages 13[ZGD+17] Shuyi Zhang, Bin Guo, Anlan Dong, Jing He, Ziping Xu, andSong Xi Chen. Cautionary tales on air-quality improvementin Beijing. Proceedings of the Royal Society A: Mathemat-ical, Physical and Engineering Sciences, 473(2205):20170457,September 2017. → pages 64[ZYLK+05] Demetrios Zeinalipour-Yazti, Song Lin, Vana Kalogeraki, Dim-itrios Gunopulos, and Walid Najjar. MicroHash: An EfficientIndex Structure for Flash-Based Sensor Devices. In Proceedingsof the FAST ’05 Conference on File and Storage Technologies,pages 31–43. USENIX Association, 2005. → pages 6482
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Lawrence, Ramon
Applying learned indexing on embedded devices for time series data
Text