Datum: Fr, 19 Feb 2010, 14:00

Ort: SR 301

Vortragende(r): Christian Staudt, Studienarbeiter

Inhalt: Graph clustering is concerned with identifying the group structure of networks. Existing static methods, however, are not the best choice for evolving networks with evolving group structures. We discuss dynamic versions of existing clustering algorithms which maintain and modify a clustering over time rather than recompute it from scratch. We developed an extensible software framework for the evaluation of these algorithms, and present experimental results on real-world and synthetic graph instances. Our focus on clustering quality, clustering smooth- ness, and runtime. We conclude that dynamically maintaining a clustering on an evolving graph is superior in terms of all criteria. We demonstrate that dynamic algorithms are able to react quickly and appropriately to changes in the cluster structure. Our results allow us to give sound recommendations for the choice of an algorithm.

Datum: Di, 16 Feb 2010, 14:00

Ort: SR 301

Vortragende(r): Hanno Kersting, Diplomarbeiter

Datum: Fr, 29 Jan 2010, 14:00

Ort: SR 301

Vortragende(r): Romuald Brillout, Studienarbeiter

Inhalt: Das Problem MinBisection besteht darin einen gegebenen Graphen in zwei gleichgroße Teile zu zerlegen, sodass möglichst wenige Kanten zwischen den beiden Teilen verlaufen. Diese Arbeit stellt ein Framework für MinBisection mittels der Multi-Level-Technik vor. Die Idee hinter der Multi-Level-Technik ist den Graphen zu verkleinern, indem Knoten verschmolzen werden, um den Suchraum zu verkleinern, sodass möglichst nur gute Lösungen übrig bleiben. Mithilfe das Frameworks wurden neue Verfahren für die Multi-Level-Technik entwickelt. Diese werden in diese Arbeit vorgestellt und evaluiert.

Datum: Di, 26 Jan 2010, 14:00

Ort: SR 301

Vortragende(r): Tobias Columbus, Studienarbeiter

Datum: Fr, 8 Jan 2010, 14:00

Ort: SR 301

Vortragende(r): Moritz Kobitzsch, Diplomarbeiter

Inhalt: We present the first fast route planning algorithm that answers shortest paths queries for a customizable linear combination of two different metrics, e.g. travel time and energy cost, on large scale road networks. The precomputation receives as input a directed graph, two edge weight functions t(e) and c(e), and a discrete interval [L,U]. The resulting flexible query algorithm finds for a parameter p an exact shortest path for the edge weight t(e) + p*c(e). This allows for different tradeoffs between the two edge weight functions at query time. We apply precomputation based on node contraction, which adds all necessary shortcuts for any parameter choice efficiently. To improve the node ordering, we developed the new concept of gradual parameter interval splitting. Additionally, we improve performance by combining node contraction and a goal-directed technique in our flexible scenario.

Datum: Fr, 18 Dez 2009, 14:00

Ort: SR 301

Vortragende(r): Andreas Gemsa, Diplomarbeiter

Inhalt: Fortschritte im Bereich der Routenplanung ermöglichen es uns kürzeste Wege Anfragen innerhalb weniger Millisekunden für europaweite Routen zu ermitteln. Zur Visualisierung werden in der Regel Kartenausschnitte verwendet bei denen die Route farblich hervorgehoben ist. Dabei wird über die gesamte Karte hinweg der gleiche Maßstab verwendet und es werden Informationen dargestellt, die für den Betrachter völlig irrelevant sind. Unser Ansatz versucht die Probleme mit der herkömmlichen Darstellung zu vermeiden. Dazu wird ein Verfahren präsentiert, dass die gesamte Route schematisiert. Dabei werden Länge und Ausrichtung einzelner Kantensegmente verändert, unter der Berücksichtigung, dass gewisse strukturelle Informationen der Route erhalten bleiben.

Datum: Mi, 18 Nov 2009, 14:00

Ort: SR 236

Vortragende(r): Valentin Polishchuk, Helsinki Institute for Information Technology

