Optimizing and Simplifying Rendering of Data Points in a Visualization

Abstract

A computing device executing a browser application obtains a dataset for rendering a data visualization, the dataset including a plurality of data points. The device selects, from the plurality of data points, a first subset of data points according to a statistical data distribution of the dataset. The device recursively applies a first algorithm to the first subset of data points to obtain a final subset of data points. Each of first subset of data points and the final subset of data points has a fewer number of data points than the plurality of data points. The device renders a data visualization using the browser application. The data visualization has a plurality of data marks corresponding to the final subset of data points. The device displays, on the browser application, the data visualization including the plurality of data marks.

What is claimed is: 
     
         1 . A method for visualizing large datasets, performed by a computing device executing a browser application, the method comprising:
 obtaining a dataset for rendering a data visualization, the dataset including a plurality of data points;   selecting, from the plurality of data points, a first subset of data points according to a statistical data distribution of the dataset;   recursively applying a first algorithm to the first subset of data points to obtain a final subset of data points, wherein each of first subset of data points and the final subset of data points has a fewer number of data points than the plurality of data points;   rendering a data visualization using the browser application, the data visualization having a plurality of data marks corresponding to the final subset of data points; and   displaying, on the browser application, the data visualization including the plurality of data marks.   
     
     
         2 . The method of  claim 1 , wherein recursively applying the first algorithm to the first subset of data points to obtain the final subset of data points includes:
 applying the first algorithm to the first subset of data points to obtain a second subset of data points;   dividing the second subset of data points into multiple data segments, each of the data segments including a respective third subset of data points; and   reapplying the first algorithm to a least a portion of each data segment, of the multiple data segments, to obtain a respective fourth subset of data points from the respective third subset of data points.   
     
     
         3 . The method of  claim 2 , wherein reapplying the first algorithm to the a least a portion of each data segment to obtain the respective fourth subset of data points:
 for each data segment:
 determining a respective tolerance value for the data segment according to characteristics of the respective fourth subset of data points; 
 in accordance with a determination that the respective fourth subset of data points satisfy the respective tolerance value:
 retaining the respective fourth subset of data points; and 
 including the respective fourth subset of data points in the final subset of final points; and 
 
 in accordance with a determination that the respective fourth subset of data points do not satisfy the respective tolerance value:
 dividing the data segment into one or more sub-segments; and 
 reapplying the first algorithm to each of the sub-segments. 
 
   
     
     
         4 . The method of  claim 2 , further comprising:
 generating a distinct computation pipeline for each data segment, of the multiple data segments, to independently process the data segment.   
     
     
         5 . The method of  claim 4 , further comprising:
 at a respective computation pipeline corresponding to a respective data segment:
 dividing the respective data segment into one or more data regions; and 
 for each data region:
 determining a value for a visual change parameter for the data visualization when data values of the data region are included an existing rendering of the data visualization; and 
 in accordance with a determination that the value for visual change parameter satisfies a threshold value:
 adding the data region to the at least a portion of each data segment; and 
 reapplying the first algorithm to the a least a portion of each data segment. 
 
 
   
     
     
         6 . The method of  claim 1 , further comprising:
 after obtaining the dataset:
 generating a data structure that includes a plurality of nodes; and 
 assigning each data point of the dataset to a respective node of the data structure according to a spatial location of the respective data point in the data visualization. 
   
     
     
         7 . The method of  claim 6 , further comprising storing each data point of the dataset in a binary data format in the data structure. 
     
     
         8 . The method of  claim 6 , wherein the data structure comprises a quadtree data structure. 
     
     
         9 . The method of  claim 6 , wherein:
 the data visualization occupies a spatial area; and   the method includes:
 partitioning the spatial area into four quadrants; and 
 for a respective quadrant:
 recursively partitioning the quadrant to sub-quadrants in accordance with a determination that a first set of criteria is satisfied; and 
 assigning a respective data point to a respective sub-quadrant according to respective coordinates of the data point. 
 
   
     
     
         10 . The method of  claim 9 , wherein the first set of criteria includes a criterion that a number of data points corresponding to the respective quadrant exceeds a threshold number of data points. 
     
     
         11 . The method of  claim 6 , further comprising:
 after displaying, on the browser application, the data visualization:
 receiving user selection of a first region of the data visualization, the first region including at least one data mark of the plurality of data marks; and 
 in response to receiving the user selection of the first region of the data visualization:
 identifying a first node, in the data structure, corresponding to the first region of the data visualization; 
 in accordance with a determination that the first node includes one or more data points that are excluded from the final subset of data points:
 re-rendering the first region of the data visualization to include one or more additional data marks, corresponding to the one or more data points; and 
 displaying the re-rendered first region of the data visualization. 
 
 
   
     
     
         12 . The method of  claim 1 , further comprising:
 after obtaining the dataset and prior to selecting the first subset of data points:
 performing initial data cleaning and transformation. 
   
     
     
         13 . The method of  claim 1 , further comprising:
 after obtaining the dataset and prior to selecting the first subset of data points:
 performing feature extraction on the dataset to identify, from the plurality of data points, an initial subset of data points that retains a visual perception of the data visualization. 
   
     
     
         14 . The method of  claim 1 , wherein the selecting the first subset of data points is further based on a data mark encoding type of the data visualization. 
     
     
         15 . The method of  claim 1 , wherein selecting, from the plurality of data points, the first subset of data points according to the data distribution of the dataset includes:
 applying a machine learning model to determine, from the statistical data distribution, the first subset of data points such that the first subset of data points preserves a visual perception of the data visualization.   
     
     
         16 . The method of  claim 1 , wherein selecting, from the plurality of data points, the first subset of data points according to the data distribution of the dataset includes:
 applying a machine learning model to determine, from the statistical data distribution, a second subset of data points from the plurality of data points; and   performing a filtering or grouping operation on each data point of the second subset of data points.   
     
     
         17 . The method of  claim 1 , wherein the first subset of data points is selected further based on a chart type of the data visualization. 
     
     
         18 . The method of  claim 1 , wherein the data visualization is a Sankey chart, a tree map, a stacked bar graph, a scatter plot, or a line chart. 
     
     
         19 . A computing device executing a browser application, comprising:
 a display;   one or more processors; and   memory coupled to the one or more processors, the memory storing one or more programs configured for execution by the one or more processors, the one or more programs including instructions for:
 obtaining a dataset for rendering a data visualization, the dataset including a plurality of data points; 
 selecting, from the plurality of data points, a first subset of data points according to a statistical data distribution of the dataset; 
 recursively applying a first algorithm to the first subset of data points to obtain a final subset of data points, wherein each of first subset of data points and the final subset of data points has a fewer number of data points than the plurality of data points; 
 rendering a data visualization using the browser application, the data visualization having a plurality of data marks corresponding to the final subset of data points; and 
 displaying, on the browser application, the data visualization including the plurality of data marks. 
   
     
     
         20 . A non-transitory computer-readable storage medium storing one or more programs configured for execution by one or more processors of a computing device executing a browser application, the one or more programs comprising instructions for:
 obtaining a dataset for rendering a data visualization, the dataset including a plurality of data points;   selecting, from the plurality of data points, a first subset of data points according to a statistical data distribution of the dataset;   recursively applying a first algorithm to the first subset of data points to obtain a final subset of data points, wherein each of first subset of data points and the final subset of data points has a fewer number of data points than the plurality of data points;   rendering a data visualization using the browser application, the data visualization having a plurality of data marks corresponding to the final subset of data points; and   displaying, on the browser application, the data visualization including the plurality of data marks.