Answering (unions of) conjunctive queries using random access and random-order enumeration. - In: ACM transactions on database systems, ISSN 0362-5915, Bd. 47 (2022), 3, S. 9:1-9:49
As data analytics becomes more crucial to digital systems, so grows the importance of characterizing the database queries that admit a more efficient evaluation. We consider the tractability yardstick of answer enumeration with a polylogarithmic delay after a linear-time preprocessing phase. Such an evaluation is obtained by constructing, in the preprocessing phase, a data structure that supports polylogarithmic-delay enumeration. In this article, we seek a structure that supports the more demanding task of a “random permutation”: polylogarithmic-delay enumeration in truly random order. Enumeration of this kind is required if downstream applications assume that the intermediate results are representative of the whole result set in a statistically meaningful manner. An even more demanding task is that of “random access”: polylogarithmic-time retrieval of an answer whose position is given. We establish that the free-connex acyclic CQs are tractable in all three senses: enumeration, random-order enumeration, and random access; and in the absence of self-joins, it follows from past results that every other CQ is intractable by each of the three (under some fine-grained complexity assumptions). However, the three yardsticks are separated in the case of a union of CQs (UCQ): while a union of free-connex acyclic CQs has a tractable enumeration, it may (provably) admit no random access. We identify a fragment of such UCQs where we can guarantee random access with polylogarithmic access time (and linear-time preprocessing) and a more general fragment where we can guarantee tractable random permutation. For general unions of free-connex acyclic CQs, we devise two algorithms with relaxed guarantees: one has logarithmic delay in expectation, and the other provides a permutation that is almost uniformly distributed. Finally, we present an implementation and an empirical study that show a considerable practical superiority of our random-order enumeration approach over state-of-the-art alternatives.
https://doi.org/10.1145/3531055
Über praktisch schnelle Verfahren zur Konstruktion von Suffixarrays. - Ilmenau. - 145 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2022
Suffixarrays sind eine der zentralen Datenstrukturen für String-Algorithmen und finden weitreichende praktische Anwendungen. Die effiziente Konstruktion dieser ist seit der ersten Veröffentlichung in 1990 ein sehr reges Forschungsgebiet geblieben. Im Jahr 2006 wurde der Algorithmus DivSufSort veröffentlicht und obwohl seitdem eine Vielzahl weiterer Suffixarray-Konstruktions-Algorithmen entwickelt wurden, konnte dieser in seiner praktischen Performanz 15 Jahre lang nicht unterboten werden. Doch im Jahr 2021 wurde ein neuer Algorithmus GSACA-DS vorgestellt, welcher unter Verwendung von speziellen Eigenschaften von Lyndon-Wörtern DivSufSort endlich in der Praxis schlagen kann. Obwohl DivSufSort solch hohe praktische Relevanz hat, entzog sich dieser bisher einer rein formellen Darstellung. GSACA-DS besitzt einen formal komplexen Ansatz, weshalb die originale Arbeit keine vollständige Grundlage für dessen Funktionsweise darstellt. Im Rahmen dieser Arbeit sollen diese Lücken in der Literatur gefüllt werden, indem beide Verfahren inklusive ihrer theoretischen Grundlagen vorgestellt, analysiert und zum ersten Mal deren Korrektheit bewiesen werden.
Peeling close to the orientability threshold - spatial coupling in hashing-based data structures. - In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, (2021), S. 2194-2211
https://dl.acm.org/doi/10.5555/3458064.3458195
Fairness in personnel scheduling. - Ilmenau. - 88 Seiten
Technische Universität Ilmenau, Masterarbeit 2021
Die Personaleinsatzplanung ist ein komplexes Optimierungsproblem, bei dem es um die Zuteilung von Mitarbeitern zum Arbeitsplan in einer Vielzahl von Branchen geht. In dieser Arbeit betrachten wir eine spezielle Variante, die "faire" Einsatzpläne erstellen soll. Der Arbeitgeber hat, ähnlich wie bei der traditionellen Personaleinsatzplanung, die Kontrolle über die Zuweisung von Einsatzorten und Arbeitszeiten an die Arbeitnehmer. Andererseits steht es den Arbeitnehmern frei, Präferenzen für die von ihnen gewünschte Arbeit zu äußern. Durch diese Präferenzen werden die Mitarbeiter in das Planungssystem einbezogen, was sich positiv auf die Arbeitsmoral und die Produktivität auswirken soll. Ziel ist es, ein faires Planungssystem zu schaffen, das den Anforderungen des Unternehmens gerecht wird und die Arbeitswünsche der Mitarbeiter berücksichtigt. In dem in dieser Arbeit vorgeschlagenen Modell geben die Unternehmen ihren Bedarf für jeden Tag an, und die Arbeitnehmer geben ihre Präferenzen an. Unser Algorithmus versucht, einen Plan zu erstellen, der sowohl für Arbeitgeber als auch für Arbeitnehmer eine Win-Win-Situation darstellt. Um dies zu erreichen, versuchen wir, einen Zeitplan zu erstellen, der den Anforderungen des Unternehmens und den Präferenzen der Arbeitnehmer so weit wie möglich gerecht wird. Wir haben den Algorithmus mit drei verschiedenen Ansätzen implementiert. Mit allen drei Ansätzen wurden verschiedene Computerexperimente durchgeführt, und ihre Ergebnisse werden diskutiert. Unser Ansatz erstellt erfolgreich einen kurz-, mittel- und langfristigen Zeitplan, der zu einem guten Prozentsatz die Präferenzen der Mitarbeiter erfüllt.
Analyse und experimentelle Evaluation moderner Heap-Strukturen. - Ilmenau. - 98 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2021
Diese Arbeit befasst sich mit einer seit 2015 existierenden Idee für die Implementierung von Prioritätswarteschlangen. Es handelt sich dabei um die von Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan und Uri Zwick vorgeschlagenen "Hollow Heaps". Von den klassischen Fibonacci-Heaps unterscheiden sie sich dadurch, dass sie auf die Cascading-Cut-Prozedur verzichten und stattdessen ein Konzept "leerer Knoten" einführen und teils sogar auf die für Heaps übliche Baumstruktur verzichten. Diese Arbeit stellt Fibonacci-Heaps und Hollow Heaps einheitlich und ausführlich dar und führt experimentelle Vergleiche. In dieser Arbeit wird gezeigt, dass die Wahl zwischen Fibonacci-Heaps und Hollow Heaps bis auf in wenigen Ausnahmen zugunsten der Hollow Heaps ausfallen sollte. Weiterhin sind in unseren Experimenten Binärheaps - als wahrscheinlich grundlegendste Heapstruktur - sogar schneller als ihre Konkurrenten.
Foundations for actively secure card-based cryptography. - In: 10th International Conference on Fun with Algorithms, (2020), S. 17.1-17:23
https://doi.org/10.4230/LIPIcs.FUN.2021.17
Random hypergraphs for hashing-based data structures. - Ilmenau : Universitätsbibliothek, 2020. - 1 Online-Ressource (ix, 165 Seiten)
Technische Universität Ilmenau, Dissertation 2020
Diese Arbeit behandelt Wörterbücher und verwandte Datenstrukturen, die darauf aufbauen, mehrere zufällige Möglichkeiten zur Speicherung jedes Schlüssels vorzusehen. Man stelle sich vor, Information über eine Menge S von m = |S| Schlüsseln soll in n Speicherplätzen abgelegt werden, die durch [n] = {1, ,n} indiziert sind. Jeder Schlüssel x [ELEMENT OF] S bekommt eine kleine Menge e(x) [SUBSET OF OR EQUAL TO] [n] von Speicherplätzen durch eine zufällige Hashfunktion unabhängig von anderen Schlüsseln zugewiesen. Die Information über x darf nun ausschließlich in den Plätzen aus e(x) untergebracht werden. Es kann hierbei passieren, dass zu viele Schlüssel um dieselben Speicherplätze konkurrieren, insbesondere bei hoher Auslastung c = m/n. Eine erfolgreiche Speicherung der Gesamtinformation ist dann eventuell unmöglich. Für die meisten Verteilungen von e(x) lässt sich Erfolg oder Misserfolg allerdings sehr zuverlässig vorhersagen, da für Auslastung c unterhalb eines gewissen Auslastungsschwellwertes c* die Erfolgswahrscheinlichkeit nahezu 1 ist und für c jenseits dieses Auslastungsschwellwertes nahezu 0 ist. Hauptsächlich werden wir zwei Arten von Datenstrukturen betrachten: - Eine Kuckucks-Hashtabelle ist eine Wörterbuchdatenstruktur, bei der jeder Schlüssel x [ELEMENT OF] S zusammen mit einem assoziierten Wert f(x) in einem der Speicherplätze mit Index aus e(x) gespeichert wird. Die Verteilung von e(x) wird hierbei vom Hashing-Schema festgelegt. Wir analysieren drei bekannte Hashing-Schemata und bestimmen erstmals deren exakte Auslastungsschwellwerte im obigen Sinne. Die Schemata sind unausgerichtete Blöcke, Doppel-Hashing sowie ein Schema für dynamisch wachsenden Schlüsselmengen. - Auch eine Retrieval-Datenstruktur speichert einen Wert f(x) für alle x [ELEMENT OF] S. Diesmal sollen die Werte in den Speicherplätzen aus e(x) eine lineare Gleichung erfüllen, die den Wert f(x) charakterisiert. Die entstehende Datenstruktur ist extrem platzsparend, aber ungewöhnlich: Sie ist ungeeignet um Fragen der Form "ist y [ELEMENT OF] S?" zu beantworten. Bei Anfrage eines Schlüssels y wird ein Ergebnis z zurückgegeben. Falls y [ELEMENT OF] S ist, so ist z = f(y) garantiert, andernfalls darf z ein beliebiger Wert sein. - Wir betrachten zwei neue Hashing-Schemata, bei denen die Elemente von e(x) in einem oder in zwei zusammenhängenden Blöcken liegen. So werden gute Zugriffszeiten auf Word-RAMs und eine hohe Cache-Effizienz erzielt. Eine wichtige Frage ist, ob Datenstrukturen obiger Art in Linearzeit konstruiert werden können. Die Erfolgswahrscheinlichkeit eines naheliegenden Greedy-Algorithmus weist abermals ein Schwellwertverhalten in Bezug auf die Auslastung c auf. Wir identifizieren ein Hashing-Schema, das diesbezüglich einen besonders hohen Schwellwert mit sich bringt. In der mathematischen Modellierung werden die Speicherpositionen [n] als Knoten und die Mengen e(x) für x [ELEMENT OF] S als Hyperkanten aufgefasst. Drei Eigenschaften der entstehenden Hypergraphen stellen sich dann als zentral heraus: Schälbarkeit, Lösbarkeit und Orientierbarkeit. Weite Teile dieser Arbeit beschäftigen sich daher mit den Wahrscheinlichkeiten für das Vorliegen dieser Eigenschaften abhängig von Hashing Schema und Auslastung, sowie mit entsprechenden Schwellwerten. Eine Rückübersetzung der Ergebnisse liefert dann Datenstrukturen mit geringen Anfragezeiten, hoher Speichereffizienz und geringen Konstruktionszeiten. Die theoretischen Überlegungen werden dabei durch experimentelle Ergebnisse ergänzt und gestützt.
https://www.db-thueringen.de/receive/dbt_mods_00047127
Obere Schranken für die maximale Kettenlänge bei linearen Hashfunktionen. - Ilmenau. - 56 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2020
In der vorliegenden Arbeit werden obere und untere Schranken für die erwartete maximale Kettenlänge bei linearen Hashfunktionen studiert, wenn Hashing mit verketteten Listen als Kollisionsbehandlung verwendet wird. Es werden Funktionen h, die von einem endlichen Universium U in eine endliche Wertemenge M abbilden, betrachtet. Sei S eine n-elementige Teilmenge von U. Es wird die Wirkung von h auf S studiert. Zunächst wird eine allgemeine obere Schranke für Hashfunktion aus universellen Hashklassen gezeigt. Für solche Funktionen liegt die erwartete maximale Kettenlänge in O(n^(1/2)). Es wird dann eine schärfere obere Schranke für zwei Familien von Hashfunktionen gezeigt, welche aus Mathias Bæk Tejs Knudsen: Linear Hashing Is Awesome. SIAM J. Comput. 48(2): 736-741 (2019) stammt. Für derartige Familien von Hashfunktionen liegt die erwartete maximale Kettenlänge in O(n^(1/3)). Abschließend werden zwei untere Schranken für die erwartete maximale Kettenlänge aus Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos: Linear Hash Functions. J. ACM 46(5): 667-683 (1999) vorgestellt. Diese Ergebnisse werden für eine weitere Familie von Hashfunktionen über endlichen Körper gezeigt.
Engineering von Algorithmen zur Berechnung eines minimalen Schnittes in Graphen. - Ilmenau. - 90 Seiten
Technische Universität Ilmenau, Masterarbeit 2020
In dieser Masterarbeit wird mittels Algorithm Engineering eine möglichst schnelle Implementation des Algorithmus von Nagamochi-Ibaraki für das Open Graph Drawing Framework erarbeitet, die ebenfalls auf großen Graphen schnell ist. Zusätzlich soll die Berechnung einer Maximum Adjacency Ordering ( MAO ) und der Algorithmus von Nagamochi-Ibaraki im praktischen Einsatz beschleunigt werden. Hierbei ist eine MAO eine Totalordnung über die Knotenmenge des Graphen. Zuerst wurden verschiedene Implementationen für die MAO Berechnung erstellt. Ein Ergebnis dieser Implementationen ist die BoundedList, in der maximal B Elemente in einer Liste enthalten sein dürfen, um Lösch- und Einfügeoperationen einzusparen. Bei dem Vergleich der MAO Berechnungen auf verschiedenen Problemfamilien ist ein Ergebnis, dass die BoundedList in der Praxis schneller ist als die Priority-Queue Variante, die von anderen experimentellen Auswertungen verwendet wurde. Daraufhin wurde die BoundedList in Nagamochi-Ibaraki zusammen mit den Padberg-Rinaldi Heuristiken eingearbeitet. Hierbei existieren ebenfalls verschiedene Varianten der Implementation. Eine dieser verwendet eine kompakte Kontraktion um Knoten zu kontrahieren. Dagegen erfolgt die Umsetzung einer anderen Variante mittels Union-Find, um zusammengehörige Knotenmengen zu bilden, die die zu kontrahierenden Knoten repräsentieren. Unter den getesteten Graphen befinden sich ebenfalls Graphen, die realen Netzwerken nachempfunden wurden. Hierbei ist ein Ergebnis, dass das Abbrechen der MAO Berechnung und das Kontrahieren von kontrahierbaren Knotenmengen innerhalb einer Runde von Nagamochi-Ibaraki vorteilhaft bei Graphen mit Clusterkoeffizienten unter 10 Prozent ist. Ansonsten ist die vollständige Berechnung der MAO zu empfehlen. Des weiteren ist während der Masterarbeit aufgefallen, dass die Implementation einer schnellen Kontraktion erheblich ist.
Experimente mit grundlegenden Algorithmen und Datenstrukturen und deren Implementierung. - Ilmenau. - 69 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2019
In der Informatik gibt es diverse Möglichkeiten zur Implementierung von Algorithmen und Datenstrukturen. Diese können sich anschließend bezüglich ihrer Laufzeit oder im Speicherverbrauch unterscheiden. Anhand verschiedener mathematischer Analysen lassen sich Schranken für diese Parameter der Algorithmen und Datenstrukturen berechnen. Durch die modernen Rechnerarchitekturen und deren interne Abläufe können sich diese berechneten Laufzeiten allerdings von den berechneten Schranken unterscheiden. Das Ziel dieser Forschung ist es, zu bestimmen, ob die modernen Rechnerarchitekturen solch großen Einfluss auf die Algorithmen und Datenstrukturen aufweisen, oder ob die bisherigen Annahmen noch zutreffen. Um dieses Problem zu untersuchen, werden ausgewählte Algorithmen und Datenstrukturen implementiert und anschließend Messungen durchgeführt. Dabei fallen die Betrachtungen im Wesentlichen auf grundlegende Algorithmen und Datenstrukturen. Genauer gesagt werden zunächst Stacks und Queues in verschiedenen Implementierungsvarianten untersucht. Anschließend wird offenes und geschlossenes Hashing betrachtet. Dabei werden verschiedene Sondierverfahren miteinander verglichen. Da es verschiedenste Verfahren zum Sortieren von Informationen gibt, werden anschließen fünf Sortieralgorithmen untersucht und dabei ihre Laufzeiten verglichen. Den Abschluss bildet die eigene Implementierung der Addition und Multiplikation zum Rechnen mit großen Ganzzahlen. Und letztendlich ein Vergleich zwischen Quickselect und Mergesort zum Finden des kleinsten Elements in einem Array. Die Betrachtung der Messergebnisse zeigt, dass die mathematischen Annahmen und Schranken für die gewählten Algorithmen und Datenstrukturen immer noch zutreffen und somit keine einzelnen Algorithmen durch die Computerarchitektur entgegen dieser Analysen optimiert werden. Auf dieser Grundlage können also die getroffenen Annahmen weiter verfolgt werden.