Abstract

In the field of algorithms and data structures analysis and design, most of the researchers focus only on the space/time trade-off, and little attention has been paid to energy consumption. More specifically, energy consumption may be of special interest when designing compact data structures. These emerged in the last decades as the perfect solution to provide not only memory-efficient data representations, but allowing fast accesses and queries over the data in compact space. They use compression strategies to reduce the size of the stored data, but with the key property that data can be directly managed and queried in compressed form, without requiring a previous decompression.

Compact data structures perfectly fit within those domains requiring battery- and memory-limited devices, such as smart cities or industry 4.0. Given the relevance that these devices have acquired in almost every aspect of our daily lives, it is crucial to minimize their energy consumption in processing, storage and data transmission. Thus, we must consider energy consumption as a first-class constraint when designing new compact data structures. For this, we need to be able to create new models to analyze energy complexity of data structures and algorithms, and thus introduce a new energy-aware paradigm for designing compact data structures.