Engineering Data Generators for Robust Experimental Evaluations [Elektronische Ressource] : Planar Graphs, Artificial Road Networks, and Traffic Information / Sascha Meinert. Betreuer: D. Wagner

Sascha Meinert

Sujets

• Informatik

Informations

• Publié par: karlsruher_institut_fur_technologie
• Publié le: 01 janvier 2012
• Nombre de lectures: 55
• Langue: English
• Poids de l'ouvrage: 13 Mo

Extrait

Engineering Data Generators for Robust
Experimental Evaluations
{ Planar Graphs, Arti cial Road Networks, and Tra c Information {
zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften
von der Fakultat fur Informatik
des Karlsruher Instituts fur Technologie (KIT)
genehmigte
Dissertation
von
Sascha Meinert
aus Neunkirchen-Seelscheid
Tag der mundlic hen Prufung: 21. Dezember 2011
Erster Gutachter: Frau Prof. Dr. Dorothea Wagner
Zweiter Gutachter: Herr Prof. Dr. Michael KaufmanniiAcknowledgments
First of all, I thank my advisor Dorothea Wagner for the opportunity to work in her great
research group with its friendly atmosphere, her constant encouragement and support, as
well as the freedom to choose and trust in the projects I invested time into. I also want
to thank Michael Kaufmann for giving me the opportunity to start my PhD studies in his
research group and for reviewing this thesis.
I thank my o ce mates Frank Schulz, Daniel Delling and Ignaz Rutter (in chronological
order) for the enjoyable time and great atmosphere we had. In particular, I thank Frank
for the warm welcomes when I sporadically visited Karlsruhe in the beginning. Thank you
Daniel for the funny and ‘sporty’ time we had. I deeply thank Ignaz, who showed me how
to step back and consider details in the context of the bigger picture. I also thank you for
putting the right pressure on me in the right moments even though I moaned from time
to time. It was always a great pleasure to work with you | keep going!
Many thanks to all my colleagues for the enjoyable and ‘sporty’ time I had in the re-
search group. My favor for delicious dishes is well known and hence I thank the ‘Freunde
des guten Geschmacks’ of our research group with whom I shared this passion; unfortu-
nately, their number decreased over time, which made me visit the canteen more often
than I wanted to. I want to thank all those who contributed to my work. Especially, I
thank Marcus Krug for our discussions on planar graphs and Reinhard Bauer for sharing
his knowledge on route-planning techniques with me. I thank Robert G orke for proofread-
ing every single piece of work of mine and improving my spelling style. Besides going Leif,
Bastian Katz and Isabelle Jellen found the time to read this thesis and to give important
feedback even on short notice. Thank you so much! The most constant contributor has
not been mentioned yet | it made this thesis nally possible: A special thank for its ne
and everlasting support goes to our co ee machine.
Throughout my years at the university I organized a lot of events and was involved in
several projects that would have been much more challenging without the help of Lilian
Beckert, Anja Blancani and Elke Sauer. They made each problem at least an order of
magnitude smaller than it was before asking them for help. Thank you for backing me up.
I also enjoyed the trust set in me when it came to questions about up-to-date information
technology. I thank Bernd Giesinger for our discussions about possible improvements to
our technical infrastructure and the associated possibility to spend hundreds and thou-
sands of euros. Also, I thank the numerous student workers who helped me deal with
the realization of the GD’06, the nal colloquium of SPP’1126 or the ALGO’08 and to
perform projects like the GraphDB or the RoutePlanning@KIT.
I thank my parents Gritta and Gun ter Meinert for supporting me all the time in nu-
merous ways. Finally, I want to thank Nina H ammerle, who believed in me and encouraged
me to nish this thesis: Thank you Nina for your love and patience.ivDeutsche Zusammenfassung (German Summary)
Das Algorithm Engineering beschreibt ein modernes Verfahren des Algorithmenentwurfs.
Dabei ist das erklarte Ziel, nicht ausschlie lich theoretische Aspekte, sondern insbesondere
auch die praktische Anwendung entwickelter Methoden zu betrachten. Diesem Verfahren
liegt ein Kreislauf aus vier Phasen zugrunde. Ausgehend vom Entwurf folgt die theoretische
Analyse. Die darauf folgende Implementierung wird dann im Experiment ausgewertet.
Die experimentelle Auswertung erlaubt dann wieder Ruc kschlusse auf den Entwurf; der
Kreislauf ist geschlossen.
Elementare Voraussetzung fur eine aussagekraftige Bewertung der Praxistauglichkeit
in diesem Kreislauf ist das Experiment an Echtweltinstanzen. Allerdings sind solche In-
stanzen oft nicht oder nur begrenzt verfugbar. Die Grunde hierfur sind vielfaltig. So sind
Firmen oft nicht bereit, ihre Daten zur Verfugung zu stellen, da Konkurrenten Einblicke
und somit Wettbewerbsvorteile gewinnen konn ten. Manchmal ist aber auch die Anzahl an
Instanzen begrenzt, wie zum Beispiel die Stra ennetze kontinentaler Gr o e. Um dennoch
die E zienz und Robustheit von Algorithmen experimentell zu evaluieren, werden typi-
scherweise kunstlic he Daten erzeugt. Diese sollten ausgewahlte strukturelle Eigenschaften
besitzen, die die Algorithmen entsprechend fordern, um signi kante R uckschlusse auf deren
Verhalten im Anwendungsfall zu ermoglichen.
An diesem Punkt setzt diese Arbeit an und leistet Beitrage zur geeigneten Generie-
rung kunstlic her Daten, die die Aussagekraft kunftiger experimenteller Studien in zwei
wichtigen Forschungsgebieten starken. Dies sind zum einen Algorithmen fur planare Gra-
phen, insbesondere im Hinblick auf die sogenannte Festparameter-Algorithmik, und zum
anderen Algorithmen zur Routenplanung in Stra ennetzen. Zur Generierung k unstlic her
Eingaben fur diese zweite Klasse von Algorithmen werden nicht nur Verfahren zur Erzeu-
gung kunstlic her Stra ennetze vorgestellt, sondern auch Verfahren zur Generierung sys-
tematischer zeitabhangiger Anderungen des Verkehrs usses in Stra ennetzen. Auch die
zu diesem Zweck vorgestellten Verfahren folgen einem Kreislauf, ahnlich dem Paradigma
des Algorithm Engineering. Ausgehend von Echtweltdaten wird ein realistisches Modell
erstellt, beispielsweise anhand der Reprasentation eines Stra ennetzwerks. Dann wird ein
Generator entworfen, der Daten mit Eigenschaften erzeugt, die dem Modell entsprechen.
Dieser wird dann implementiert und es wird ausgewertet, inwieweit die hieraus generier-
ten Daten den Ursprungsdaten ahneln. Der Ruc kschluss auf notwendige Anpassungen am
Generator oder gar dem Modell vervollstandigt dann den Kreislauf. Dies fuhrt letztlich zu
einem Modell inklusive Generator, das Instanzen ahnlich den Echtweltdaten erzeugt.
Daten zur Evaluierung von Algorithmen fur plana-
re Graphen
Der Prozess des Algorithm Engineering wird hau g in der Festparameter-Algorithmik an-
gewendet. Dabei werden NP-schwere Probleme bezuglich Ihrer Instanzgro e polynomiell
O(1)und haben dann eine Laufzeit von f(k)n , wobei f eine berechenbare Funktion ist,
deren Laufzeit nur vom Parameter k abhangt. Beispielsweise lasst sich die Frage, ob ein vi
p
ksogenanntes Vertex Cover der Gro e k existiert, in LaufzeitO(c n) entscheiden, wobeic
eine Konstante ist und n der Gro e der Eingabe entspricht [AFN04]. Die Laufzeit h angt
also in erster Linie von der Gro e des Parameters k ab, der nicht zu gro werden sollte.
Hierbei spielen oft planare Graphen, eine Unterklasse der allgemeinen Graphenklasse, eine
wichtige Rolle. Ihre speziellen Eigenschaften ermoglichen es oft, starkere theoretische Aus-
sagen zu beweisen und e zientere Algorithmen anzugeben, als es f ur allgemeine Graphen
moglich ware. Konnte fur ein Problem ein Festparameter-Algorithmus fur planare Gra-
phen angegeben werden, wird oft zusatzlich in einer experimentellen Studie gezeigt, dass
die Algorithmen praktikabel sind, also die O-Notation keine hohen Konstanten versteckt.
Allerdings hangt diese Evaluierung stark von den gewahlten Instanzen ab. Ein Fakt, der in
manchen Forschungsarbeiten vernachlassigt wurde und belegbar dazu fuhrte, dass falsche
Schlusse aus experimentellen Studien gezogen wurden. Um dies zu verhindern, mussen
planare Graphen reprasentativ generiert werden. Grundlegend betri t dies die Wahl der
zu nutzenden Generatoren. Besitzen Generatoren zudem den Freiheitsgrad, die Anzahl
zu generierender Kanten ub er Parameter extern zu setzen, muss dieser ebenfalls geeignet
gewahlt werden.
Diese Arbeit untersucht eine Reihe ausgewahlter Generatoren zur Erzeugung planarer
Graphen. Die Analyse der Generatoren erfolgt auf ihre Vollstandigkeit, ihre Laufzeit und
Verteilungen von lokalen sowie globalen Ma en. Dazu werden unter anderem die Core-
Zahl, der Durchmesser, die Gro e des minimalen Dominating Set, die Baumbreite und der
Clustering Coe cient betrachtet. Dabei k onnen signi kante Unterschiede zwischen den
Generatoren festgestellt werden, die in algorithmischen Studien oft ignoriert wurden. Aus
diesen Ergebnissen resultieren Empfehlungen, welche Generatoren in einer experimentellen
Studie genutzt werden sollten, um reprasentative Schlussfolgerungen ziehen zu konnen.
Daten zur Evaluierung von Algorithmen zur kur-
zeste-Wege-Suche
Die Beschleunigung von Punkt-zu-Punkt-kurzeste-W ege-Anfragen in sehr gro en Stra en-
netzen kann als eine Paradedisziplin des Algorithm Engineering angesehen werden. So ist
der klassische Algorithmus von Dijkstra zwar exakt, liefert die Antwort auf Stra ennetzen
kontinentaler Gro e aber erst nach Sekunden. Daher wurden zahlreiche Ans atze entwickelt
und iterativ verbessert, so dass die Antwortzeiten heute um das millionenfache beschleu-
nigt sind. Diese Algorithmen wurden