PaperlayerView exact revision on arXiv

Source-linked AI summary

Visualization-Aware Sampling for Very Large Databases

Yongjoo Park, Michael Cafarella, Barzan Mozafari

arXiv:1510.03921v2cs.DB

TL;DR

Large datasets make interactive visualization slow, and common sampling approaches can miss sparse features. VAS selects data using a visualization-oriented objective; its samples were more useful across three tasks and could match quality with far fewer points.

  • Problem

    Reducing data can speed visualization but risks losing quality, and uniform or stratified sampling can miss sparsely represented features.

    Source: §I · p. 1

  • Method

    VAS selects a sample using a visualization-oriented metric for scatter and map plots, with sample size tied to a specified time bound.

    Source: §I · p. 2

  • Results

    VAS outputs were substantially more useful across regression, density estimation, and clustering at the same sample size, and could match competing quality with up to 400× fewer data points.

    Source: §I · p. 2, §VIII · p. 12

  • Takeaways & Limitations

    A small subset can yield fast, high-quality scatter or map plots, and the user study found VAS outputs more useful than other sampling methods at the same sample size.

    Source: §VIII · pp. 11–12

    The paper’s scope is scatter and map plots; other visualization goals and data types are left for future investigation.

    Source: §VIII · p. 12

Abstract

from arXiv · show

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 tuples which minimize a visualization-inspired loss function. Our user study confirms that optimizing this loss function correlates strongly with user success in using the resulting visualizations. We also show the NP-hardness of our optimization problem and propose an efficient approximation algorithm. Our experiments show that, compared to previous methods, (i) using the same sample size, 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 times faster.

I. INTRODUCTION

Large datasets make interactive visualization slow, while common sampling methods can miss sparsely represented features. The paper introduces VAS, which selects samples using a visualization-oriented metric for scatter and map plots.

I. INTRODUCTION

  • Tableau takes over four minutes to generate a scatterplot from 50M in-memory tuples, far longer than the 500ms-to-2-second interactive target.The paper notes that dataset sizes are growing faster than Moore’s Law.Source: §I · p. 1
  • Uniform and stratified sampling can miss important features when those features are sparsely represented, despite their common use in approximate query processing.Reducing data can lower CPU, I/O, and rendering work, but may reduce visualization quality.Source: §I · pp. 1–2
  • VAS targets high-fidelity scatter and map plots at arbitrary zoom levels by choosing tuples with a visualization-oriented metric linked to user success.The method can be requested through visualization-tool queries, with sample size selected from a specified time bound.Source: §I · p. 2
  • VAS can match competing visualization quality with up to 400× fewer data points, or deliver higher quality with the same number of points.The Geolife example shows similar overview quality but richer information in VAS zoomed-in views.Source: §I · p. 2

A. Software Architecture Model

  • In the standard architecture, a visualization tool submits an SQL query to a remote RDBMS, receives records, and renders the resulting bitmap for the user.The user specifies database fields and ranges as well as image parameters such as plot type, axis labels, and color coding.Source: A. Software Architecture Model · p. 2

B. Data Sampling

The paper frames sampling as a tradeoff between visualization fidelity and runtime, and targets scatterplots and map plots for regression, density estimation, and clustering. VAS uses a visualization-specific metric and an offline-preprocessing/query-time sampling workflow.

B. Data Sampling

  • Sampling reduces query work by running visualization queries over smaller derived tables, with sample size trading output fidelity against runtime.Samples are typically created and stored offline for repeated interactive queries.Source: B. Data Sampling · p. 3

C. Visualization Quality

  • Bar charts, line charts, and choropleths are among the visualization types left for future work.Source: C. Visualization Quality · p. 3
  • The authors make no claim for pattern finding or outlier detection, reserving those goals for future work despite anecdotal evidence of possible capability.Source: C. Visualization Quality · p. 3
  • The target goals are regression, density estimation, and clustering, while shape visualization, classification, hierarchy understanding, and network community detection are out of scope.Regression estimates dependent values, density estimation examines data distribution, and clustering assigns nearby elements to groups.Source: C. Visualization Quality · p. 3

