Literature list from the university bibliography

Results: 144
Created on: Wed, 27 Mar 2024 23:06:06 +0100 in 0.0332 sec


Aumüller, Martin; Dietzfelbinger, Martin; Dietzfelbinger, Martin *1956-*; Wölfel, Philipp;
Explicit and efficient hash families suffice for cuckoo hashing with a stash. - In: Algorithmica, ISSN 1432-0541, Bd. 70 (2014), 3, S. 428-456

It is shown that for cuckoo hashing with a stash as proposed by Kirsch et al. (Proc. 16th European Symposium on Algorithms (ESA), pp. 611-622, Springer, Berlin, 2008) families of very simple hash functions can be used, maintaining the favorable performance guarantees: with constant stash size s the probability of a rehash is O(1/n^(s+1)), the lookup time and the deletion time are O(s) in the worst case, and the amortized expected insertion time is O(s) as well. Instead of the full randomness needed for the analysis of Kirsch et al. and of Kutzelnigg (Discrete Math. Theor. Comput. Sci., 12(3):81-102, 2010) (resp. (log n)-wise independence for standard cuckoo hashing) the new approach even works with 2-wise independent hash families as building blocks. Both construction and analysis build upon the work of Dietzfelbinger and Woelfel (Proc. 35th ACM Symp. on Theory of Computing (STOC), pp. 629-638, 2003). The analysis, which can also be applied to the fully random case, utilizes a graph counting argument and is much simpler than previous proofs. The results can be generalized to situations where the stash size is non-constant.



http://dx.doi.org/10.1007/s00453-013-9840-x
Dietzfelbinger, Martin; Wölfel, Philipp;
Tight lower bounds for greedy routing in higher-dimensional small-world grids. - In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, (2014), S. 816-829

We consider Kleinberg's celebrated small world graph model (Kleinberg, 2000), in which a D-dimensional grid {0,\dots,n-1}^D is augmented with a constant number of additional unidirectional edges leaving each node. These long range edges are determined at random according to a probability distribution (the augmenting distribution), which is the same for each node. Kleinberg suggested using the inverse D-th power distribution, in which node v is the long range contact of node u with a probability proportional to |u-v|^(-D). He showed that such an augmenting distribution allows to route a message efficiently in the resulting random graph: The greedy algorithm, where in each intermediate node the message travels over a link that brings the message closest to the target w.r.t. the Manhattan distance, finds a path of expected length O((log n)^2) between any two nodes. We prove that greedy routing does not perform asymptotically better for any uniform and isotropic augmenting distribution, i.,e., the probability that node u has a particular long range contact v is independent of the labels of u and v and only a function of |u-v|. In particular, we show that for such graphs the expected greedy routing time between two arbitrary nodes s and t is Omega((log|s-t|)^2). This lower bound proves and strengthens a conjecture by Aspnes, Diamadi, and Shah (2000). In order to obtain the result, we introduce a novel proof technique: We define a so-called budget game, in which a token travels over a game board, from one end to the other, while the player manages a "probability budget". In each round, the player "bets" part of her remaining probability budget on step sizes. A step size is chosen at random according to a probability distribution of the player's bet. The token then makes progress as determined by the chosen step size, while some of the player's bet is removed from her probability budget. We prove a tight lower bound for such a budget game, and then obtain a lower bound for greedy routing in the D-dimensional grid by a reduction.



Chemissov, Alexej;
Evaluierung effizienter Hashverfahren mit randomisierten Hashfunktionen. - 47 S. : Ilmenau, Techn. Univ., Bachelor-Arbeit, 2014

In dieser Arbeit werden mehrere Hashverfahren betrachtet und implementiert. Anschließend werden die Verfahren anhand geeigneter Experimente miteinander verglichen. Das Ziel der Arbeit ist, anhand der Experimente eine Aussage bezüglich des praktischen Einsatzes der Verfahren zu treffen. Wir betrachten offenes Hashing mit verketteten Listen und erweitern dieses auf binäre Bäume und AVL-Bäume. Weiterhin untersuchen wir zwei geschlossene Hashverfahren: Robin Hood Hashing und eine Kombination aus d-ärem und geblocktem Cuckoo Hashing. Unterschiedliche Einfügestrategien für das Cuckoo Hashing, wie Random Walk, Local Search von Megha Khosla und Breitensuchenstrategie, werden miteinander verglichen. Wir untersuchen das Verhalten der Verfahren mit und ohne Verdopplungsstrategie und stellen fest, für welche Zwecke jedes der vorgestellten Hashverfahren besser geeignet ist.



Hirte, Steffen;
Load balancing using iterated bisection. - 56 S. Ilmenau : Techn. Univ., Masterarbeit, 2014

