Method and apparatus for graphical data interaction and vizualization of graphs via paths
Inventors
Moore, Jason A. • LEBO, TIMOTHY
Assignees
United States Department of the Air Force
Publication Number
US-9715748-B2
Publication Date
2017-07-25
Expiration Date
2035-07-28
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Abstract
Method for displaying and identifying relevant paths through a graph by displaying them in a tabular format and providing user defined and computed values and filters. Each graph is represented as a set of nodes and edges. Each path through the graph is displayed as a row in a table where the user can apply sorting, filtering, and compute intrinsic or extrinsic information to augment the data.
Core Innovation
The invention provides a method and apparatus for displaying computer generated graphs as a series of paths in a tabular or spreadsheet style format, referred to as Graphtables. Each graph consists of a set of nodes and edges, and each path through the graph is displayed as a row in a table with columns alternating between nodes and edges. The table columns are subdivided into subcolumns that represent the attributes of the respective nodes or edges. This structure accommodates non-uniform metadata types across nodes and edges.
The invention addresses problems inherent in traditional graph visualization methods, which rely on graph layout algorithms that become less effective as graph size and complexity increase. Traditional visualizations fail to preserve proximity principles and are not well suited for rapid, sequential queries, often requiring different layouts for different types of analysis which can lead to loss of context. The invention provides user-interactive functionality allowing dynamic sorting, filtering, and computation of intrinsic and extrinsic values on paths to prioritize displayed paths based on user queries without losing the overall graph context.
Graphtables allow a user to configure the sorting order of columns, define the displayed data in each column, and compute new values or fields based on graph data. Filtering is handled by ranking paths based on filter criteria rather than eliminating data, enabling the user to see paths that partially match filter criteria. The method includes features like edge bundling to reduce visual clutter by representing repeated edges across rows only once, and allows user insertion of additional computed columns which can be moved and sorted. This form of representation and interaction offers a powerful, intuitive alternative to traditional node-link graph visualizations.
Claims Coverage
The patent claims comprise nine inventive features related to a computer system and software for graphical visualization, retrieval, sorting, filtering, and interaction with graph data presented as a table of paths.
Graph visualization as tabular paths with metadata-based columns and rows
Defines nodes and edges with user metadata, visualizes the graph as multiple major columns (nodes and edges) subdivided into metadata subcolumns, with each row representing a path traversal and applies sorting criteria to reorder rows based on subcolumn values.
Visual differentiation of nodes and edges
Encircles data cells corresponding to nodes and strikes a continuous line through cells corresponding to edges to improve user interpretation.
Determination of number of major columns
Defines the number of major columns by the length of the longest traversal through the graph.
Multi-level sorting with preservation of previous order
Allows retention of row reordering from prior sorts and application of subsequent sorting criteria maintaining sorting precedence.
Graph-wide filtering with sorted ranking and visual cue
Applies graph filtering by evaluating all cells; rows failing filter criteria are sorted after non-failing rows and a visual demarcation line separates filtered from non-filtered rows.
Column-based filtering with sorted ranking and visual cue
Applies filters to cells within a specific column; rows with failing cells are sorted below those passing and separated by a visual cue.
Edge bundling for consecutive identical cell values
When consecutive rows have identical cell values in a major column, edge bundling is indicated by visual cues connecting those edges to reduce clutter.
Insertion of additional computed columns with sorting
Enables insertion of new major and sub columns for derived data and applies sorting criteria on these inserted subcolumns.
Visual cue as a line for filter demarcation
Uses a line as the visual indicator marking the transition between filtered and non-filtered rows.
The claims together cover a comprehensive system that visualizes graph traversals as table rows, enhances interpretability through visual cues, supports complex sorting and filtering operations maintaining context, and provides extensibility via additional computed columns and edge bundling.
Stated Advantages
Enables intuitive interaction with graph data using a spreadsheet style metaphor, improving ease of understanding and querying complex graph structures.
Allows dynamic sorting and filtering of paths based on intrinsic and extrinsic values without losing context of other paths.
Preserves proximity and contextual relationships by displaying all paths with filtered results ranked rather than omitted.
Reduces visual clutter through edge bundling by avoiding duplication of shared edges across rows.
Supports user-defined computed columns that can be integrated into sorting and visualization seamlessly.
Documented Applications
Analyzing social networks by visualizing and filtering paths within network graphs.
Analyzing computer networks to identify relevant communication or data paths.
Interpreting road networks and subway maps through path-based visualization.
Exploring command and control structures using graph data visualization in tabular formats.
Interested in licensing this patent?