Not logged in.

Quick Search - Contribution

Contribution Details

Type Master's Thesis
Scope Discipline-based scholarship
Title Optimization of Lempel-Ziv Entropy Rate Estimator for Numerical Time series
Organization Unit
Authors
  • Lukas Vollenweider
Supervisors
  • Michael Böhlen
  • Jamal Mohammed
Language
  • English
Institution University of Zurich
Faculty Faculty of Business, Economics and Informatics
Date 2022
Abstract Text The entropy rate is an important tool for reasoning about characteristics of a time series, like the complexity, the similarity between time series, or its compressibility. Computing the entropy rate is too complex, which is why approximations are being used. One such approximations is based upon Lempel-Ziv coefficients. Calculating those Lempel-Ziv coefficients is, however, computationally expensive. Therefore, this work evaluates a dictionary-based data structure, used within the Dictionary Compression Score (DCS) method, which was devised to compress time series efficiently. The goal of the evaluation is to find out how the dictionary needs to be adapted to extract Lempel-Ziv coefficients. In a second step, the algorithm is improved to be able to compete against the reference implementation. The evaluation of the proposed algorithms is done by benchmarking their running time as well as their memory usage on real-world temperature data in respect to the reference implementation. We find out that the improvements can beat the reference implementation in terms of running time, while maintaining a similar memory footprint.
Zusammenfassung Die Entropierate ist ein wichtiges Instrument, um die Merkmale einer Zeitreihe, wie die Komplexität, die Ähnlichkeit zwischen Zeitreihen oder die Komprimierbarkeit, analysieren zu können. Die Berechnung der Entropierate ist zu komplex, weshalb Näherungswerte verwendet werden. Eine dieser Annäherungen basiert auf den Lempel-Ziv-Koeffizienten. Die Berechnung dieser Lempel-Ziv-Koeffizienten ist jedoch sehr rechenintensiv. Daher wird in dieser Arbeit eine wörterbuchbasierte Datenstruktur analysiert und evaluiert, die im Rahmen der Dictionary Compression Score (DCS) Methode verwendet wird, die entwickelt wurde, um Zeitreihen effizient zu komprimieren. Ziel der Evaluierung ist es, herauszufinden, wie das Wörterbuch angepasst werden muss, um Lempel-Ziv-Koeffizienten zu extrahieren. In einem zweiten Schritt wird der Algorithmus verbessert, damit er mit der Referenzimplementierung konkurrieren kann. Die Bewertung der vorgeschlagenen Algorithmen erfolgt durch Benchmarking ihrer Laufzeit und ihres Speicherverbrauchs in Bezug auf die Referenzimplementierung anhand von realen Temperaturdaten. Wir finden heraus, dass die Verbesserungen die Referenzimplementierung in Bezug auf die Laufzeit schlagen können, während sie einen ähnlichen Speicherplatzbedarf haben.
PDF File Download
Export BibTeX