STULL: Unbiased Online Sampling for Visual Exploration of Large Spatiotemporal Data

Guizhen Wang, Jingjing Guo, Mingjie Tang, José Florencio de Queiroz Neto, Calvin Yau, Anas Daghistani, Morteza Karimzadeh, Walid G. Aref, David S. Ebert

TL;DR

This paper introduces STULL, a novel method for unbiased online sampling of large spatiotemporal datasets. By ensuring every data point has an equal chance of being selected, STULL enables more accurate and visually representative interactive explorations compared to existing biased methods, without sacrificing performance.

What Problem Does This Paper Address?

Visual analytics (VA) systems often struggle with the sheer volume of large datasets, making it impossible to display everything at once. Online sampling offers a solution by progressively retrieving and visualizing subsets of data, allowing users to explore interactively. However, many existing sampling techniques are biased. This means they don't select data points uniformly, leading to distorted representations of the underlying data. For spatiotemporal data (data with both location and time components), this bias can result in incorrect interpretations of patterns, hotspots, and trends, ultimately hindering effective decision-making. The core challenge is to achieve unbiased sampling that is both computationally efficient for interactive use and accurately reflects the true data distribution.

Methods

STULL tackles the problem of biased sampling by introducing a novel data index and a carefully designed sample retrieval plan. The key innovation lies in its "proportionally-sized" sample buffer design within a hierarchical index structure (pyramids).

  • Hierarchical Indexing: Data is first organized into temporal bins. Within each bin, a pyramid structure (similar to a quadtree but with modifications) is used to spatially segment the data.
  • Proportionally-Sized Sample Buffers: Unlike previous methods that used fixed-size buffers, STULL's non-leaf nodes in the pyramid store sample buffers whose size is proportional to the data volume they represent. This ensures that when data is aggregated from multiple nodes, the resulting sample accurately reflects the overall distribution.
  • Unbiased Retrieval: The sample retrieval process is designed to guarantee that each data point satisfying a user's query has an equal probability of being selected. This is achieved through a systematic traversal of the pyramid structure and careful selection from the proportionally-sized buffers.
  • Online and Incremental: STULL is designed for online use, meaning it can process incoming data streams and respond to queries in real-time. It also supports incremental updates, allowing visualizations to be refined as more samples are retrieved.

Datasets

The paper evaluates STULL using four real-world datasets:

  • GEO: Human movement data from April 2011 to August 2013, covering Beijing, China.
  • OSP: Ohio highway traffic incident data from January 2012 to December 2013.
  • Tweet-Chicago: Tweets collected in Chicago from April 2013 to September 2013.
  • Tweet-US: Tweets collected across the entire US from January 2018 to March 2018.

These datasets vary in their spatial distribution (concentrated vs. scattered hotspots) and temporal granularity, allowing for a comprehensive evaluation of STULL's performance.

Key Insights and Ideas

  • Bias is a Major Hurdle: The paper strongly emphasizes that biased sampling, even if fast, can lead to fundamentally incorrect interpretations, undermining the purpose of visual analytics.
  • Proportionality is Key to Unbiasedness: The core insight is that sample buffer sizes must be proportional to the data they represent to avoid bias. Fixed-size buffers, as used in prior work, can disproportionately favor certain regions or data characteristics.
  • Unbiasedness Doesn't Mean Slow: STULL demonstrates that achieving unbiased sampling doesn't require sacrificing performance. It achieves comparable or better speeds than existing methods while providing superior accuracy.
  • Visuals Matter: The paper highlights that unbiased sampling not only improves numerical accuracy but also leads to visualizations that more closely resemble the "exact" data, making them more trustworthy and easier to interpret.

Key Results

  • Numerical Accuracy: STULL improves approximate spatial accuracy by at least 50% compared to the state-of-the-art STORM approach when sampling 5% of the data. RMSE values are significantly lower, indicating closer approximations to the true data distribution.
  • Visual Accuracy: Heatmaps and pie charts generated by STULL are visually more similar to the exact representations than those produced by STORM, especially at smaller sample sizes. STULL's visualizations maintain consistency even as sample sizes increase.
  • Performance: STULL achieves competitive retrieval latencies, often outperforming baseline methods like RandomPath by significant margins (e.g., saving at least 60% of time for incremental updates). Its index creation and update times are also efficient.
  • Scalability: The approach is designed to handle large spatiotemporal datasets and streaming data effectively.

Limitations and Future Work

  • Storage Overhead: STULL's proportionally-sized sample buffers can lead to increased storage requirements compared to methods that don't duplicate data across levels.
  • Disk-Based Indexing: While the current implementation is efficient for in-memory data, the paper acknowledges that further work is needed to optimize STULL for disk-resident indexes, particularly concerning the management of variable-sized sample buffers and disk I/O.
  • Parallel Processing: The current retrieval scheme is sequential; exploring parallel processing for sample retrieval is suggested for further performance gains.

Summary updated

Abstract

Online sampling-supported visual analytics is increasingly important, as it allows users to explore large datasets with acceptable approximate answers at interactive rates. However, existing online spatiotemporal sampling techniques are often biased, as most researchers have primarily focused on reducing computational latency. Biased sampling approaches select data with unequal probabilities and produce results that do not match the exact data distribution, leading end users to incorrect interpretations. In this paper, we propose a novel approach to perform unbiased online sampling of large spatiotemporal data. The proposed approach ensures the same probability of selection to every point that qualifies the specifications of a user's multidimensional query. To achieve unbiased sampling for accurate representative interactive visualizations, we design a novel data index and an associated sample retrieval plan. Our proposed sampling approach is suitable for a wide variety of visual analytics tasks, e.g., tasks that run aggregate queries of spatiotemporal data. Extensive experiments confirm the superiority of our approach over a state-of-the-art spatial online sampling technique, demonstrating that within the same computational time, data samples generated in our approach are at least 50% more accurate in representing the actual spatial distribution of the data and enable approximate visualizations to present closer visual appearances to the exact ones.
BibTeX
@inproceedings{wang2020stull,
  author = {Guizhen Wang and Jingjing Guo and Mingjie Tang and José Florencio de Queiroz Neto and Calvin Yau and Anas Daghistani and Morteza Karimzadeh and Walid G. Aref and David S. Ebert},
  title = {{STULL: Unbiased Online Sampling for Visual Exploration of Large Spatiotemporal Data}},
  booktitle = {IEEE VAST@IEEE VIS},
  year = {2020},
  url = {https://openreview.net/forum?id=w8DmYQYddy},
}
Figure