Positioning labels on graphical visualizations of graphs

• US 9,740,368 B1
• Filed: 08/10/2016
• Issued: 08/22/2017
• Est. Priority Date: 08/10/2016
• Status: Active Grant

• Current Assignee: Quid, Inc. (Netbase Quid)
• Original Assignee: Quid, Inc. (Netbase Quid)
• Inventors: Love, Oriana Jeannette, Lowe, Mary Kate, Wu, Hao
• Primary Examiner(s): Nabi, Reza
• Assistant Examiner(s): Rodriguez, Daniel
• Application Number:
  US15/233,007
• Time in Patent Office: 377 Days
• Field of Search: 715853
• CPC Class Codes: G06F 3/04817 using icons graphical or visual programming using iconic symbols G06F8/34
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• CPC Class Codes: G06F 3/04845 for image manipulation, e.g. dragging, rotation, expansion or change of colour
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 2200/24 involving graphical user interfaces [GUIs]

Abstract

Provided is a process, including: obtaining a graph to be visually represented in a graphical user interface of a client computing device; obtaining a set of text labels each corresponding to a respective collection of the nodes; determining a two dimensional or higher layout of the icons in the visual representation; segmenting the field of view into a plurality of segments; determining which icons are disposed within each of the segments of the field of view; determining positions of the text labels in the visual representation relative to one or more icons representing nodes in the respective collection of nodes based on the segment of the field of view in which the one or more icons representing nodes in the respective collection are disposed; and causing the visual representation to be displayed.

Claims

1. A method of arranging labels on a visual representation of a graph data structure, the method comprising:

obtaining, with one or more processors, a graph to be visually represented in a graphical user interface of a client computing device, the visual representation including a plurality of icons each representing one or more nodes of a graph data structure and links extending between the icons in the visual representation;

obtaining, with one or more processors, a set of text labels each corresponding to a respective collection of the nodes;

determining, with one or more processors, a two dimensional or higher layout of the icons in the visual representation within a field of view;

segmenting, with one or more processors, the field of view into a plurality of segments of the field of view;

determining, with one or more processors, which icons are disposed within each of the segments of the field of view;

determining, with one or more processors, positions of the text labels in the visual representation relative to one or more icons representing nodes in the respective collection of nodes based on the segment of the field of view in which the one or more icons representing nodes in the respective collection are disposed;

causing, with one or more processors, the visual representation to be displayed;

receiving a user request to zoom into a portion of the visual representation;

re-determining which icons are in which of the segments of the field of view after zooming; and

re-determining positions of the text labels based on changes in segments in which icons are disposed after zooming, wherein re-determining positions of the text labels based on changes in segments in which icons are disposed after zooming comprises;

determining a plurality of sets of sub-segments, each set of sub-segments having a plurality of sub-segments, each set of sub-segments corresponding to a respective cluster, each of the sets of sub-segments being centered at a different respective position of the field of view;

selecting, for each of the clusters, a respective sub-segment based on a segment of the field of view in which the respective cluster is disposed; and

positioning respective text labels for respective clusters or icons therein based on, and at least partially in, respective selected sub-segment corresponding to the respective clusters.

2. The method of claim 1, wherein:

each of the icons represents one node in a document-relationship graph;

each of the links is a line extending between pairs of the nodes and indicating a relationship between corresponding documents;

the layout comprises modeling pairwise interactions between the nodes that depend on distance between respective pairs of nodes as the respective pairs of nodes would appear in the visual representation;

the text labels indicate respective categories of the respective collections of nodes.

3. The method of claim 2, wherein:

visual representation includes user-selectable anchor icons visually associated in the visual representation with corresponding text labels.

4. The method of claim 3, wherein the anchor icons are user selectable to reveal information about the respective collection of nodes.

5. The method of claim 1, wherein:

obtaining a graph comprises obtaining a clustered semantic similarity graph of documents based on semantic similarly of unstructured text in the documents by performing operations comprising;

determining a feature vector for each document, each feature vector having plurality of scores, each score corresponding to a given n-gram and being based on;

an amount of occurrences of the given n-gram in the respective document,

a length of the respective document,

an amount of occurrences of the given n-gram in a plurality of other documents different from the respective document, and

whether the given n-gram is among the set of n-grams pertaining to the selected topic; and

determining an adjacency matrix based on the feature vectors, wherein rows and columns of the adjacency matrix correspond to the documents, values of the adjacency matrix correspond to a selected-topic-adjusted semantic similarity of documents corresponding to the respective row and column of the values, and values of the adjacency matrix are based on angles between feature vectors of the documents corresponding to the respective row and column of the values, the operations comprising steps for reducing movement of data across a memory hierarchy;

some of the icons are cluster icons that represent clusters of the graph;

