Rapid Sampling for Visualizations with Ordering Guarantees

1. INTRODUCTION

• The algorithms target rapid approximate visualizations of large datasets, with tuning parameters that let users trade accuracy for interactivity.The focus is on visualizations corresponding directly to SQL aggregation queries, such as bar charts and histograms.Source: §1 · pp. 1–2
• The techniques also extend to other visual properties, including accurate trends and bounded-error values, and to other visualization types.The paper names trend-lines and choropleth maps as examples of other visualization types.Source: Figure 1 · p. 1, §1 · p. 2
• The challenge is to meet visual ordering guarantees with as few samples as possible, since round-robin sampling can do more work than necessary.Sampling groups whose confidence intervals overlap can resolve ambiguous comparisons, while further sampling a group already clearly largest adds no ordering information.Source: §1 · pp. 1–2, Figure 2 · p. 2
• The sampling algorithms are theoretically optimal: no other algorithms can use substantially fewer samples.The paper develops a family of algorithms based on sound probabilistic principles.Source: §1 · p. 2
• Up to 50X fewer samples than conventional schemes are needed in the experiments, while the algorithms preserve correct visual properties.The algorithms return correctly ordered estimates with probability greater than a user-specified threshold, independent of the data distribution.Source: §1 · p. 2
• The methods do not currently apply to scatter-plots, stacked charts, timelines, or treemaps.The stated focus is on visualization types that directly correspond to SQL aggregation queries.Source: §1 · p. 2

1. Partial Results:

• Analysts can receive partial results as they are computed and peruse them immediately while the visualization improves over time.The algorithms can also terminate early by using finite display resolution or by allowing mistakes on a few groups.Source: §1 · p. 2
• The algorithms generalize beyond AVG to other aggregation functions, more complex queries, and more general settings.Source: §1 · p. 2
• The algorithms can generate visualization types beyond bar graphs, including trend-lines and choropleth maps.Source: §1 · p. 2

2.1 Visualization Setting

• For a GROUP BY X and AVG(Y) query, the visualization places X on the x-axis and group averages on the y-axis.The setting assumes random samples can be retrieved from each group and bounded values, though the algorithms can still be used without a known bound.Source: §2.1 · p. 2, §2.2 · p. 2

2.2 Query Processing

• The query processor repeatedly samples groups and returns estimates whose ordering should match the true averages; Table 1 marks active and inactive groups as A and I.The ordering guarantee allows failure probability δ.Source: §2.2 · pp. 2–3, Table 1 · p. 3

2.3 Characterizing Performance

• Performance is characterized by total samples, algorithm computation time, and experimentally measured wall-clock time.Sample complexity sums samples across groups, assuming equal cost per sample.Source: §2.3 · p. 3

2.4 Formal Problem

• AVG-ORDER seeks estimates with the same ordering as the true group averages with probability greater than 1 − δ, while minimizing sample complexity.The problem also seeks relatively small computational complexity.Source: §2.4 · p. 3
• AVG-ORDER-RESOLUTION relaxes ordering requirements for pairs whose true averages differ by at most a user-specified resolution r.Pairs farther apart must retain their correct ordering, with probability greater than 1 − δ.Source: §2.4 · p. 3

2.5 Extensions

• Other variants address adjacent-group ordering for trends and heat maps, top-t or bottom-t groups, tolerated mistakes, stronger value guarantees, and partial results.Source: §2.5 · p. 3
• The techniques extend to predicates, multiple group-by attributes, multiple aggregates, no-index settings, and aggregates such as SUM and COUNT.Source: §2.5 · p. 3

3.1 The Basic IFOCUS Algorithm

• IFOCUS samples every group initially, then takes one additional sample per round only from groups with overlapping confidence intervals, stopping when none overlap.The intervals are updated using the sample count and a half-width derived from a variation of Hoeffding’s inequality; sample complexity does not depend on group size.Source: §3.1 · p. 4

3.2 Proof of Correctness

• With probability at least 1 − δ, IFOCUS returns estimates in the same order as the groups’ true averages.The proof combines confidence intervals that contain active groups’ true averages with the fact that disjoint intervals preserve their ordering.Source: §3.2 · pp. 5–6

3.3 Sample Complexity of IFOCUS

• IFOCUS’s sample complexity scales with the sum of inverse squared nearest-neighbor gaps η_i, so more closely spaced group averages require more sampling.With probability at least 1 − δ, the estimates satisfy the ordering guarantee while the algorithm draws the theorem-bounded total number of samples.Source: §3.3 · p. 6

3.4 Computational Complexity

• Maintaining a binary search tree lets IFOCUS check whether a group remains active in O(log |A|) time per round, or O(k log k) across active groups.For typical small k, the paper notes that taking another sample can dominate the cost of checking activity.Source: §3.4 · p. 6

3.5 Lower bounds on Sample Complexity

