2016 · 116 citations · 42 references
ComputingVisualizationData VisualizationInteractive VisualizationVisual AnalyticsHigh-dimensional Data VisualizationInteractive Data AnalysisInteractive Data ExplorationVisual Data ExplorationAggregation QueriesData Reduction For VisualizationOverhead ReductionSampling-based VisualizationScatter PlotsStratified SamplingUser Study EvaluationVisual Fidelity
Interactive visualizations are crucial in ad hoc data exploration and analysis. However, with the growing number of massive datasets, generating visualizations in interactive timescales is increasingly challenging. One approach for improving the speed of the visualization tool is via data reduction in order to reduce the computational overhead, but at a potential cost in visualization accuracy. Common data reduction techniques, such as uniform and stratified sampling, do not exploit the fact that the sampled tuples will be transformed into a visualization for human consumption. We propose a visualization-aware sampling (VAS) that guarantees high quality visualizations with a small subset of the entire dataset. We validate our method when applied to scatter and map plots for three common visualization goals: regression, density estimation, and clustering. The key to our sampling method's success is in choosing a set of tuples that minimizes a visualization-inspired loss function. While existing sampling approaches minimize the error of aggregation queries, we focus on a loss function that maximizes the visual fidelity of scatter plots. Our user study confirms that our proposed loss function correlates strongly with user success in using the resulting visualizations. Our experiments show that (i) VAS improves user's success by up to 35% in various visualization tasks, and (ii) VAS can achieve a required visualization quality up to 400× faster.
42
Multidimensional binary search trees used for associative searching
Jon Bentley · Communications of the ACM · 1975 · 7.5K citations · Full text
É. A. Nadaraya · Theory of Probability and Its Applications · 1964 · 3.4K citations