Graphenzeichnen mit hardwarebeschleunigter MDS
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
Diese Masterarbeit behandelt die kombinierte Multidimensionale Skalierung (kombinierte MDS), ein Verfahren zum Zeichnen von Graphen, welches Pivot-MDS mit der ausgedünnten Stressmajorisierung verknüpft. Dabei wird das von Pivot-MDS generierte Layout, welches sich sehr effizient berechnen lässt, als Initiallayout für die ausgedünnte Stressmajorisierung verwendet. Dieses Initiallayout reduziert zum einen die Wahrscheinlichkeit der Stressmajorisierung, in lokalen Minima der Stressfunktion zu enden, zum anderen reduziert es die Anzahl von Iterationen, welche die Stressmajorisierung benötigt, um ein gutes Layout zu finden.
Diese Kombination führt zu einem laufzeiteffizienten Verfahren, welches beim Zeichnen von Graphen hochwertige Ergebnisse liefert. Weiter wird eine eigene parallelisierte Implementierung der kombinierten MDS vorgestellt, welche die Hardwarebeschleunigung der Grafikkarte nutzt. Diese Implementierung erreicht im Vergleich zu effizienten Implementierungen anderer Verfahren gute Laufzeiten und Ergebnisse. Ferner bietet diese Implementierung die Möglichkeit, zusätzlich zu zweidimensionalen auch dreidimensionale Graphenlayouts zu erstellen, welche mittels eines eigens erstellen Programms visualisiert werden können.
Zusammenfassung in einer weiteren Sprache
This Master thesis deals with combined multidimensional scaling (combined MDS), which is a graph drawing method combining both Pivot-MDS and sparse stress majorisation. The layout generated by Pivot-MDS, which can be calculated efficiently, is thereby used as initial layout of the sparse stress majorisation. On the one hand this initial layout reduces the possibility of ending in a local minimum of the stress function, on the other hand it reduces the number of iterations used by the stress majorisation to find a pleasing layout. This results in a method which is both efficient and generating pleasing layouts.
Further a parallel implementation using the graphics card for hardware acceleration is presented. This implementation offers good runtime properties and results compared to efficient implementations of other graph drawing methods. In addition to generating two dimensional layouts this implementation offers the possibility of creating three dimensional layouts which can be visualized by a self made program.
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
KAISER, Daniel, 2011. Graphenzeichnen mit hardwarebeschleunigter MDS [Master thesis]BibTex
@mastersthesis{Kaiser2011Graph-18736, year={2011}, title={Graphenzeichnen mit hardwarebeschleunigter MDS}, author={Kaiser, Daniel} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/18736"> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/18736/2/masterarbeit_kaiserd.pdf"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dc:creator>Kaiser, Daniel</dc:creator> <dc:rights>terms-of-use</dc:rights> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-03-05T07:19:56Z</dcterms:available> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/18736/2/masterarbeit_kaiserd.pdf"/> <dc:language>deu</dc:language> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-03-05T07:19:56Z</dc:date> <dcterms:alternative>Graph Drawing Using Hardware Accelerated MDS</dcterms:alternative> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/18736"/> <dc:contributor>Kaiser, Daniel</dc:contributor> <dcterms:abstract xml:lang="deu">Diese Masterarbeit behandelt die kombinierte Multidimensionale Skalierung (kombinierte MDS), ein Verfahren zum Zeichnen von Graphen, welches Pivot-MDS mit der ausgedünnten Stressmajorisierung verknüpft. Dabei wird das von Pivot-MDS generierte Layout, welches sich sehr effizient berechnen lässt, als Initiallayout für die ausgedünnte Stressmajorisierung verwendet. Dieses Initiallayout reduziert zum einen die Wahrscheinlichkeit der Stressmajorisierung, in lokalen Minima der Stressfunktion zu enden, zum anderen reduziert es die Anzahl von Iterationen, welche die Stressmajorisierung benötigt, um ein gutes Layout zu finden.<br /><br />Diese Kombination führt zu einem laufzeiteffizienten Verfahren, welches beim Zeichnen von Graphen hochwertige Ergebnisse liefert. Weiter wird eine eigene parallelisierte Implementierung der kombinierten MDS vorgestellt, welche die Hardwarebeschleunigung der Grafikkarte nutzt. Diese Implementierung erreicht im Vergleich zu effizienten Implementierungen anderer Verfahren gute Laufzeiten und Ergebnisse. Ferner bietet diese Implementierung die Möglichkeit, zusätzlich zu zweidimensionalen auch dreidimensionale Graphenlayouts zu erstellen, welche mittels eines eigens erstellen Programms visualisiert werden können.</dcterms:abstract> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:issued>2011</dcterms:issued> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:title>Graphenzeichnen mit hardwarebeschleunigter MDS</dcterms:title> </rdf:Description> </rdf:RDF>