• IFOCUS’s sample complexity is optimal up to constant multiplicative factors and a small additive term, as its bound nearly matches a lower bound for any correct-ordering algorithm.The lower bound applies to algorithms that satisfy the correct-ordering condition with probability at least 1 − δ.Source: §3.5 · p. 6
• 3.5 Lower bounds on Sample Complexity: Any algorithm estimating µ_i within ±ε with confidence 1−δ must sample at least 1/(8ε^2) ln(1/(16e√πδ)) elements from S_i in expectation.The same lower bound applies when distinguishing the promised cases µ_i ∈ {1/2−ε, 1/2+ε}.Source: §3.5 · pp. 6–7

3.6 Discussion

• 3.6 Discussion: With replacement, IFOCUS can use Hoeffding’s inequality and omit group sizes, while sampling without replacement has smaller sample complexity.The replacement variant removes the finite-population correction from its confidence interval calculation.Source: §3.6 · p. 7
• 3.6 Discussion: For ordering only groups whose means differ by more than threshold r, the algorithm can stop when ε_m < r/4 and replace each η_i with max{η_i,r}.The variant’s sample complexity is essentially that of Theorem 3.6, apart from constant factors.Source: §3.6 · p. 7
• 3.6 Discussion: IREFINE maintains confidence intervals and refines them aggressively, but has less desirable sample complexity than IFOCUS and is not optimal.It stops refining an estimate when its interval is disjoint from the others; the analysis bounds its samples per group by O(log(k/δ) log(1/η_i)).Source: §3.6 · pp. 7–8

4. SYSTEM DESCRIPTION

• NEEDLETAIL is designed to produce random samples of records matching ad-hoc conditions.It uses in-memory bitmap-based indexes to retrieve satisfying tuples.Source: §4 · p. 8
• Bitmap indexes record tuple matches for attribute values and can be compressed to store them compactly in memory.NEEDLETAIL also uses other optimizations to store and operate on the indexes.Source: §4 · p. 8
• The evaluation uses NEEDLETAIL in row-store mode to eliminate gains originating from column-store configuration.The indexes are organized hierarchically; retrieval time is described as logarithmic in the number of records, or tree depth.Source: §4 · p. 8

5.1 Experimental Setup

• Experiments used a single-threaded, early-stage NEEDLETAIL prototype, measuring CPU and I/O separately against sequential SCAN; the authors expected optimization and parallelization to improve runtime further.The prototype ran on a 64-core server, but all experiments were single-threaded and used Direct I/O.Source: §5.1 · p. 9

5. EXPERIMENTS

• Across large synthetic datasets, IFOCUS and IFOCUSR reduce samples by up to 80% and 98%, and runtime by up to 79% and 92%, respectively, versus ROUNDROBIN on average.On the flight-record dataset, the reported runtime reductions are up to 70% and 85%, respectively.Source: §5.1 · p. 9

5.2 Synthetic Experiments

• For 10^9 synthetic records, IFOCUS and IFOCUSR finish in 3.9 and 0.37 seconds, versus 89 seconds for SCAN; at 10^10 records, IFOCUSR takes 0.78 seconds versus SCAN’s 898 seconds.The paper attributes the sampling methods’ sublinear runtime growth to their sample complexities, while SCAN scales linearly.Source: Figure 4 · p. 9, §5.2 · p. 10
• All six algorithms achieved 100% ordering accuracy across tested datasets, but shrinking confidence intervals faster than prescribed caused errors, exceeding 2–3% even at heuristic factor 2.In the hard case, sampling just 1% less reduced accuracy below 95%, and sampling 20% less reduced it below 70%.Source: §5.2 · p. 11
• IFOCUS quickly narrows sampling to a few active groups: after 1M samples in a 10M-record dataset, an average of 2 of 10 groups remained active, while incorrect pairs stayed near zero.Some incorrect pairs persisted through 3M samples, so the current estimates could support incremental, though not necessarily fully correct, visualizations.Source: §5.2 · p. 11, Figure 6 · p. 12
• Sampling increased with group count and dataset difficulty, yet IFOCUSR’s share rose from under 10% at 5 groups to nearly 40% at 50; its gains persisted under 90% skew, while higher standard deviations changed sampling by less than 1–2%.The reported average difficulty increased four orders of magnitude, from 10^4 at 5 groups to 10^8 at 50 groups.Source: §5.2 · pp. 11–12

5.3 Real Dataset Experiments

• On flight records [20], IFOCUS and IFOCUSR were faster than ROUNDROBIN for averages of three airline-grouped attributes, with elapsed-time runtimes of 9.70 and 5.04 seconds versus 32.6 seconds.The runtimes roughly doubled when dataset size increased 100×, as sampling increased for groups with closely spaced means; all returned orderings were correct.Source: §5.3 · p. 12
• Up to 6× runtime speedup over round-robin was achieved on a real dataset; greater speedups were possible by tolerating a higher minimum resolution.Source: §5.3 · p. 12