Inhalt: We have designed efficient algorithms for geometric motion planning by developing continuous analogues of classical graph-theoretic concepts. I will describe some of these developments, from the continuous Dijkstra paradigm to continuous versions of the MaxFlow-MinCut, Flow Decomposition, and Menger's theorems. Our research is motivated by air traffic management; we present some applications of our algorithmic and combinatorial results to real data. This is joint work with Estie Arkin, Joondong Kim, Jimmy Krozel, Joseph Mitchell, Anne Paakko, Joseph Prete, and Arto Vihavainen.

Datum: Fr, 30 Okt 2009, 14:00

Ort: SR 301

Vortragende(r): Edith Brunel, Studienarbeiterin

Inhalt: Bei der Routenplanung auf Transportnetzen werden sogenannte Beschleunigungstechniken für Dijkstra's Algorithmus eingesetzt, die in einer Vorberechnungsphase zusätzliche Informationen berechnen, die später Dijkstra's Algorithmus mit dem Ziel unterstützen, die Anfragezeiten drastisch zu reduzieren. Die Technik SHARC-Routing basiert dabei auf zwei Bestandteilen: Shortcuts und Arc-Flags. In dieser Arbeit wurden Strategien untersucht, um in einem zusätzlichen Vorberechnungsschritt für SHARC-Routing Shortcuts wieder zu entfernen. Insbesondere wurden verschiedene Ordnungsfunktionen, die die Wichtigkeit von Shortcuts bewerten, aufgestellt und bezüglich ihrer Auswirkung auf die Anfragezeiten evaluiert.

Datum: Fr, 9 Okt 2009, 14:00

Ort: SR 301

Vortragende(r): Manuel Krings, Diplomarbeiter

Inhalt: Es wird das Problem untersucht, minimale zeitstabile Schnitte in dynamischen Graphen zu berechnen. Zwei Problemvarianten werden definiert und Algorithmen vorgestellt, die diese Probleme exakt oder heuristisch lösen. Für die dazu verwendete Kaktus-Repräsentation wurden Operationen eingeführt, mit denen der Kaktus nach dem Einfügen- oder Entfernen einer Kante aktualisert werden kann. Als Anwendungsbeispiel wird ein Clusterungsverfahren für Graphfamilien vorgestellt.

Datum: Mi, 16 Sep 2009, 14:00

Ort: SR 301

Vortragende(r): Andrea Schumm, Diplomarbeiterin

Datum: Di, 18 Aug 2009, 14:00

Ort: SR 301

Vortragende(r): Robert Franke, Studienarbeiter

Inhalt: Es werden Algorithmen vorgestellt, die große Matchings in planaren Graphen mit festem Minimalgrad berechnen. Die Algorithmen arbeiten in Linearzeit und garantieren eine Mindestgröße der gefundenen Matchings. Für Minimalgrad 3 wird die Schranke (n+2)/3 erreicht, die für diese Klasse von Graphen die beste garantierbare Mindestgröße eines maximalen Matchings darstellt.

Datum: Mo, 10 Aug 2009, 14:00

Ort: SR 301

Vortragende(r): Christian Vetter, Studienarbeiter ITI Sanders

Inhalt: Time-Dependent Contraction Hierarchies is a routing technique that solves the shortest path problem in graphs with time-dependent edge weights, that have to satisfy the FIFO property. Although it shows great speedups over Dijkstra's Algorithm the preprocessing is slow. We present a parallelized version of the preprocessing taking advantage of the multiple cores present in todays CPUs. Nodes independent of one another are found and processed in parallel. We give experimental results for the German road network. With 4 and 8 cores a speedup of up to 3.4 and 5.3 is achieved respectively.

Datum: Di, 28 Jul 2009, 14:45

Ort: SR 301

Vortragende(r): Ingmar Wirths, Studienarbeiter ITI Sanders

Inhalt: Für ein all-to-all Kommunikationsschema in einem Cluster-Computer wird ein Scheduling-Verfahren vorgestellt. Dieses wurde mit MPI implementiert und auf der XC1 evaluiert.