D. Our Approach

  • The method proceeds through offline sample preprocessing followed by query-time selection of a sample sized for the specific query.VAS is described as a specialized index for visualization workloads that requires indexed-column choices and upfront computation.Source: D. Our Approach · p. 3
  • VAS requires frequently visualized column pairs rather than groups or filters; cited traces report 80–90% of exploratory queries use 5–10% of column combinations.The authors describe choosing frequently visualized columns as a simple approach that works reasonably well and can be resilient to workload changes.Source: D. Our Approach · p. 3
  • VAS generates samples according to a visualization-specific metric intended to support regression, density estimation, and clustering from few rendered points.The authors do not claim the method works for other visualization types or goals.Source: D. Our Approach · pp. 3–4

III. PROBLEM FORMULATION

VAS formulates sampling as minimizing a visualization-driven loss over a fixed-size sample. The loss reflects how well sampled points represent locations across the plotted space, and the resulting objective uses pairwise proximity.

III. PROBLEM FORMULATION

  • The loss at a location is lower when sampled points lie at or near it, while adding points where many already exist brings little improvement.The proximity function κ captures how near a sampled point is to the location; the paper uses a decreasing convex function.Source: §III · p. 4
  • Integrating pointwise loss over the plotted 2D space yields a global objective, and a second-order Taylor expansion makes the problem more tractable.The exact integral would require computationally expensive methods such as a large Monte Carlo experiment.Source: §III · p. 4
  • The VAS objective minimizes the sum of pairwise proximity terms among the selected points, using a proximity function in place of the integrated term.For the paper's exponential proximity function, the corresponding pairwise function has the same form with a rescaled denominator.Source: §III · p. 5
  • VAS seeks a fixed-size sample that minimizes visualization-quality loss across the space where the scatter or map plot is drawn.The sample size K is given as input, and the loss is designed to track visualization quality or utility from the user's perspective.Source: §III · pp. 4–5
  • VAS is NP-hard, so the paper presents an efficient approximation algorithm for finding samples that minimize this loss.Source: §III · p. 5

IV. SOLVING VAS

The VAS optimization problem is NP-hard, motivating an approximation algorithm. This section establishes the hardness through a polynomial-time reduction from maximum edge subgraph.

A. Hardness of VAS

  • VAS is NP-hard, as shown by a polynomial-time reduction from maximum edge subgraph.The reduction maps graph vertices to data points and transforms edge weights into pairwise proximity values.Source: A. Hardness of VAS · p. 5

IV. SOLVING VAS

  • Because exact VAS solutions are prohibitively slow, the paper presents an approximation algorithm and additional improvement ideas.The section introduces the algorithm as the practical response to the problem's hardness.Source: A. Hardness of VAS · p. 5, §IV · p. 5

B. The Interchange Algorithm

Interchange starts from a random sample and improves it by replacing points when doing so lowers the VAS objective. Responsibility-based Expand/Shrink updates make replacement tests efficient.

B. The Interchange Algorithm

  • Interchange scans the dataset from a random size-K sample, accepting replacements that reduce the optimization objective.It can be viewed as hill climbing over subsets of size K, where transitions exchange one selected point for another.Source: B. The Interchange Algorithm · p. 5
  • Responsibility lets Interchange test replacements without recomputing all pairwise proximity functions, reducing each candidate test from O(K^3) to O(K^2) computations.The responsibility of a new point is compared with that of each existing sample point.Source: B. The Interchange Algorithm · pp. 5–6
  • Expand inserts a candidate into a temporary size-(K+1) set, then Shrink removes the element with the largest responsibility.Theorem 2 states that this procedure replaces an existing point exactly when the replacement reduces the objective; otherwise the sample remains unchanged.Source: B. The Interchange Algorithm · p. 6
  • Scanning N points with Expand and Shrink takes O(NK) computations.Each routine updates element responsibilities in a single loop, taking O(K) computations per new point.Source: B. The Interchange Algorithm · p. 6
  • Theorem 3 gives an upper bound on Interchange's objective relative to the optimal sample, based on VAS submodularity.The proof applies a result of Nemhauser et al., with submodularity established in the technical report.Source: B. The Interchange Algorithm · p. 6
  • The authors report that a half-hour run already produces a high-quality sample, with quality continuing to improve until convergence when more time is allowed.The ideal stopping condition is that no further valid replacements are possible.Source: B. The Interchange Algorithm · p. 6

