A Visual Analytics Approach for Comparing Tree-Structures

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2012
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Masterarbeit/Diplomarbeit
Publikationsstatus
Published
Erschienen in
Zusammenfassung

Today's storage capabilities facilitate the accessibility and long term archival of increasingly large data sets usually refered to as "Big Data". Tree-structured hierarchical data is very common, for instance phylogenetic trees, filesystem data, syntax trees
and often times organizational structures. Analysts often face the problem of gathering information through comparison of multiple trees. Visual analytic tools aid analysts by combining visual clues and analytical reasoning. Visual representations are ideal as they tend to stress human strength which are great at interpreting visualizations.

We therefore propose a prototype for comparing tree-structures which either evolve through time or usually share large node-sets. Our backend Treetank is a tree-storage system de-signed to persist several revisions of a tree-structure efficiently. Different types of similarity measures are implemented adhering to the well known tree-to-tree edit problem.

The aggregated tree-structure is input to several interactive visualizations. A novel Sunburst-layout facilitates the comparison between two revisions. It provides several interaction options such as zooming as well as drilling down into the tree by selecting a new root node.

Using hierarchical edge bundles to visualize moves reduces clutter from edge crossings. Several filtering-techniques are available to compare even very large tree-structures up to many hundred thousand or even millions of nodes. Small multiple displays of the Sunburst-layout aid the comparison between multiple trees.

A short evaluation and a study of three application scenarios as well as performance evaluations proves the applicability of our approach. It surpasses most other approaches in terms of generability and scalability due to our database driven approach which allows for a fast ID-based difference algorithm optionally using hashes for filtering changed subtrees.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
visual analytics, diff compare, tree-to-tree, json, visualization
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690LICHTENBERGER, Johannes, 2012. A Visual Analytics Approach for Comparing Tree-Structures [Master thesis]
BibTex
@mastersthesis{Lichtenberger2012Visua-21041,
  year={2012},
  title={A Visual Analytics Approach for Comparing Tree-Structures},
  author={Lichtenberger, Johannes}
}
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/21041">
    <dc:creator>Lichtenberger, Johannes</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:language>eng</dc:language>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:issued>2012</dcterms:issued>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-12-13T09:55:18Z</dcterms:available>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-12-13T09:55:18Z</dc:date>
    <dc:contributor>Lichtenberger, Johannes</dc:contributor>
    <dcterms:abstract xml:lang="eng">Today's storage capabilities facilitate the accessibility and long term archival of increasingly large data sets usually refered to as "Big Data". Tree-structured hierarchical data is very common, for instance phylogenetic trees, filesystem data, syntax trees&lt;br /&gt;and often times organizational structures. Analysts often face the problem of gathering information through comparison of multiple trees. Visual analytic tools aid analysts by combining visual clues and analytical reasoning. Visual representations are ideal as they tend to stress human strength which are great at interpreting visualizations.&lt;br /&gt;&lt;br /&gt;We therefore propose a prototype for comparing tree-structures which either evolve through time or usually share large node-sets. Our backend Treetank is a tree-storage system de-signed to persist several revisions of a tree-structure efficiently. Different types of similarity measures are implemented adhering to the well known tree-to-tree edit problem.&lt;br /&gt;&lt;br /&gt;The aggregated tree-structure is input to several interactive visualizations. A novel Sunburst-layout facilitates the comparison between two revisions. It provides several interaction options such as zooming as well as drilling down into the tree by selecting a new root node.&lt;br /&gt;&lt;br /&gt;Using hierarchical edge bundles to visualize moves reduces clutter from edge crossings. Several filtering-techniques are available to compare even very large tree-structures up to many hundred thousand or even millions of nodes. Small multiple displays of the Sunburst-layout aid the comparison between multiple trees.&lt;br /&gt;&lt;br /&gt;A short evaluation and a study of three application scenarios as well as performance evaluations proves the applicability of our approach. It surpasses most other approaches in terms of generability and scalability due to our database driven approach which allows for a fast ID-based difference algorithm optionally using hashes for filtering changed subtrees.</dcterms:abstract>
    <dcterms:title>A Visual Analytics Approach for Comparing Tree-Structures</dcterms:title>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/21041"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/21041/2/master-thesis-Lichtenberger.pdf"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/21041/2/master-thesis-Lichtenberger.pdf"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Begutachtet
Diese Publikation teilen