Datum: Di, 28 Jul 2009, 14:00

Ort: SR 301

Vortragende(r): Manuel Holtgrewe, Diplomarbeiter ITI Sanders

Inhalt: Graph Partitioning is an important load balancing problem in parallel processing. The simplest case of graph partitioning is as follows: Given a graph G = (V, E) and an integer k, the vertex set is to be partitioned such that each partition block has the same size and minimize the edges adjacent to vertices in different blocks.
Beginning, from the mid-90s, the most successful practicable codes use a multi-level approach. We present a scalable coarsening phase for a distributed memory, parallel multi-level partitioner and an experimental evaluation thereof. The main contribution is using high-quality matching algorithm with target functions different from the edge weight. Also, the algorithm for finding matchings of vertices that are not local to one process is more advanced than other codes we are aware of.

Datum: Mi, 15 Jul 2009, 14:00

Ort: SR 236

Vortragende(r): Thomas Pajor, Diplomarbeiter

Inhalt: Route Planning in transportation networks has become an integral part of today's life. Let it be navigation systems for cars or timetable information systems for railway and flight companies. However, all these systems have one common limitation: They only allow route planning within their respective domain.
In this talk we introduce multi-modal route planning, where we combine different transportation networks and ask for routes involving roads, railways, and flights simultaneously. To control the number of different means of transportation along the route (e.g., you would not want to use a car in the middle of your journey), we augment the shortest path problem by constraining valid paths with regular languages. The problem can be solved by a generalization of Dijkstra's algorithm.
In the second part of this talk we study speed-up techniques for the label constrained variant of Dijkstra's algorithm. After adapting the basic ingredients of today's speed-up techniques on road networks (bidirectional search, goal-directed search and contraction), we derive a new multi-modal speed-up technique called Access-Node Routing which uses ideas from Transit-Node Routing yielding speed-ups of four orders of magnitude on large-scale multi-modal transportation networks.

Datum: Fr, 3 Jul 2009, 14:30

Ort: SR 301

Vortragende(r): Selma Mukhtar, Diplomarbeiterin

Inhalt: In the last decade large interbranch loyalty programs became a major trend among German companies and their customers. Being the biggest German loyalty program, PAYBACK started out in 2000 and by 2008 about 60% of all German private households owned a PAYBACK-card. Now receipts can be assigned to single customers and their buying behaviors can be tracked, which opens up new possibilities for highly effective and selective marketing concepts and for very close customer relationships. The more information a company can gain about its customers and their purchasing behaviors the better it can respond to their needs and the closer to the market it actually is. The content of this work is a case study. We want to ?nd out if graph clustering as a data mining technique is suitable to extract meaningful customer pro?les in PAYBACK-card data provided by the German chemist chain dm. In our approach, we model the data as a network of customers and apply graph clustering methods to find groups of customers with similar buying behaviors.

Datum: Fr, 26 Jun 2009, 14:30

Ort: SR 301

Vortragende(r): Dominik Itte, Studienarbeiter ITI Sanders

Inhalt: Aufgrund ihrer Eigenschaft eines universalen Approximators stellen Gaußmischdichten, d.h. die gewichtete Summe von Gaußdichten, ein weit verbreitetes Funktionensystem dar, um beliebige Wahrscheinlichkeitsdichtefunktionen zu repräsentieren. Durch die rekursive Verarbeitung von Gaußmischdichten, etwa bei der nichtlinearen Zustandsschätzung, steigt die Anzahl der Gaußkomponenten mit der Zeit exponentiell an. Um den Rechen- und Speicheraufwand begrenzt zu halten, ist es daher unvermeidlich dem exponentiellen Wachstum entgegen zu wirken. In dieser Arbeit wurde ein mehrstufiges Verfahren zur Gaußmischdichtenreduktion entwickelt, welches auf Vorarbeiten der Lehrstühle von Prof. Hanebeck und Prof. Sanders beruht. Ausgangspunkt der Reduktion und somit erste Stufe des Verfahrens ist die Bestimmung von Clusterzentren. Die iterative Zuordnung der Komponenten der Gaußdichte erfolgt in der zweiten Stufe des Verfahrens. Hierbei wird eine probeweise Zuordnung jeder Komponente zu jedem Cluster vorgenommen. Die resultierende Abweichung zur wahren Gaußmischdichte wird evaluiert und die Zuordnung mit der geringsten Abweichung letztendlich durchgeführt. Dies wird solange wiederholt, bis sich die Abweichung zur wahren Dichte nur noch unwesentlich verändert. In der letzten Stufe des Verfahrens werden die Parameter der reduzierten Gaußmischdichte mittels eines Optimierers adaptiert, um die Formabweichung zur wahren Dichte zu minimieren.