V. EXTENDING VAS: EMBEDDING DENSITY

VAS can be extended to represent density, which ordinary scatter plots may obscure when points are duplicates or very close together. The extension counts how many dataset points each sampled point represents.

V. EXTENDING VAS: EMBEDDING DENSITY

  • Dense regions can be hard to estimate visually because overlapping or near-duplicate points are difficult to distinguish.The extension encodes density through larger point sizes or jitter proportional to the original density of the represented region.Source: §V · p. 7
  • After obtaining a VAS sample, the method attaches a counter to each sampled point and increments it for each dataset point assigned to that sample point as nearest neighbor.The density calculation scans the dataset once more.Source: §V · p. 7
  • The counters can encode density through point size or jitter, while leaving the basic Interchange algorithm unchanged.The extension adds only a database column and requires no additional user information.Source: §V · p. 7
  • A k-d tree can accelerate the second-pass nearest-neighbor tests, yielding O(N log K) time.The tree is built from the sample obtained in the first pass.Source: §V · p. 7

VI. EXPERIMENTS

The experiments evaluate VAS and VAS with density embedding on plot quality, user success, sample efficiency, and the Interchange approximation algorithm.

VI. EXPERIMENTS

  • The experiments compare VAS and VAS with density embedding against competing methods across plot quality, runtime, and user-facing tasks.The evaluation includes a user study, fixed-quality sample comparisons, and tests of Interchange against the exact method.Source: §VI · p. 7
  • The evaluations use Geolife, a 24.4M-tuple GPS dataset, and a synthetic five-column SPLOM dataset with 1B tuples.Experiments ran on an Amazon EC2 r3.4xlarge instance with 16 cores and 122G memory.Source: §VI · p. 7

A. Existing Systems are Slow

Tests of Tableau and MathGL show that producing plots from large datasets exceeds interactive response times, with runtime increasing with sample size.

A. Existing Systems are Slow

  • The benchmark measured data loading and rendering in Tableau and MathGL on both Geolife and SPLOM.MathGL loaded data from SSD storage; Tableau loaded it from memory.Source: A. Existing Systems are Slow · p. 7
  • More than 2 seconds were required to visualize even 1M records, exceeding the stated interactive limit.Visualization time grew linearly with sample size.Source: A. Existing Systems are Slow · p. 7

B. User Success and Sample Quality

A user study tested regression, density estimation, and clustering with sampled visualizations. Results varied by task: VAS led in regression, while density embedding improved density and clustering performance over basic VAS.

B. User Success and Sample Quality

1) User Success:

  • VAS users achieved the highest regression accuracy, significantly outperforming the other sampling methods.Users estimated altitude at a marked location in Geolife visualizations; Table I(a) summarizes performance.Source: 1) User Success · p. 8, Table I · p. 8, Figure 5 · p. 8
  • In density estimation, VAS with density embedding outperformed uniform random sampling, while basic VAS performed very poorly.The task asked users to identify both densest and sparsest areas; uniform samples often had few points in sparse areas.Source: 1) User Success · pp. 8–9, Table I · p. 8, Figure 6 · p. 8
  • The clustering study used four synthetic Gaussian datasets because Geolife lacked clustering ground truth and SPLOM contained a single Gaussian cluster.The study tested samples from 100 to 100K tuples and asked users to identify the number of underlying clusters.Source: 1) User Success · p. 9
  • In clustering, VAS with density embedding improved user success over uniform random sampling, while VAS without density achieved a roughly comparable score.Stratified sampling performed poorly because within-bin samples tended to group together, leading users to infer too many clusters.Source: Table I · p. 8, 1) User Success · p. 9