Das Problem der Lastbalancierung tritt auf, wenn eine große Berechnungsaufgabe in kleinere Instanzen zerteilt und auf mehreren Prozessoren separat ausgefuhrt werden muss. Aus praktischen Gründen ist es oftmals ungünstig oder zu schwierig, ein Problem direkt in die gewünschte Anzahl an Stücken zu teilen. Deswegen bietet sich die wiederholte Zweiteilung eines Problems an. Dabei wird das HeaviestFirst-Prinzip berücksichtigt, d.h. es wird stets die größte, noch nicht geteilte Instanz als nächstes fragmentiert. Wenn genug Stücke erzeugt wurden, können diese auf die Prozessoren verteilt und ausgeführt werden. Weil das größte erzeugte Stück die Gesamtlaufzeit auf dem parallelen System bestimmt, ist es wünschenswert, dass alle entstehenden Probleme etwa gleich groß sind. Die Problemstellung wurde von Bischof, Ebner und Erlebach (1998) eingeführt. In derselben Arbeit erfolgte für verschiedene Verteilungsklassen eine Worstcase-Analyse. Weiterhin zeigten Bischof, Schickinger und Steger (1999), dass man auch fur pessimistische Verteilungen eine gute erwartete Gesamtlaufzeit vorhersagen kann. Mit Hilfe der Methoden von Dean, Majumdar (2002) und Janson, Neininger (2008) lässt sich das durchschnittliche Gewicht des größten resultierenden Teilproblems fur ein gegebenes Ausgangproblem explizit ermitteln. Dabei muss jedoch die Schnittverteilung für jede auftretende Instanz explizit bekannt und vor allem gleich sein. In dieser Arbeit wird eine Situation betrachtet, in der die Schnittverteilungen aus einer Verteilungsklasse frei gewählt werden können. Es wird gezeigt, dass sich die entstehenden Problemgewichte durchschnittlich nur mit konstantem Faktor vom Optimalwert unterscheiden. Weiterhin wird demonstriert, dass auch die Abweichung vom Erwartungswert klein ist.



Klaue, Pascal;
Optimale Partitionierungsverfahren für Multi-Pivot-Quicksort. - 65 S. : Ilmenau, Techn. Univ., Masterarbeit, 2014

Vor kurzer Zeit wurde eine neue Implementierung von Quicksort als Standard der Java 7 Laufzeitbibliothek gewählt. Überraschenderweise nutzte diese Implementierung zwei Pivotelemente, trotz der Annahme, dass dies zu keiner Verbesserung führen wird. Dadurch wurde neues Interesse in der Nutzbarkeit von Multipivotquicksort geweckt. Deswegen stelle ich in dieser Arbeit eine Methode vor, die es erlaubt eines der einflussreichsten Kostenmaße für das Sortieren, die Anzahl an Vergleichen, zu analysieren. Diese nutze ich um für dieses Kostenmaß optimale Partitionierungsverfahren zu beschreiben. Die Auswirkungen dieser optmalen Partitionierungsverfahren werden, dabei sowohl theoretisch, als auch experiementell untersucht.



Aumüller, Martin; Dietzfelbinger, Martin;
Optimal partitioning for dual pivot quicksort. - In: Automata, Languages, and Programming, (2013), S. 33-44

http://dx.doi.org/10.1007/978-3-642-39206-1_4
Mattern, Christopher;
Linear and geometric mixtures - analysis. - In: Data Compression Conference (DCC), 2013, ISBN 978-0-7695-4965-1, (2013), S. 301-310

http://dx.doi.org/10.1109/DCC.2013.38
Sukiennik, David;
Schnelle Kompression von Sensordaten. - 76 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2013

Das Ziel der Bachelorarbeit "Schnelle Kompression von Sensordaten" war die Entwicklung eines Kompressionsverfahrens für Sensordaten unter den restriktiven Bedingungen eingebetteter Systeme. Beispielsweise im Bereich der Medizin, Hausautomatisierung oder der Umweltüberwachung erfassen eingebettete Systeme Sensordaten, wobei eine Kompression einige Vorteile mit sich bringt. Eingangs werden Grundlagen über Sensordaten, Hard- und Software sowie Kompression geschaffen. Das Konzept prädiktorbasierter Kompression wird eingeführt. Anschließend wird eine Übersicht über geeignete Verfahren aus der Literatur und deren Struktur und Methoden erstellt. Daraufhin wird ein Konzept entworfen, das die vorher ausgearbeiteten Probleme lösen und gleichzeitig Restriktionen beachten soll: Es soll eine Bibliothek für prädiktorbasierte Kompression entstehen, die verschiedene Kombinationenen aus einer Auswahl diverser Prädiktoren und Codierungen ermöglicht. So kann einer Vielzahl der diffusen Beschränkungen Beachtung geschenkt werden. Im darauffolgenden Teil werden die Implementierung und ihre Abweichungen von der mathematischen Beschreibung nachgezeichnet. In der anschließenden Evaluierung und dem Vergleich mit bestehenden Verfahren ließen sich die Ergebnisse der Literatur reproduzieren. Teilweise gab es leichte Abweichungen, oft ließen sich die Verfahren aus der Literatur aber überbieten. Abschließend wird ein Ausblick gegeben mit Verbesserungsmöglichkeiten für die Bibliothek.



Rink, Michael;
Mixed hypergraphs for linear-time construction of denser hashing-based data structures. - In: SOFSEM 2013: Theory and Practice of Computer Science, (2013), S. 356-368

http://dx.doi.org/10.1007/978-3-642-35843-2_31
Jaberi, Raed;
Effiziente Algorithmen für grundlegende Graphprobleme. - 169 S. : Ilmenau, Techn. Univ., Masterarbeit, 2013

Die Berechnung der starken Zusammenhangskomponenten eines gerichteten Graphen ist eine wichtige Anwendung der Tiefensuche. Diese Arbeit beschäftigt sich mit bekannten Algorithmen für dieses Problem, die alle lineare Zeit benötigen: Tarjan-Algorithmus, Kosaraju-Sharir-Algorithmus und Cheriyan-Mehlhorn-Gabow-Algorithmus. Modifizierte Versionen werden in dieser Arbeit beschrieben und untersucht. Diese Varianten machen die Algorithmen schneller oder sparen Speicherplatz. Die Verfahren werden experimentell verglichen. Diese Arbeit befasst sich auch mit grundlegenden Graphproblemen für das Durchsuchen von großen Graphen, die nicht in den Hauptspeicher passen. Schließlich werden effiziente externe Algorithmen auf azyklische gerichtete Graphen, deren topologische Sortierung gegeben ist, beschrieben. Diese Algorithmen benutzen den Technik Time-Forward-Processing.