Structured data model for resource-constrained devices
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Master's thesis
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Authors
Date
2010
Major/Subject
Informaatiotekniikka
Mcode
T-115
Degree programme
Language
en
Pages
xi + 47 s. + liitt.
Series
Abstract
In this thesis I present a design framework for handling structured data efficiently in terms of computational and memory resource use. The design is based on four principles: simplicity, generality, modularity, and efficiency. The presented data model is simple, focusing on relations between the modelled entities instead of data types and formats as is the case with the majority of existing structured models. Modularity of the design is pursued with a clear separation of the parts of the design - modular design allows mixing and matching between different design components to suit the needs of the modelling problem at hand. Most existing structured formats are considered mainly as data exchange formats. Presented data structure is meant to be kept always in the same format, whether the data is stored in a file, transmitted, or processed in the main memory. Thus, special focus is in succinct data structures that minimize data size while maintaining fast access. Essential feature in the model serialization is the separation of the sequencing and encoding phases. Sequencing is the linearization of arbitrarily related model entities and their properties into a sequence of integer symbols and is essential in achieving an efficiently accessible and compressible data structure. The encoding of a symbol sequences belongs to the much researched area of lossless data compression. Finally, programming interfaces for accessing the structured data are presented. Main goal in the interface design has been simplicity and possibility to access compressed data structures efficiently.Esitän diplomityössäni suunnitelmakehyksen tehokkaaseen rakenteisen tiedon käsittelyyn laskennallisten resurssien ja muistinkäytön suhteen. Suunnitelma pohjautuu neljään perusperiaatteeseen: yksinkertaisuuteen, yleistettävyyteen, modulaarisuuteen ja tehokkuuteen. Esitetty tietomalli on yksinkertainen ja keskittyy mallinnettavien entiteettien suhteisiin tietotyyppien ja formaattien sijaan, kuten valtaosassa olemassa olevista rakenteisista malleista. Modulaarisuuteen pyritään selkeällä järjestelmän osien erottelulla - modulaarinen suunnitelma mahdollistaa eri komponenttien yhdistelyn kulloiseenkin käyttötarkoitukseen soveltuvaksi. Valtaosa olemassa olevista rakenteisista formaateista on suunniteltu tiedonvaihtoa varten. Esitetty tietorakenne on tarkoitus pitää samassa muodossa huolimatta siitä, onko se tallennettuna vai käsiteltävänä keskusmuistissa. Tästä johtuen suunnitelmassa keskitytään erityisesti ytimekkäisiin tietorakenteisiin, jotka minimoivat tiedon koon, kuitenkin mahdollistaen tehokkaan tiedonhaun. Oleellinen ominaisuus tietomallin sanallistamisessa on sekvensoinnin ja koodauksen erottaminen omiksi vaiheikseen. Sekvensointi käsittää tietomallin entiteettien, niiden välisten suhteiden ja attribuuttien linearisoinnin jonoksi kokonaislukusymboleja ja on oleellinen osa tehokkaasti haettavan ja pakkautuvan tietorakenteen luomista. Symbolijonon koodaus kuuluu tietotekniikassa paljon tutkittuun häviöttömään tiedonpakkaukseen. Lopuksi esitän ohjelmistorajapinnan rakenteisen tietomallin käsittelyyn. Päämääränä suunnittelussa on ollut yksinkertaisuus ja mahdollisuus tehokkaaseen pakatun tiedon käsittelyyn.Description
Supervisor
Simula, OlliThesis advisor
Rintala, NikoKeywords
structured modeling, rakenteinen mallintaminen, succinct data structures, ytimekkäät tietorakenteet, data serialization, tiedon sarjallistaminen, data compression, tiedonpakkaus