Mobile and Ubiquitous Systems: Computing, Networking, and Services. 10th International Conference, MOBIQUITOUS 2013, Tokyo, Japan, December 2-4, 2013, Revised Selected Papers

Research Article

Types in Their Prime: Sub-typing of Data in Resource Constrained Environments

Download
377 downloads
  • @INPROCEEDINGS{10.1007/978-3-319-11569-6_20,
        author={Klaas Thoelen and Davy Preuveneers and Sam Michiels and Wouter Joosen and Danny Hughes},
        title={Types in Their Prime: Sub-typing of Data in Resource Constrained Environments},
        proceedings={Mobile and Ubiquitous Systems: Computing, Networking, and Services. 10th International Conference, MOBIQUITOUS 2013, Tokyo, Japan, December 2-4, 2013,  Revised Selected Papers},
        proceedings_a={MOBIQUITOUS},
        year={2014},
        month={12},
        keywords={Sub-typing Constrained environments Prime numbers},
        doi={10.1007/978-3-319-11569-6_20}
    }
    
  • Klaas Thoelen
    Davy Preuveneers
    Sam Michiels
    Wouter Joosen
    Danny Hughes
    Year: 2014
    Types in Their Prime: Sub-typing of Data in Resource Constrained Environments
    MOBIQUITOUS
    Springer
    DOI: 10.1007/978-3-319-11569-6_20
Klaas Thoelen1,*, Davy Preuveneers1, Sam Michiels1, Wouter Joosen1, Danny Hughes1
  • 1: KU Leuven
*Contact email: klaas.thoelen@cs.kuleuven.be

Abstract

Sub-typing of data improves reuse and allows for reasoning at different levels of abstraction; however, it is seldom applied in resource constrained environments. The key reason behind this is the increase in overhead that is caused by including hierarchical information in data types as compared to a flat list. Where hierarchical data typing is used, it is often represented using verbose textual identifiers or numerical encodings that are suboptimal with regards to space. In this paper, we present an encoding function for hierarchically typed information, based on the properties of prime numbers. It provides a compact representation of types, fast subsumption testing even on resource constrained platforms and support for the evolution of the data type hierarchy. We demonstrate the feasibility of our approach on two representative communication models in constrained environments; a publish/subscribe event bus and a RESTful application protocol. We evaluate the performance of our encoding function and show that it has limited overhead compared to a flat list of data types and that this overhead is outweighed by reduced memory and communication overhead once applied.