Abstract:
Techniques for visualizing sets are described. Arbitrary subsets of data elements are represented by corresponding graphic lines. The data elements in a set are connected up sequentially by a corresponding graphic line, the graphic line passing through each data element once with minimal or no self-overlapping. The graphic lines may be curved, for instance in the form of spline segments interconnecting nodes that represent the respective subsets. Each line may have a different color. Data elements not belonging to a subset may still be represented by a nodes but are not connected with any of the graphic lines, thus it can be seen which data elements belong to which sets, if any.

Description:
BACKGROUND 
       [0001]    Data visualization tools have been used to find properties of and relations between data elements in large datasets. For example, biologists may use data visualization tools to understand the relationships between groups of genes in the human genome, social scientists may use visualization tools to study interactions between communities of people in social networks, and machine learning experts sometimes explore how data has been categorized using data visualization tools. 
         [0002]    One approach used in data visualization tools is to visually represent sets. Several techniques have been used to visually represent sets, and these techniques can influence how people perceive properties of individual elements and relationships between elements. Consider Euler or Venn diagrams, which are commonly used set representations. While sometimes effective, visual set representations with these types of diagrams often overlap due to membership intersection, and excessive intersections or overlaps may cause these diagrams to lose their expressive qualities. That is, when numerous sets intersect with each other, most types of set representations become difficult to read. 
         [0003]      FIG. 1  shows an example Venn diagram  100 . Points  102  (also referred to as graphic nodes) represent data elements that belong to sets represented by regions  104 . In the example of  FIG. 1 , points  102 A belong only to a set represented by region  104 A. As seen in area  106 , where many regions  104  overlap, it can be difficult to interpret the relevant data and the relations between sets. Enhancements such as color, transparency, and texture may not fully address the problem of visual comprehension when many intersecting sets are displayed. Previous methods for visually representing sets may have other shortcomings, and there is a general need for set representations that are readily grasped and which facilitate new ways of understanding interrelated sets of data. Consequently, techniques related to linear representations of sets are discussed below. 
       SUMMARY 
       [0004]    The following summary is included only to introduce some concepts discussed in the Detailed Description below. This summary is not comprehensive and is not intended to delineate the scope of the claimed subject matter, which is set forth by the claims presented at the end. 
         [0005]    Techniques for visualizing sets are described. Arbitrary subsets of data elements are represented by corresponding graphic lines. The data elements in a set are connected up sequentially by a corresponding graphic line, the graphic line passing through each data element once with minimal or no self-overlapping. The graphic lines may be curved, for instance in the form of spline segments interconnecting nodes that represent the respective subsets. Each line may have a different color. Data elements not belonging to a subset may still be represented by a nodes but are not connected with any of the graphic lines, thus it can be seen which data elements belong to which sets, if any. 
         [0006]    Many of the attendant features will be explained below with reference to the following detailed description considered in connection with the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]    The present description will be better understood from the following detailed description read in light of the accompanying drawings, wherein like reference numerals are used to designate like parts in the accompanying description. 
           [0008]      FIG. 1  shows an example Venn diagram. 
           [0009]      FIG. 2  shows a data visualization tool. 
           [0010]      FIG. 3  shows a map as displayed on a computer display where points of interest are displayed on the map. 
           [0011]      FIG. 4  shows a flow for producing linesets. 
           [0012]      FIG. 5  shows an example of overlapping or intersecting graph nodes. 
           [0013]      FIG. 6  shows a process for computing graphic lines that represent sets of data elements. 
           [0014]      FIG. 7  shows linesets used in a mapping application. 
           [0015]      FIG. 8  shows a social network. 
           [0016]      FIG. 9  shows an interactive interface for exploring a restaurant dataset. 
           [0017]      FIG. 10  shows a list interface that can be included with interactive interface. 
           [0018]      FIG. 11  shows an example computer. 
       
    
    
     DETAILED DESCRIPTION 
     Overview 
       [0019]      FIG. 2  shows a data visualization tool  120 . The data visualization tool  120  may be in the form of software executing on one or more computers. Tools for interactively navigating data, defining subsets, and displaying results are known and described in detail elsewhere. The data visualization tool  120  is only an example provided to give context to the linear set visualization techniques described below. A data store  122 , such as a database or network data service, stores data elements  124  (e.g., rows) in interrelated tables  126 . A search or database engine  128  provides query functionality. When a query or search condition is received, the database engine  128  returns results that satisfy the query. A communication interface or front-end  130  may be used to facilitate communication between the data store  122  and the data visualization tool  120 . 
         [0020]    The data visualization tool  120  may include a search interface  132  through which a user may specify a data source such as data store  122 , input search conditions (e.g., a query), and otherwise define a dataset to work with. When a search condition is sent to the front-end  130 , a copy of (or a reference to) a dataset is returned. In one embodiment, a filter UI (user interface)  134  may have various components that a user can interact with to visually explore the current dataset. A current visualization may be displayed in a display area  136 . As will be discussed below, graphic nodes representing elements of the dataset may be displayed. As a user defines different sets of the data elements, different visual representations of the sets (or, subsets) are displayed. In one embodiment, different sets of data elements are displayed for different respective queries of perhaps different types of data elements. In another embodiment, a dataset is obtained and then subsets of a same data type are specified by a user. 
         [0021]    Note that the visualization techniques described herein can be used in other contexts where sets of data elements may be visualized. For example,  FIG. 3  shows a map  138  as displayed on a computer display where points of interest  140  are displayed on the map  138 . Sets or subsets of the points of interest are represented by respective lines  142 . Lines  142  may have various attributes discussed further below, generally, however, a line representing a set (i.e., a “lineset”) will connect with each of its points or graphic nodes one time, and a line may be constructed to avoid crossing itself. Conceptually, this may be thought of as similar to beads (nodes) on a string (lines  142 ). 
         [0022]    The different sets or subsets of the points of interest  140  may represent any kind of information. For example, there may be a set of doctor office locations and a set of bus stop locations, each represented by a corresponding line  142 . Or, there may be a master dataset of restaurant locations, which may be grouped into subsets by category of cuisine or other criteria. 
         [0023]    As used herein, a node-connecting “line” (“graphic line”, “lineset”) will refer to any curved or serpentine line segment, any linear sequence of straight segments, and/or a sequence of curving line segments and straight line segments. Lines need not be solid and may be distinguished by width, color, fill pattern, and so on. Any graphic that a human will perceive as stringing together individual nodes can be used as a line (to be distinguished from patches, regions, areas, etc.). In general, such lines may be used in any case where sets of data elements are displayed or represented by graphic elements or nodes. 
         [0024]      FIG. 4  shows a flow for producing linesets. A dataset  150  is presumed available in a data structure, file, memory, etc. The dataset  150  has elements that may be database rows, nodes in a data structure, etc., with fields containing values. In one embodiment, when the dataset  150  is received, nodes representing the data elements may be displayed. The elements are in sets A, B, and C, which may overlap. The dataset  150  may also have elements that do not belong to these sets. A lineset visualization component  152  receives the dataset  150  and computes a layout of graph nodes  150 A,  150 B,  150 C, and  150 D. In this example, it will be assumed that each element has fields containing a pre-defined location that can be translated to a display position, for instance, a geographic location or street address. Graph nodes  150 A represent elements that belong to a set A, graph nodes  150 B represent elements in set B, and graph nodes  150 C represent elements in set C. Graph nodes  150 D represent elements not in set A, B, or C. 
         [0025]    The lineset visualization component  152  also computes linesets  154 A,  154 B, and  154 C, which correspond to sets A, B, and C, respectively. Lines are computed based on set membership and locations of elements in a set. More specifically, given a set of elements such as set A, the locations in the set are connected with each other by a suitable algorithm such as a traveling salesman algorithm. This algorithm may produce an ordering of the elements. Given an ordering of the elements and their locations, graphical features may be computed, for instance, spline curves may be fitted between graph nodes. Some graph nodes that represent elements that belong to more than one set are also included with the corresponding linesets. To aid a viewer&#39;s comprehension, concentric rings, overlapping graph nodes, or other graphic indicia may be displayed to indicate (as represented by a graph node) set memberships of a given data element.  FIG. 5  shows an example of overlapping or intersecting graph nodes  170 . A single data element is represented, which belongs to three different sets, each represented by a portion of a linesets  172 A,  172 B,  172 C. At a glance it can easily be seen which sets the corresponding data element belong to. In one embodiment, a graph node  174  is displayed (as it might be displayed if not connected with any lineset), and is at least partly encompassed by pixels of each lineset to which it belongs. 
         [0026]    Although an ordering can be computed algorithmically, an ordering can also be based on a property of the data elements. For instance, the data elements may represent tourist landmarks and may each have a visitor rating property. An ordering might be defined based on the ratings, where a set of data elements (landmarks) are ordered from highest rating to lowest rating. An ordering might be according to an order of physically visiting places, alphabetic order, and so on. 
         [0027]      FIG. 6  shows a process for computing graphic lines that represent sets of data elements. At step  190 , a dataset is accessed. Subsets of the data elements are assumed to be defined. At step  192 , locations of points or nodes that represent the elements are obtained or computed. Some types of data elements may have their own location data, such as map locations. Other types of data elements may have their locations computed based on values of the data elements, based on their position in a data structure (e.g., a graph or tree), etc. That is, they have only derived display locations. In either case, given locations of the data elements, graphic nodes (e.g., icons, symbols, shapes, etc.) are displayed accordingly. 
         [0028]    At step  194 , lines are computed for each respective set of data elements. Given an arbitrary distribution of points in space, there are many known ways to draw a line visiting all of the points once. In selecting an algorithm, it may be helpful to consider algorithms that draw curves that are as succinct (short) as possible and that minimally or do not self-cross. The Lin-Kernighan traveling salesman heuristic may be used to minimize the length of a curve in reasonable computation time with little or no self-crossing. Given a computed sequence of elements/nodes (members of a set), curves therebetween may be drawn using piecewise Bezier splines with virtual control points to ensure that a spline visits all set members. In other words, the graphic line computation may involve first finding an order of the elements for the line, and then computing geometric features of the line as it passes through each of the elements/nodes in the computed sequence. For each element/node that is required to be traversed by a lineset. Two control points may be computed with continuous second and first order derivative constraints. Elements/nodes on a lineset are represented as circles or other shapes or symbols. At step  196 , the graphic linesets and nodes are displayed on a computer display, perhaps for interactive manipulation, selection, etc. In one embodiment, nodes are displayed before any lines are displayed, and lines are then displayed such that they connect with the nodes; some nodes are displayed without any connecting lines. 
         [0029]      FIGS. 7 and 8  shows example linesets computed in this manner.  FIG. 7  shows linesets  200  used in a mapping application. A map  200  is displayed with linesets  200  superimposed thereon. Note that different linesets may visually cross at points where there is not a common node. However, logical intersections due to a shared node are shown by nodes such as node  204 , which indicate which linesets  200  are intersecting; example intersection  206  shows a dashed, thin, and thick lineset and overlapping/merged nodes  204 .  FIG. 8  shows a social network  220 . In this example, nodes are arranged by computing locations with a layout algorithm; a known algorithm that takes a graph of data and determines positions of the nodes of the graph. With a layout computed, a user may interactively define two sets of the person nodes (e.g., by inputting two set definitions such as “persons who work for Company” and “persons in Contact book”). The lineset process then computes lines for the sets. 
         [0030]    Among the factors that may be used to affect the shape of a set representation line, one is the possibility of adjusting the spatial layout of the data elements. While the locations of points of interest on a map should not be modified to improve the representation of the existing sets, when representing non-spatial data such as the social network  220  depicted in  FIG. 8 , the nodes&#39; positions can be adjusted to improve the appearance of the linesets. 
         [0031]      FIG. 9  shows an interactive interface  238  for exploring a restaurant dataset. A map  240  is displayed and a dataset of current data elements to be operated on is defined, for example, by automatically selecting all of a relevant data type corresponding to the currently viewed area. In this example, records of restaurants whose locations are in the map area shown in the display area serve as the base dataset. A user may indicate, via category indicators  242 , properties of sets that are to be formed and displayed. In the example, restaurant type, price, and rating are to be used as set-defining properties of the data elements (restaurant records). If a user activates the “Italian” category indicator  242 , any restaurants that are Italian are grouped into a set and a lineset is drawn to interconnect them. Colors of the category indicators  242  may correspond to colors of the linesets. Sets may be merged by interactively combining category indicators  242 . In one embodiment, each lineset is represented by a user interface element. The user interface elements can be used to display and undisplay linesets, merge linesets, etc. As set criteria is interactively modified and set membership changes, the linesets may also be updated; new nodes are added or removed, new overlapping node intersections are displayed, and so forth. 
         [0032]      FIG. 10  shows a list interface  250  that can be included with interactive interface  238 . The list interface  250 , which may be scrollable, shows the currently active sets, their members and their relationships in an order corresponding to their linesets. Nodes may be labeled, and any relevant properties listed along with a key indicating the appearance of a corresponding lineset. 
         [0033]    In one embodiment, linesets may have a selected and deselected state. In a deselected state, a lineset is shown as a thin line to reduce clutter on the display. When a lineset becomes selected, e.g., by a user clicking over it, it grows in width compared with unselected linesets. Elements may also be visually emphasized as a user selects them. Individual nodes/elements may also be selected to enable additional filtering. 
         [0034]    While two-dimensional examples have been discussed above, the same techniques may be used in three dimensional embodiments, whether in the form of three-dimensional displays or in the form of two-dimensional renderings of three-dimensional linesets. 
         [0035]    In another embodiment, users are allowed to interactively manipulate the positions of the graphic nodes attached to linesets. The algorithm used to compute the graphic lines is re-executed to re-computed new graphic lines based on the changed positions. Even if only one node is moved, a global re-computation may result in substantial changes in lineset shapes and orders of element visitation. 
         [0036]      FIG. 11  shows an example computer  270 . The computer  270  has a processor  272 , storage  274  (volatile/non-volatile), and a display  276  for displaying various graphics as discussed above. A network may also be used to obtain datasets, maps, etc., from a server. 
       CONCLUSION 
       [0037]    Embodiments and features discussed above can be realized in the form of information stored in volatile or non-volatile computer or device readable media. This is deemed to include at least media such as optical storage (e.g., compact-disk read-only memory (CD-ROM)), magnetic media, flash read-only memory (ROM), or any current or future means of storing digital information. The stored information can be in the form of machine executable instructions (e.g., compiled executable binary code), source code, bytecode, or any other information that can be used to enable or configure computing devices to perform the various embodiments discussed above. This is also deemed to include at least volatile memory such as random-access memory (RAM) and/or virtual memory storing information such as central processing unit (CPU) instructions during execution of a program carrying out an embodiment, as well as non-volatile media storing information that allows a program or executable to be loaded and executed. The embodiments and features can be performed on any type of computing device, including portable devices, workstations, servers, mobile wireless devices, and so on.