Visualizing set data with the metro map metaphor

Abstract

Verschiedenste visuelle Metaphern existieren, um Datensätze aus der Mengenlehre grafisch darzustellen. Manche Metaphern, z.B. Venn oder Euler Diagramme, sind einfach zu interpretieren, aber skalieren schlecht mit steigender Anzahl an Elementen und Mengen. Andere Metaphern können gut mit großen Datensätzen umgehen, aber dadurch dass sie nur gut in Visual Analytics Programmen integriert funktionieren, wird Erfahrung und Interaktivität zur Interpretation benötigt. Von Menschen kann bis zu einem gewissen Grad vorausgesetzt werden, dass sie wissen wie eine Metro-Karte zu lesen und zu interpretieren ist. Ebenfalls zeigen Beispiele aus der realen Welt, dass Metro-Karten Hunderte Stationen und Linien gut darstellen können. Die Metro-Karten Metapher könnte sich deshalb als guter Kompromiss zwischen Lesbarkeit und Skalierbarkeit für mittelgroße Datensätze herausstellen. Wir modellieren Datensätze mit einem Hypergraph H = (V, S ), um in sieben Schritten durch eine lineare Pipeline eine Metro-Karte M = (G, L, D) zu erzeugen. Zuerst wird die Problemgröße reduziert, um danach eine Metroliniendefinition L zu finden. Unsere Eingabedatensätze haben inhärent keine eigene Metroliniendefinitionen, aber dies ist äquivalent mit dem Erstellen eines Support Pfads für jede Hyperkante von H. Die Vereinigung aller Support Pfade bildet den Support Graphen G. Unsere Methodik zum Erstellen versucht die benötigten Kanten in G zu minimieren. Anschließend betten wir G in der 2-dimensionalen Zeichenfläche ein, schematisieren das Layout und führen Nachbearbeitungsschritte durch, um die Karte zu beschriften und sich kreuzende Linien zu minimieren. Nachdem wir die Pipeline präsentiert haben, stellen wir unsere Ergebnisse anhand verschiedener Datensätzen vor, führen eine Selbstevaluation durch und vergleichen mit anderen Visualisierungssystemen. Abschließend gehen wir noch auf Verbesserungen der statischen Metro-Karten ein, die durch Interaktivität erreicht werden können.

Several metaphors exist to visualize set systems. Some metaphors are easy to read and interpret, like Venn or Euler diagrams, but usually do not scale well to larger data sets. Other metaphors work well with large data sets, but are often implemented in visual analytics systems that require explanation in order to be used. In a real-world scenario, people are familiar with reading metro maps and these metro maps have proven to effectively scale up for hundreds of stations and dozen of lines. Using the metro map metaphor for set visualization could offer a functional middle ground between readability and scalability. We formalize the problem by using a hypergraph H = (V, S ) to represent set data and create a metro map drawing M = (G, L, D) by using a 7-step linear pipeline. We first reduce the problem size before we create a metro line definition L, as set data does not inherently have this information. Creating a metro line definition is equivalent with finding a support path for every hyperedge of H, where the union of all support paths is the path-based support graph G. We propose a method for constructing a path-based support graph that aims to minimize the edges required to draw the graph. Because G does not have any contextual information on where to place the vertices on the map, we create an initial layout before we schematize it. Finally, we show how to perform post-processing for adding labels and minimizing line crossings in the drawing D. Afterwards, the implemented system is self-evaluated by a set visualization task taxonomy and compared against other systems. We also reflect on how interactivity could improve a static drawing of the metaphor.