Datum: Fr, 19 Jun 2009, 14:00

Ort: SR 301

Vortragende(r): Jung Long, Diplomarbeiter ITI Sanders

Datum: Do, 28 Mai 2009, 11:30

Ort: SR 301

Vortragende(r): D. T. Lee, Institute of Information Science & Research Center for IT Innovation, Academia Sinica, Taiwan

Inhalt: In this talk we present algorithms for solving problems related to sequence manipulation, including searching subsequences of maximum density and selecting subsequences of a certain density, of a given rank, with or without length restrictions. Problem transformation and utilization of efficient data structures or problem-solving methods will be presented. The problem-solving methods are fundamental to computational problems, which arise, for example, in bioinformatics. (Joint work with Dr. Tien-Ching Lin, Institute of Information Science, Academia Sinica, Taiwan.)

Datum: Fr, 15 Mai 2009, 14:00

Ort: SR 301

Vortragende(r): Julian Dibbelt, Diplomarbeiter

Datum: Mi, 6 Mai 2009, 14:00

Ort: SR 236

Vortragende(r): Jonathan Dees, Studienarbeiter

Inhalt: In verschiedenen Szenarien spielen sich über die Zeit ändernde Graphen eine wichtige Rolle, beispielsweise in Rechnernetzen oder sozialen Netzwerken. Hier betrachten wir das klassische Matching Problem in dynamischen Graphen: Wir suchen kardinalitätsmaximale Matchings in sich änderden Graphen, so dass die Matchings in zwei aufeinanderfolgenden Graphen möglichst ähnlich sind (offline). Wohingegen das gewöhnliche Matchingproblem in P liegt, zeigen wir, dass das hier betrachtete dynamische Matching Problem NP-schwer ist. Desweiteren präsentieren wir verschiedene Lösungsansätze wie eine Heuristik und eine ILP-Formulierung, die auch experimentell evaluiert werden.

Datum: Mi, 6 Mai 2009, 13:30

Ort: SR 236

Vortragende(r): Thomas Gramer, Studienarbeiter

Inhalt: Diese Arbeit beschäftigt sich mit der Ermittlung von Druckzonen in bestehenden Wasserverteilungssystemen. Es werden verschiedene Arten der Modellierung mittels Linearer Programmierung für die grundlegensten Anforderungen der Ermittlung von Druckzonen vorgestellt. Als Resultat stehen dabei verschiedene Formulierungen zur Auswahl die entweder sehr schnell eine bereits akzeptable Lösung auch für große Netze finden oder mit etwas mehr Aufwand qualitativ bessere Lösungen ausfindig machen.

Datum: Mi, 18 Mär 2009, 14:00

Ort: SR 236

Vortragende(r): Johannes Fischer, Uni Tübingen

Inhalt: Suffix trees are one of the most important data structures in stringology, with myriads of applications in fluorishing areas like bioinformatics. As their main problem is space usage, recent efforts have focused on compressed suffix tree representations, which obtain large space reductions in exchange for moderate slowdowns. Such a smaller suffix tree could fit in a faster memory, outweighting by far the theoretical slowdown. We present a novel compressed suffix tree. Compared to the current compressed suffix trees, it is the first achieving at the same time sublogarithmic complexity for the operations, and space usage which goes to zero as the entropy of the text does. Our development contains several novel ideas, such as compressing the longest common prefix information, and totally getting rid of the suffix tree topology, expressing all the suffix tree operations using range minimum queries and a new primitive called next/previous smaller value in a sequence.
Joint work with V. Mäkinen (Univ. Helsinki) und G. Navarro (Univ. Chile)

