La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

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

De
165 pages
Ajouté le : 01 janvier 2012
Lecture(s) : 0
Signaler un abus

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 darauf zugeschnitten, die speziellen strukturellen
Eigenschaften von Stra ennetzen auszunutzen. Daher ist nicht zu erwarten, dass sie sich
auf beliebigen Netzen ahnlich verhalten.
Kunstliche Stra ennetze
Forschern stehen zur Evaluierung ihrer Algorithmen im wesentlichen drei teilweise o ent-
liche Instanzen zur Verfugung: Tiger/Line umfasst die USA und wird vom U. S. Census
Bureau zur Verfugung gestellt. Den Teilnehmern der 9. Dimacs Challenge (2005) wurde
von der Firma PTV ein aus 14 europaischen Landern bestehender Datensatz zuganglich
gemacht. Freiwillige Mitarbeiter kartographieren beim o enen Internetprojekt OpenStreet-vii
Map (OSM) mit Hilfe handelsublic her GPS-Gerate die Welt. Da das Projekt noch relativ
jung ist, beschrankt sich die Verfugbarkeit detaillierter Karten auf Teile Europas und
der USA. Dies ist auch der Grund, warum die bisherigen Algorithmen hauptsachlich auf
die Eigenschaften von Tiger/Line und PTV-Daten hin optimiert und an ihnen evaluiert
wurden. Es ist aber zu erwarten, dass weitere kontinentale Netzwerke hinzukommen, die
dann vielleicht auch weitere, bislang nicht beobachtete Charakteristika aufweisen. Letztlich
werden Algorithmen in der Lage sein mussen, Kurzeste-W ege-Anfragen auf dem globalen
Stra ennetz zu beantworten.
Um Forschern schon heute zu ermoglichen, ihre Algorithmen an vielfaltigen und sehr
gro en Stra ennetzen zu testen, muss ein entsprechender Generator entwickelt werden.
Dabei stehen zwei Ziele im Vordergrund. Zum einen sollen die kunstlichen Netze den Echt-
weltnetzen optisch ahnlich sein. Zum anderen sollen Beschleunigungstechniken in beiden
Netzwerkarten ahnliches algorithmisches Verhalten aufweisen. Die Analyse der verfugbaren
Stra ennetze o enbart, dass Unterschiede in den Skalierungse ekten auftreten. Dies gilt
sowohl fur die Instanzen Tiger/Line und PTV als auch deren kontinentalen Entsprechun-
gen im OSM-Datensatz. Daraus folgt einerseits, dass sich die Reprasentationen desselben
Stra ennetzes unterscheiden und andererseits, dass Stra ennetze je nach geographischer
Lage unterschiedliche Charakteristika aufweisen.
Um kunstliche Stra ennetze zu erzeugen, wurde der bislang ungetestete Vorschlag eines
Generators von Abraham et al. [AFGW10] implementiert, wo notig angepasst und mit den
Echtweltinstanzen verglichen. Obwohl mit diesem Generator Instanzen generiert werden
konnten, die oft ein ahnliches Verhalten bei Anwendung von Beschleunigungstechniken
aufwiesen, entsprach deren Aussehen nicht dem der Echtweltinstanzen.
Daher wurde ein neuer Algorithmus entwickelt, der beide Ziele besser vereinbart. Die
zentrale Herausforderung dabei ist eine realistische Erfassung folgender Eigenschaften:
Stadte weisen eine hohere Knotendichte als landliche Regionen auf. Stadtische Stra en
sind relativ kurz und durfen nur mit geringer Geschwindigkeit befahren werden. Benach-
barte Stadte sind direkt durch Landstra en verbunden. Weit entfernte St adte werden
zusatzlic h durch Autobahnen untereinander angebunden. Dieses Modell der inharenten
Hierarchie von Stra ennetzen wurde im neuen Algorithmus durch die rekursive Gene-
rierung von Voronoidiagrammen nachgebildet. Durch diesen Ansatz erzeugte Graphen
ubertre en Abrahams Algorithmus sowohl in der optischen Ahnlichkeit als auch bezuglich
des algorithmischen Verhaltens.
Zusammenfassend ermoglicht dieser Teil der Arbeit Forschern, ihre Algorithmen an
mehr, gro eren und, bei entsprechender Streuung der Parameter, vielf altigeren Instanzen
zu evaluieren. Ferner konnte dieses neue Modell dazu beitragen, eine weitere Methodik
zur theoretischen Untersuchung von Beschleunigungstechniken zu entwickeln, ahnlich dem
System der Highway Dimension von Abraham et al. [AFGW10].
Systematische zeitabhangige Verkehrs usse in Stra ennetzen
Ein weiterer aktueller Punkt in der Forschung ist die Beschleunigung der Suche nach
schnellsten Punkt-zu-Punkt-Verbindungen unter Beruc ksichtigung von Informationen zum
zeitabhangigen Verkehrs uss. Werden diese nicht ber ucksichtigt, fuhrt beispielsweise der
schnellste Weg von Mannheim nach Karlsruhe immer ub er die Autobahn. Zieht man aber
den zeitabhangigen Verkehrs uss in Betracht, ist die Nutzung dieser Strecke im Morgen-viii
und Feierabendverkehr ungunstig, da aufgrund des hohen Verkehrsaufkommens mit deut-
lich reduzierter Durchschnittsgeschwindigkeit zu rechnen ist. Zu diesen Zeiten lohnt sich
der Weg ub er die Landstra e, da hier eine h ohere Durchschnittsgeschwindigkeit erreicht
wird und das Ziel schneller erreicht werden kann. Das hier betrachtete Szenario sind also
systematische zeitabhangige Verkehrs usse auf Strecken, wie sie taglich auftreten. Man-
gels o entlich zug anglicher Echtweltdaten sind Forscher in diesem Bereich voll auf die
Verwendung kunstlic her Daten angewiesen.
Bislang existierte nur ein Ansatz von Nannicini et al. [NDLS08], der weder auf die Ei-
genschaften von Stra ennetzen optimiert ist, noch auf seine Realit atsnahe getestet wurde
und trotzdem in zahlreichen Arbeiten Verwendung fand [Del11, KLSV10, BGNS10, DN08].
Daruber hinaus ist fraglich, ob experimentell gewonnene Erkenntnis basierend auf diesen
Daten aussagekraftig ist. So stellten Nannicini et al. fest, dass von ihnen getestete Algorith-
men unter Inkaufnahme approximativer Losungen um das zehnfache beschleunigt werden
konnen, und somit eine attraktive Option sind [NDLS08]. Dahingegen stellte Delling in
seiner Arbeit fest, dass unter gleichen approximativen Bedingungen, jedoch an Echtwelt-
daten getestet lediglich eine Beschleunigung um den Faktor 2 erreicht wird [Del09]. Daher
ware in einem Echtweltszenario die vorgeschlagene approximative Variante eine unwahr-
scheinliche Option.
In diesem Teil der Arbeit schlie en wir obige L uc ke durch die Entwicklung von Algo-
rithmen, die in der Lage sind, realistischere zeitabhangige Instanzen zu generieren. Um
dieses Ziel zu erreichen, analysieren wir einen vertraulichen zeitabhangigen Datensatz der
Firma PTV. Hieraus ergibt sich, dass der Verkehrs uss haupts achlich innerhalb einer Stadt
sowie zwischen der Stadt und einer gewissen Ein ussumgebung entsteht. Daher teilen die
entwickelten Ansatze das Stra ennetz in st adtische und landliche Regionen. Daraus las-
sen sich Stra enabschnitte ableiten, die wahrscheinlich mit hohem Verkehr belastet sein
werden. Dazu benotigen die Algorithmen zusatzliche Daten, die entweder Kanteninforma-
tionen zur Stra enkategorie oder die Koordinaten jedes Knotens beinhalten. Somit lassen
sich fur alle vorgestellten Echtwelt- und kunstlic h generierten Stra ennetze Verkehrs usse
erzeugen, da mindestens eine dieser Informationen im Netzwerk vorhanden ist. Experimen-
tell werden die durch diese Verfahren generierten Daten mit dem vertraulichen Datensatz
von Deutschland auf ihre lokalen, globalen sowie algorithmischen Eigenschaften hin vergli-
chen. Bei geeigneter Parameterwahl werden hierbei Daten erzeugt, die den Echtweltdaten
sehr ahnlich sind. Insbesondere gilt dies auch fur die oben beanstandeten Verfahren, woraus
wir schlie en, dass unsere neuen Algorithmen deutlich realistischere Instanzen generieren
als es bislang moglich war. Da die Verfahren parametrisiert und randomisiert sind, wird
die Generierung vielfaltiger Instanzen ermoglicht. In Zukunft konnen Forscher mit diesen
Verfahren realitatsnahe Daten generieren, unabhangig von der Herkunft ihrer Stra en-
netze, um die Qualitat Ihrer Evaluierung zu verbessern und robustere Algorithmen zu
entwickeln.Contents
Acknowledgments iii
Deutsche Zusammenfassung (German Summary) v
Contents x
1 Introduction and Outline 1
2 Preliminaries 5
2.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Basic De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 Network Analysis / Basic Graph Properties . . . . . . . . . . . . . . 9
2.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Basic Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Basic Complexity Classi cation . . . . . . . . . . . . . . . . . . . . . 13
2.2.3 Basic NP-Hard Problems . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Randomness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Data Structures and Basic Algorithms . . . . . . . . . . . . . . . . . . . . . 17
2.4.1 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.2 Basic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5 Route Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.1 Modeling of Road Networks . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.2 Basic Route-Planning Techniques . . . . . . . . . . . . . . . . . . . . 20
2.5.3 Basic Speed-Up Techniques . . . . . . . . . . . . . . . . . . . . . . . 22
I Arti cial Planar Graphs in Experiments 31
3 Planar Graph Generators 33
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Graph Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 (n)-Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.2 (n,m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.1 Dataset Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.2 Basic Network Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.3 Algorithmical Behavior . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.4 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64x Contents
II Arti cial Data in Experiments for Route-Planning Techniques 67
4 Arti cial Road Networks 69
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2 Real-World Road Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 Graph Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.1 The Generator of Abraham et al. . . . . . . . . . . . . . . . . . . . . 73
4.3.2 Voronoi-Based Generator . . . . . . . . . . . . . . . . . . . . . . . . 77
4.3.3 Standard Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.4 Data Generation and Graph Properties . . . . . . . . . . . . . . . . . . . . 84
4.4.1 Data Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.2 Graph Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.5 Algorithmic Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.5.1 Small-Scale Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.5.2 Large-Scale Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.6 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.7 Appendix of Plots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5 Arti cial Tra c Information 115
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.2 Analysis of Real-World Time-Dependent Data . . . . . . . . . . . . . . . . . 117
5.3 Algorithms for Assigning Pro les . . . . . . . . . . . . . . . . . . . . . . . . 122
5.3.1 General Five-Phases Approach . . . . . . . . . . . . . . . . . . . . . 122
5.3.2 Algorithm I: A ected-By-Category . . . . . . . . . . . . . . . . . . . 123
5.3.3 II: A ected-By-Region . . . . . . . . . . . . . . . . . . . . 126
5.3.4 Algorithm III: A ected-By-Level . . . . . . . . . . . . . . . . . . . . 128
5.3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6 Conclusion 143
Curriculum Vit 145
List of Publications 147
Bibliography 149