2) Correlation with Sample Quality:

The paper tests whether its loss metric predicts user success in regression visualizations. Lower loss was strongly associated with better user performance, supporting the metric as an indicator of sample quality.

2) Correlation with Sample Quality:

  • For the regression analysis, the authors approximated the loss integral using 1,000 random domain points and used the median because extreme point-loss values exceeded double precision.The median was considered valid for correlation analysis because the authors observed no reversal between mean and median sample rankings.Source: 2) Correlation with Sample Quality · p. 9
  • Samples with log-loss-ratios close to zero are considered good because Loss(D) represents the lowest loss attainable by a sample.D denotes the original dataset.Source: 2) Correlation with Sample Quality · p. 9
  • Figure 7 shows that lower loss corresponds to higher success ratios in the regression task.The study compared log-loss-ratio rankings with the percentage of correctly answered questions for each visualization.Source: 2) Correlation with Sample Quality · p. 9, Figure 7 · p. 9
  • −0.85 was the Spearman rank correlation between user success and log-loss-ratio, with p-value 5.2 × 10^-4.The authors report a strong negative correlation, consistent with higher user success for samples with lower loss.Source: 2) Correlation with Sample Quality · pp. 9–10, Figure 7 · p. 9

C. VAS Uses a Smaller Sample

VAS produces lower-loss visualizations than competing sampling methods across tested runtime settings, and its optimization improves sample quality quickly before gains slow. The algorithmic results show that exact solutions are costly and that the fastest optimization setting depends on sample size.

C. VAS Uses a Smaller Sample

  • VAS had lower loss than competing methods across tested Geolife runtimes, while competitors needed much more time to reach the same quality.The quality gap persisted until after an entire minute of runtime.Source: C. VAS Uses a Smaller Sample · p. 10

D. Algorithmic Details

  • VAS’s NP-hardness motivates an approximation algorithm, while the exact-solution comparison illustrates why exact optimization is impractical beyond very small datasets.The exact approach was formulated as a mixed-integer program and solved with GLPK.Source: D. Algorithmic Details · p. 10
  • At N = 80, obtaining an exact VAS solution took more than 40 minutes; exact solutions had better quality but were feasible only for extremely small datasets.The comparison fixed K at 10; the table reports the loss and runtime comparison.Source: D. Algorithmic Details · p. 10, Table II · p. 10
  • The Interchange algorithm improved visualization quality quickly at first, then more slowly, producing low-error plots within tens of minutes with O(K) storage.K is the sample size.Source: D. Algorithmic Details · p. 11
  • Expand/Shrink was fastest at sample size 100, whereas ES+Loc was fastest at 5K and is preferable for samples above 10K.ES reduces time complexity by O(K); ES+Loc adds an R-tree to exploit loss-function locality, whose overhead can hurt at small sample sizes.Source: D. Algorithmic Details · p. 11, Figure 10 · p. 11

VII. RELATED WORK

Related approaches include sampling, binning, parallel rendering, and incremental visualization, with several described as orthogonal to VAS. The conclusion reports greater usefulness for VAS samples across three user goals and identifies other goals and data types for future investigation.

VII. RELATED WORK

  • Prior approaches include ScalaR’s random sampling, binned aggregation, parallel rendering, and incremental refinement; the paper describes several as orthogonal to VAS.ScalaR dynamically inserts aggregation, sampling, or filtering; incremental visualization progressively refines an initial low-resolution image.Source: §VII · p. 11
  • Binned aggregation fixes bins in advance, limiting flexibility for changing data and forcing a choice between zoom performance and low-resolution results.Smoothing can address variability in small bins but may make results unsuitable for outlier finding; the paper describes smoothing as orthogonal to VAS.Source: §VII · p. 11

VIII. CONCLUSIONS AND FUTURE WORK

  • For regression, density estimation, and clustering, VAS outputs were substantially more useful than other sampling methods’ outputs at the same tuple count.The authors plan to investigate other goals, including outlier detection and trend identification, and other data types such as large networks.Source: §VIII · p. 12
Loading 1510.03921v2…