Faster & strong: string dictionary compression using sampling and fast vectorized decompression. - In: The VLDB journal, ISSN 0949-877X, Bd. 29 (2020), 6, S. 1263-1285
String dictionaries constitute a large portion of the memory footprint of database applications. While strong string dictionary compression algorithms exist, these come with impractical access and compression times. Therefore, lightweight algorithms such as front coding (PFC) are favored in practice. This paper endeavors to make strong string dictionary compression practical. We focus on Re-Pair Front Coding (RPFC), a grammar-based compression algorithm, since it consistently offers better compression ratios than other algorithms in the literature. To accelerate compression times, we propose block-based RPFC (BRPFC) which consists in independently compressing small blocks of the dictionary. For further accelerated compression times especially on large string dictionaries, we also propose an alternative version of BRPFC that uses sampling to speed up compression. Moreover, to accelerate access times, we devise a vectorized access method, using Intel® Advanced Vector Extensions 512 (Intel® AVX-512). Our experimental evaluation shows that sampled BRPFC offers compression times up to 190 × faster than RPFC, and random string lookups 2.3 × faster than RPFC on average. These results move our modified RPFC into a practical range for use in database systems because the overhead of Re-Pair-based compression for access times can be reduced by 2 ×.
https://doi.org/10.1007/s00778-020-00620-x
A gray-box modeling methodology for runtime prediction of Apache Spark jobs. - In: Distributed and parallel databases, ISSN 1573-7578, Bd. 38 (2020), 4, S. 819-839
Apache Spark jobs are often characterized by processing huge data sets and, therefore, require runtimes in the range of minutes to hours. Thus, being able to predict the runtime of such jobs would be useful not only to know when the job will finish, but also for scheduling purposes, to estimate monetary costs for cloud deployment, or to determine an appropriate cluster configuration, such as the number of nodes. However, predicting Spark job runtimes is much more challenging than for standard database queries: cluster configuration and parameters have a significant performance impact and jobs usually contain a lot of user-defined code making it difficult to estimate cardinalities and execution costs. In this paper, we present a gray-box modeling methodology for runtime prediction of Apache Spark jobs. Our approach comprises two steps: first, a white-box model for predicting the cardinalities of the input RDDs of each operator is built based on prior knowledge about the behavior and application parameters such as applied filters data, number of iterations, etc. In the second step, a black-box model for each task constructed by monitoring runtime metrics while varying allocated resources and input RDD cardinalities is used. We further show how to use this gray-box approach not only for predicting the runtime of a given job, but also as part of a decision model for reusing intermediate cached results of Spark jobs. Our methodology is validated with experimental evaluation showing a highly accurate prediction of the actual job runtime and a performance improvement if intermediate results can be reused.
https://doi.org/10.1007/s10619-020-07286-y
Data-driven discovery from a data management perspective: challenges, solutions, and applications. - In: Advances in engineering research and application, (2020), S. vii
Parallelization of massive multiway stream joins on manycore CPUs. - In: Euro-Par 2019: parallel processing workshops, (2020), S. 5-16
Doctoral symposium: Pre-processing and data validation in IoT data streams. - In: DEBS 2020, (2020), S. 226-229
https://doi.org/10.1145/3401025.3406443
Efficient processing of large-scale spatio-temporal data. - Ilmenau : Universitätsbibliothek, 2020. - 1 Online-Ressource (148 Seiten)
Technische Universität Ilmenau, Dissertation 2020
Millionen Geräte, wie z.B. Mobiltelefone, Autos und Umweltsensoren senden ihre Positionen zusammen mit einem Zeitstempel und weiteren Nutzdaten an einen Server zu verschiedenen Analysezwecken. Die Positionsinformationen und übertragenen Ereignisinformationen werden als Punkte oder Polygone dargestellt. Eine weitere Art räumlicher Daten sind Rasterdaten, die zum Beispiel von Kameras und Sensoren produziert werden. Diese großen räumlich-zeitlichen Datenmengen können nur auf skalierbaren Plattformen wie Hadoop und Apache Spark verarbeitet werden, die jedoch z.B. die Nachbarschaftsinformation nicht ausnutzen können - was die Ausführung bestimmter Anfragen praktisch unmöglich macht. Die wiederholten Ausführungen der Analyseprogramme während ihrer Entwicklung und durch verschiedene Nutzer resultieren in langen Ausführungszeiten und hohen Kosten für gemietete Ressourcen, die durch die Wiederverwendung von Zwischenergebnissen reduziert werden können. Diese Arbeit beschäftigt sich mit den beiden oben beschriebenen Herausforderungen. Wir präsentieren zunächst das STARK Framework für die Verarbeitung räumlich-zeitlicher Vektor- und Rasterdaten in Apache Spark. Wir identifizieren verschiedene Algorithmen für Operatoren und analysieren, wie diese von den Eigenschaften der zugrundeliegenden Plattform profitieren können. Weiterhin wird untersucht, wie Indexe in der verteilten und parallelen Umgebung realisiert werden können. Außerdem vergleichen wir Partitionierungsmethoden, die unterschiedlich gut mit ungleichmäßiger Datenverteilung und der Größe der Datenmenge umgehen können und präsentieren einen Ansatz um die auf Operatorebene zu verarbeitende Datenmenge frühzeitig zu reduzieren. Um die Ausführungszeit von Programmen zu verkürzen, stellen wir einen Ansatz zur transparenten Materialisierung von Zwischenergebnissen vor. Dieser Ansatz benutzt ein Entscheidungsmodell, welches auf den tatsächlichen Operatorkosten basiert. In der Evaluierung vergleichen wir die verschiedenen Implementierungs- sowie Konfigurationsmöglichkeiten in STARK und identifizieren Szenarien wann Partitionierung und Indexierung eingesetzt werden sollten. Außerdem vergleichen wir STARK mit verwandten Systemen. Im zweiten Teil der Evaluierung zeigen wir, dass die transparente Wiederverwendung der materialisierten Zwischenergebnisse die Ausführungszeit der Programme signifikant verringern kann.
https://nbn-resolving.org/urn:nbn:de:gbv:ilm1-2020000132
Accelerating re-pair compression using FPGAs. - In: DaMoN '20, (2020), insges. 8 S.
Article no. 8
https://doi.org/10.1145/3399666.3399931
Data structure primitives on persistent memory: an evaluation. - In: DaMoN '20, (2020), insges. 3 S.
Article no. 15
https://doi.org/10.1145/3399666.3399900
Elastic scaling in VectorH. - In: Advances in Database Technology - EDBT 2020, (2020), S. 498-509
Industrial paper
http://dx.doi.org/10.5441/002/edbt.2020.61
PatchIndex - exploiting approximate constraints in self-managing databases. - In: 2020 IEEE 36th International Conference on Data Engineering workshops, (2020), S. 139-146
https://doi.org/10.1109/ICDEW49219.2020.00014