some of the icons are node icons that represent nodes of the clusters and are positioned in the visual representation adjacent a cluster icon of a cluster in which the corresponding node is disposed;

determining a layout of the icons comprises determining a force directed layout in which the cluster icons are subject to different forces relative to the node icons;

the segments correspond to quadrants of the field of view;

determining positions of the text labels in the visual representation comprises;

positioning a text label in an upper left quadrant upward and to the left of a corresponding icon;

positioning a text label in a lower left quadrant downward and to the left of a corresponding icon;

positioning a text label in an upper right quadrant upward and to the right of a corresponding icon; and

positioning a text label in a lower right quadrant downward and to the right of a corresponding icon.

6. The method of claim 1, wherein the segments correspond to quadrants of the field of view.

7. The method of claim 1, wherein the segments correspond to at least three sectors of the field of view about a given point.

8. The method of claim 7, wherein the segments correspond to at least five sectors.

9. The method of claim 7, wherein the sectors are of the same angular size.

10. The method of claim 7, wherein at least some of the sectors have different angular sizes, the method comprising:

determining angular sizes of each of the sectors based on an amount of icons corresponding to each of the sectors.

11. The method of claim 10, wherein determining angular sizes comprises balancing the number of icons among the sectors.

12. The method of claim 10, wherein the point corresponds to a centroid of the icons.

13. The method of claim 7, wherein the point is a center of the field of view.

14. The method of claim 7, wherein the point is determined based on positions of the icons in the field of view.

15. The method of claim 1, wherein segmenting the field of view comprises:

sub-dividing the field of view according to a Voronoi diagram of the icons positions after determining the layout to form a plurality of Voronoi regions by performing a k-means cluster of vertical and horizontal coordinates of the icons in the field of view;

segmenting each of the Voronoi regions into a plurality of sectors about a point at a location selected based on a centroid of the respective Voronoi region.

16. The method of claim 1, wherein determining a plurality of sets of sub-segments comprises:

determining a plurality of sets of sub-segments quadrants, each set of sub-segment quadrants having four sub-segments, the sub-segment quadrants being selected based on a segment in the field of view in which a corresponding cluster is disposed.

17. The method of claim 1, comprising:

animating a movement of a text label from a pre-zoom position relative to a corresponding icon to a post-zoom position relative to the corresponding icon.

18. The method of claim 17, wherein animating movement comprises:

animating movement according to an ease-in translation, an ease-out translation, or both.

19. The method of claim 18, wherein animating movement comprises:

animating movement according to a cubic-Bezier translation.

20. The method of claim 1, wherein:

obtaining a graph to be visually represented in a graphical user interface comprises performing steps for obtaining a graph; and

determining a layout of the icons comprises steps for determining a layout of the icons.

21. The method of claim 1, wherein:

segmenting the field of view comprises steps for segmenting the field of view;

determining which icons are in each of the segments comprises steps for determining which icons are in each of the segments;

determining positions of the text labels in the visual representation comprises;

steps for determining positions of the text labels in the visual representation; and

steps for animating movement between positions due to panning;

causing the visual representation to be displayed comprises steps for causing the visual representation to be displayed.

22. The method of claim 1, comprising:

providing a computational linguistics system configured to send the visual representation to a remote client computing device in a web browser of the remote client computing device.

23. A system, comprising:

one or more processors; and

memory storing instructions that when executed by at least some of the processors effectuate operations comprising;

obtaining a graph to be visually represented in a graphical user interface of a client computing device, the visual representation including a plurality of icons each representing one or more nodes of a graph data structure and links extending between the icons in the visual representation;

obtaining a set of text labels each corresponding to a respective collection of the nodes;

determining a two dimensional or higher layout of the icons in the visual representation within a field of view;

segmenting the field of view into a plurality of segments;

determining, with one or more processors, which icons are disposed within each of the segments of the field of view of the field of view;

determining positions of the text labels in the visual representation relative to one or more icons representing nodes in the respective collection of nodes based on the segment of the field of view in which the one or more icons representing nodes in the respective collection are disposed;

causing the visual representation to be displayed;

receiving a user request to zoom into a portion of the visual representation;

re-determining which icons are in which segments of the field of view after zooming; and

re-determining positions of the text labels based on changes in segments in which icons are disposed after zooming, wherein re-determining positions of the text labels based on changes in segments in which icons are disposed after zooming comprises;

determining a plurality of sets of sub-segments, each set of sub-segments having a plurality of sub-segments, each set of sub-segments corresponding to a respective cluster, each of the sets of sub-segments being centered at a different respective position of the field of view;

selecting, for each of the clusters, a respective sub-segment based on a segment of the field of view in which the respective cluster is disposed; and

positioning respective text labels for respective clusters or icons therein based on, and at least partially in, respective selected sub-segment corresponding to the respective clusters.