Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMulti-level tree based approach for interactive graph visualization with semantic zoom
107
0
0.0
(
0
)
Added by
Felice De Luca
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Human subject studies that map-like visualizations are as good or better than standard node-link representations of graphs, in terms of task performance, memorization and recall of the underlying data, and engagement [SSKB14, SSKB15]. With this in mind, we propose the Zoomable Multi-Level Tree (ZMLT) algorithm for multi-level tree-based, map-like visualization of large graphs. We propose seven desirable properties that such visualization should maintain and an algorithm that accomplishes them. (1) The abstract trees represent the underlying graph appropriately at different level of details; (2) The embedded trees represent the underlying graph appropriately at different levels of details; (3) At every level of detail we show real vertices and real paths from the underlying graph; (4) If any node or edge appears in a given level, then they also appear in all deeper levels; (5) All nodes at the current level and higher levels are labeled and there are no label overlaps; (6) There are no edge crossings on any level; (7) The drawing area is proportional to the total area of the labels. This algorithm is implemented and we have a functional prototype for the interactive interface in a web browser.
rate research
Read More
We study the question whether a crossing-free 3D morph between two straight-line drawings of an $n$-vertex tree can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-dimensional and at the one in which they are three-dimensional. In the former setting we prove that a crossing-free 3D morph always exists with $O(log n)$ steps, while for the latter $Theta(n)$ steps are always sufficient and sometimes necessary.
Visualization recommendation or automatic visualization generation can significantly lower the barriers for general users to rapidly create effective data visualizations, especially for those users without a background in data visualizations. However, existing rule-based approaches require tedious manual specifications of visualization rules by visualization experts. Other machine learning-based approaches often work like black-box and are difficult to understand why a specific visualization is recommended, limiting the wider adoption of these approaches. This paper fills the gap by presenting KG4Vis, a knowledge graph (KG)-based approach for visualization recommendation. It does not require manual specifications of visualization rules and can also guarantee good explainability. Specifically, we propose a framework for building knowledge graphs, consisting of three types of entities (i.e., data features, data columns and visualization design choices) and the relations between them, to model the mapping rules between data and effective visualizations. A TransE-based embedding technique is employed to learn the embeddings of both entities and relations of the knowledge graph from existing dataset-visualization pairs. Such embeddings intrinsically model the desirable visualization rules. Then, given a new dataset, effective visualizations can be inferred from the knowledge graph with semantically meaningful rules. We conducted extensive evaluations to assess the proposed approach, including quantitative comparisons, case studies and expert interviews. The results demonstrate the effectiveness of our approach.
Proceedings of GD2020: This volume contains the papers presented at GD~2020, the 28th International Symposium on Graph Drawing and Network Visualization, held on September 18-20, 2020 online. Graph drawing is concerned with the geometric representation of graphs and constitutes the algorithmic core of network visualization. Graph drawing and network visualization are motivated by applications where it is crucial to visually analyse and interact with relational datasets. Information about the conference series and past symposia is maintained at http://www.graphdrawing.org. The 2020 edition of the conference was hosted by University Of British Columbia, with Will Evans as chair of the Organizing Committee. A total of 251 participants attended the conference.
The problem of {em efficiently} finding the best match for a query in a given set with respect to the Euclidean distance or the cosine similarity has been extensively studied in literature. However, a closely related problem of efficiently finding the best match with respect to the inner product has never been explored in the general setting to the best of our knowledge. In this paper we consider this general problem and contrast it with the existing best-match algorithms. First, we propose a general branch-and-bound algorithm using a tree data structure. Subsequently, we present a dual-tree algorithm for the case where there are multiple queries. Finally we present a new data structure for increasing the efficiency of the dual-tree algorithm. These branch-and-bound algorithms involve novel bounds suited for the purpose of best-matching with inner products. We evaluate our proposed algorithms on a variety of data sets from various applications, and exhibit up to five orders of magnitude improvement in query time over the naive search technique.
Solomon and Elkin constructed a shortcutting scheme for weighted trees which results in a 1-spanner for the tree metric induced by the input tree. The spanner has logarithmic lightness, logarithmic diameter, a linear number of edges and bounded degree (provided the input tree has bounded degree). This spanner has been applied in a series of papers devoted to designing bounded degree, low-diameter, low-weight $(1+epsilon)$-spanners in Euclidean and doubling metrics. In this paper, we present a simple local routing algorithm for this tree metric spanner. The algorithm has a routing ratio of 1, is guaranteed to terminate after $O(log n)$ hops and requires $O(Delta log n)$ bits of storage per vertex where $Delta$ is the maximum degree of the tree on which the spanner is constructed. This local routing algorithm can be adapted to a local routing algorithm for a doubling metric spanner which makes use of the shortcutting scheme.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