Datum: Di, 10 Mär 2009, 14:00

Ort: SR 301

Vortragende(r): Marius Elvert, Studienarbeiter ITI Sanders

Datum: Fr, 20 Feb 2009, 14:00

Ort: SR 301

Vortragende(r): Sabine Neubauer, Studienarbeiterin ITI Sanders

Datum: Fr, 6 Feb 2009, 16:00

Ort: SR 301

Vortragende(r): Marcel Birn, Studienarbeiter ITI Sanders

Inhalt: Das Suchen des nächsten Nachbarn eines Anfragepunkts in einer gegebenen Punktmenge ist ein klassisches Problem der algorithmischen Geometrie. Wir präsentieren ein neues Verfahren, das durch Ergebnisse aus der Routenplanung (insbesondere Contraction Hierarchies) inspiriert ist. In eine Delaunay-Triangulierung der Punktmenge werden zusätzliche Kanten eingefügt, die als Abkürzung auf der Suche nach dem nächsten Nachbarn genutzt werden können. Unsere experimentellen Ergebnisse zeigen, dass unser einfaches Verfahren dank kompakter Datenstruktur etablierte Verfahren in den meisten Fällen schlägt.

Datum: Di, 3 Feb 2009, 14:00

Ort: SR 301

Vortragende(r): Johannes Wirges, Diplomarbeiter

Datum: Fr, 16 Jan 2009, 14:00

Ort: SR 301

Vortragende(r): Andreas Gemsa, Studienarbeiter

Datum: Di, 13 Jan 2009, 14:00

Ort: SR 301

Vortragende(r): Daniel Karch, Studienarbeiter

Datum: Fr, 19 Dez 2008, 14:00

Ort: SR 301

Vortragende(r): Stefanie Nagel, Diplomarbeiterin

Datum: Di, 16 Dez 2008, 14:00

Ort: SR 301

Vortragende(r): Martin Wolff

Inhalt: A fast method for computing highway node hierarchies is developed. The result is very fast preprocessing at the cost of somewhat larger query times.

Datum: Di, 16 Dez 2008, 10:30

Ort: SR -109

Vortragende(r): Tanja Hartmann, Diplomarbeiterin

Datum: Fr, 12 Dez 2008, 14:00

Ort: SR 301

Vortragende(r): Fabian König, Diplomarbeiter

Datum: Di, 9 Dez 2008, 14:00

Ort: SR 301

Vortragende(r): Michael Ziller, Studienarbeiter

Datum: Di, 11 Nov 2008, 14:00

Ort: SR 301

Vortragende(r): Markus Völker, Diplomarbeiter

Datum: Mi, 29 Okt 2008, 13:00

Ort: SR 301

Vortragende(r): Frederik Transier, ITI Sanders

Inhalt: Phrase searches are an important operation on text search engines. This talk shows how inverted index based text search engines can be improved to achieve reduced reponse times for phrase queries.

Datum: Di, 14 Okt 2008, 14:00

Ort: SR -102

Vortragende(r): Myriam Freidinger, Diplomarbeiterin

Inhalt: Die betrachteten Stabilisatorgruppen sind Untergruppen von Aut(Fz) von endlichem Index, zu denen bisher nur sehr wenig bekannt ist. Sie können beispielsweise verwendet werden, um die Veechgruppe einer Überlagerung einer primitiven Translationsfläche zu bestimmen. Ziel des Vortrags ist die Vorstellung eines effizienten Algorithmus zur Berechnung des Stabilisators einer Untergruppe der freien Gruppe, sowie die Betrachtung heuristischer Maßnahmen zur Laufzeitverbesserung.