• Figure 7 examines sampling as the first group's proportion and the standard deviation for truncnorm vary.Source: Figure 7 · p. 13
• Table 3 presents real-data experiments.Source: Table 3 · p. 13
• The section presents algorithm variations for stronger or weaker conditions and other queries or settings.Source: §6 · p. 13

6.1.1 Trends and Chloropleths

• For trends and choropleths, IFOCUS samples groups whose confidence intervals overlap those of neighboring or nearby groups.For trends, the ordering guarantee applies to consecutive groups; for choropleths, it can apply to adjacent or nearby regions.Source: §6.1.1 · p. 13

6.1.2 Top-t Results

• For top-t results, groups remain active only while their intervals overlap and their membership in the top-t is uncertain.Groups known not to belong to the top-t are removed; the approach guarantees correctness with probability greater than 1 −δ.Source: §6.1.2 · p. 13

6.1.3 Allowing Mistakes

• When allowing errors on γ% of comparisons, the modified IFOCUS stops once it knows the ordering for the desired fraction γ.The guarantee requires correct ordering for at least a γ fraction of pairs, with probability greater than 1 −δ.Source: §6.1.3 · pp. 13–14

6.2.1 Approximate Actual Values

• For approximate actual values, IFOCUS first samples until ε ≥ d/2, then proceeds with η_i replaced by min{η_i, d/2}.The target combines correct ordering with an absolute error bound of d for every group.Source: §6.2.1 · p. 14

6.2.2 Partial Results

• For partial results, estimates are output as groups become inactive, with correct ordering among all groups output at any stage.The stated sample complexity to output the first k′ groups depends on the smallest η_i among those groups.Source: §6.2.1 · p. 14

6.3.1 Different Aggregation Functions: SUM

• For SUM with known group sizes, sum and average are related by σ_i = μ_i ⋅ |S_i|, and confidence-interval updates scale by group size.With unknown sizes, the method estimates group fractions and averages together using unbiased samples of x ⋅ z; equal-sized groups can require roughly k^2 times as many samples for normalized sums.Source: §6.3.1 · pp. 14–15

6.3.2 Different Aggregation Functions: COUNT

• For COUNT with unknown group sizes but known total size, the SUM approach estimates group fractions s_i instead of normalized sums.Source: §6.3.2 · p. 15

6.3.3 Selection Predicates

• Selection predicates are supported when an index on the group-by attribute lets the system retrieve qualifying tuples from each group.Source: §6.3.3 · p. 15

6.3.4 Multiple Group-bys

• For multiple group-bys, the algorithms work with a joint index or an index on either attribute, though a single-attribute index may increase sample complexity.Source: §6.3.4 · p. 15

6.3.5 Multiple Aggregates Visualized

• For multiple aggregates, IFOCUS processes one aggregate while estimating the other, then processes the second with δ split between them.The worst-case sample complexity is the sum of running both independently, but the second run may need fewer samples because it starts with existing estimates.Source: §6.3.5 · p. 15

6.3.6 No Indexes

• Without an index on the group-by attribute, the algorithm samples randomly across groups and uses Hoeffding’s inequality to decide when to stop.For groups of roughly equal size, performance is similar to round robin, though poorer than IFOCUS.Source: §6.3.6 · p. 15

Approximate Query Processing

• Online aggregation leaves users to decide when group confidence is sufficient, whereas IFOCUS automatically stops sampling to preserve visualization ordering.The authors also say automatic stopping can prevent users from stopping too early or doing extra work by stopping too late.Source: §7 · p. 16
• Prior online query-processing methods target objectives unlike relative ordering, and the paper reports that round-robin stratified sampling uses more samples than its techniques.The authors also state that uniform random sampling is strictly worse than round-robin stratified sampling, or equal in the best case.Source: §7 · p. 16
• For ad-hoc visualizations, the paper assumes no precomputed sample and no known group variances, making round-robin stratified sampling an appropriate baseline.Offline samples are typically chosen in advance for a workload; Neyman Allocation requires variance information that is unavailable here.Source: §7 · p. 16

Statistical Tests and Noisy Sorting

• Statistical tests and noisy-sorting methods do not directly fit this setting, where sampling a group informs multiple comparisons.The paper says sampling decisions must be made across sets without directly requesting pairwise comparisons.Source: §7 · p. 16

Visualization Tools and Scalable Visualization

• Precomputed cubes and image tiles support some scalable visualizations, but ad-hoc queries may not fit those approaches; other scalability techniques are orthogonal to online computation of one visualization.The paper also notes that visualization tools could benefit from its algorithms, while prior user studies support analyst acceptance of uncertain visualizations with error bars.Source: §7 · p. 16

8. CONCLUSIONS

• On datasets with 10^10 tuples, the methods preserve visual properties while querying less than 0.02% of the data, achieving over 60× speedup over ROUNDROBIN and 1000× over full-data visualization.The comparison is with schemes providing similar guarantees for ROUNDROBIN and with generating the visualization on the entire database.Source: §8 · p. 16