Datum: Fr, 8 Aug 2008, 14:00

Ort: SR 301

Vortragende(r): Christian Schulz, Studienarbeiter

Datum: Fr, 18 Jul 2008, 14:00

Ort: 231, Kollegiengebäude am Ehrenhof

Vortragende(r): Mike Fellows, University of Newcastle, Australien

Datum: Fr, 11 Jul 2008, 14:00

Ort: SR 301

Vortragende(r): Jakob Blomer, Diplomarbeiter ITI Sanders

Datum: Fr, 13 Jun 2008, 15:00

Ort: PTV, Stumpfstraße 1

Vortragende(r): Johannes Spallek, Diplomarbeiter ITI Sanders/PTV

Datum: Fr, 13 Jun 2008, 14:00

Ort: SR 301

Vortragende(r): Bastian Katz

Datum: Di, 27 Mai 2008, 15:00

Ort: SR 131

Vortragende(r): Dominik Schultes, ITI Sanders

Inhalt: Rainbow Sort is an unconventional method for sorting, which is based on the physical concepts of refraction and dispersion. It is inspired by the observation that light that traverses a prism is sorted by wavelength. At first sight this "rainbow effect" that appears in nature has nothing to do with a computation in the classical sense, still it can be used to design a sorting method that has the potential of running in O(n) with a space complexity of O(n), where n denotes the number of elements that are sorted.

Datum: Mo, 26 Mai 2008, 14:00

Ort: SR 236

Vortragende(r): Markus Maier, MPI für biologische Kybernetik

Datum: Mo, 26 Mai 2008, 11:30

Ort: SR 131

Vortragende(r): Renato Werneck, Microsoft Research, USA

Inhalt: This talk will describe fast algorithms for computing exact point-to-point shortest paths (driving directions) on road networks. Our approach is a combination of two techniques: reach-based pruning eliminates local intersections, while landmark-based A* search directs the search towards the goal. On the road networks of the USA and Western Europe, an average query visits no more than a thousand road intersections (out of roughly 20 million), which is four orders of magnitude better than Dijkstra's algorithm. Besides presenting an overview of the basic techniques, the talk will discuss a few recent developments, such as an improved algorithm for computing landmarks. Joint work with Andrew Goldberg and Haim Kaplan.

Datum: Fr, 16 Mai 2008, 14:00

Ort: SR 301

Vortragende(r): Paul Dütting, Diplomarbeiter

Inhalt: Large-scale web search engines typically split the overall index into hundreds of subindices. Thus, not only different queries can be run in parallel on different servers but also the work required to answer a single query can be split across multiple servers. For high resource utilization and throughput the overall workload has to be balanced over the available servers. Experiments with query logs from AltaVista and AllTheWeb and 20M web pages from Stanford's WebBase suggest that (a) the overall load is roughly balanced over the subindices and that (b) the load generated by individual queries is rather tiny. Based on these insights we present a refined theoretical framework and devise several highly competitive loadbalancing strategies.

Datum: Di, 15 Apr 2008, 15:45

Ort: SR 301

Vortragende(r): Robert Geisberger, Diplomarbeiter, ITI Sanders

Inhalt: We present a route planning technique solely based on the concept of node contraction. The nodes are first ordered by 'importance'. A hierarchy is then generated by iteratively contracting the least important node. Contracting a node v means replacing shortest paths going through v by shortcuts. We obtain a hierarchical query algorithm using bidirectional shortest-path search. The forward search uses only edges leading to more important nodes and the backward search uses only edges coming from more important nodes. For fastest routes in road networks, the graph remains very sparse throughout the contraction process using rather simple heuristics for ordering the nodes. We have five times lower query times than the best previous hierarchical Dijkstra-based speedup techniques and a negative space overhead, i.e., the data structure for distance computation needs less space than the input graph. CHs can be combined with many other route planning techniques, leading to improved performance for many-to-many routing, transit-node routing, goal-directed routing or mobile and dynamic scenarios.