<figure><img src="image_1.png" /></figure>

HAL
open science

Progressive Data Analysis

Jean-Daniel Fekete, Danyel Fisher, Michael Sedlmair

► To cite this version:

Jean-Daniel Fekete, Danyel Fisher, Michael Sedlmair. Progressive Data Analysis. Eurographics, pp.231, 2024, 978-3-03868-270-7. 10.2312/pda.20242707. hal-04776568

HAL Id: hal-04776568

https://inria.hal.science/hal-04776568v1

Submitted on 11 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Progressive Data Analysis
## Roadmap and Research Agenda

<figure><img src="image_3.png" /></figure>

Editors: Jean-Daniel Fekete, Danyel Fisher
and Michael Sedlmair
# Progressive Data Analysis

## Roadmap and Research Agenda

**Editors:** Jean-Daniel Fekete, Danyel Fisher, and Michael Sedlmair

<figure><img src="image_4.png" /></figure>

WRITTEN
BY
HUMANS
Copyright © 2024 by the authors.

This work is licensed under CC BY 4.0. To view a copy of this license, visit
https://creativecommons.org/licenses/by/4.0/

Published by the Eurographics Association
—Groene Loper 3, 5612AE Eindhoven, The Netherlands.

Printed by BELTZ Grafische Betriebe GmbH, Bad Langensalza, Germany.

Cover image © by Véronique Fekete

ISBN: 978-3-03868-270-7

The electronic version of this work is available from the Eurographics Digital Library:
https://doi.org/10.2312/pda.20242707
# Preface

We live in an era in which data is abundant and growing rapidly. Big data databases sprawl past memory and computation limits and across distributed systems. To sustain this growth, engineers are designing new hardware and software systems with new storage management and capabilities for predictive computation. Yet, as datasets grow and computations become more complex, response times suffer. These infrastructures, while good for data at scale, do not support exploratory data analysis (EDA) effectively. EDA allows analysts to make sense of data with little or no known model and is essential in many application domains, from network security and fraud detection to epidemiology and preventive medicine. Data exploration is conducted with an iterative loop in which analysts interact with data through computations that return results, usually displayed with visualizations, which the analyst can then interact with again. EDA requires highly responsive system response times: at 500 ms, users typically change their querying behavior; after five or ten seconds, they abandon tasks or lose attention. To address this problem, a new computational paradigm has emerged in the last decade, which goes under several names. In the database community, it is called *online aggregation*, while among visualization researchers, it has been called *progressive, incremental, or iterative visualization*. In this book, we will refer to it as *Progressive Data Analysis*.

This paradigm consists of splitting long computations into a series of approximate results that improve over time. In this process, partial or approximate results are rapidly returned to the user and can be interacted with in a fluent and iterative fashion. With the increasing growth in data, such progressive data analysis approaches will become one of the leading paradigms for data exploration systems, but it will also require major changes to algorithms, data structures, and visualization tools.

By solving the latency issue, progressive data analysis opens up new perspectives but also presents new challenges. Problems involving complex analyses can now be addressed interactively with little or no preparation time, but how long should the analyst wait before obtaining results that are good enough to make decisions? Can progressive systems provide effective quality measures to avoid either waiting too long or deciding too early? While the progressive process is being computed, the iterative visualization of partial results should remain stable enough to be monitored.
Can we stabilize these partial results without hurting their quality or speed? And, more fundamentally, can we transform all data analysis operations so that they become progressive? These questions, among others, are at the core of this book.

This book is an introduction to the new paradigm of progressive data analysis and visualization. It explores the major scientific and technical benefits of performing complex data analysis progressively on big data. It also examines the challenges that must be addressed for the paradigm to become fully usable. These important issues involve research fields that are traditionally viewed as separate areas in computer science: databases, scientific computing, machine learning, visualization, statistics, and human-computer interaction; they will need to work together to achieve end-to-end solutions to solve these challenges and enable the emergence of practical, progressive systems. This book closes with a research agenda to help researchers converge on key questions.

## Acknowledgments

This book is the result of the Dagstuhl seminar 18411 "Progressive Data Analysis and Visualization". We want to thank Schloss Dagstuhl—Leibniz Center for Informatics for its support and the outstanding facility it provides to researchers. We also thank all the participants for the fruitful discussions.

Many people helped prepare this book, in addition to the chapter authors and editors. It was written mostly during the COVID-19 crisis while several authors struggled to manage their health, professional, and family life. We are grateful for their scientific dedication.

We want to thank: Anastasia Bezerianos, Remco Chang, Min Chen, Pierre Dragicevic, Steven Drucker, Nivan Roberto Ferreira, Dominik Moritz, Jaakko Peltonen, Adam Perer, Christian Poli, Marianne Procopio, Guido Reina, Daniel Weiskopf, Eugene Wu, and anonymous reviewers for proofreading chapters of this book and providing insightful feedback.

Jean-Daniel Fekete, Danyel Fisher, Michael Sedlmair, Editors
Paris, Seattle, Stuttgart, November 10, 2024
# Contents

<table><tr><td>Preface</td><td>i</td></tr><tr><td>1 Introduction</td><td>1</td></tr><tr><td>1.1 Intuition</td><td>2</td></tr><tr><td>1.2 Why we need Progressive Data Analysis</td><td>4</td></tr><tr><td>1.3 Illustrative Scenario</td><td>6</td></tr><tr><td>1.4 Resistance to Progressive Data Analysis?</td><td>9</td></tr><tr><td>1.5 A History of Progressive Data Analysis</td><td>10</td></tr><tr><td>1.6 Goal of the Book</td><td>10</td></tr><tr><td>1.7 A Research Future for PDA</td><td>12</td></tr><tr><td>1.8 Organization of this Book</td><td>13</td></tr><tr><td>2 Concepts and Definition</td><td>16</td></tr><tr><td>2.1 Motivation</td><td>16</td></tr><tr><td>2.2 Concepts</td><td>18</td></tr><tr><td>2.3 Definitions</td><td>22</td></tr><tr><td>2.4 Progressive-in-chunks and Progressive-in-iterations</td><td>30</td></tr><tr><td>2.5 Summary</td><td>31</td></tr><tr><td>3 Data Management</td><td>33</td></tr><tr><td>3.1 Motivation</td><td>33</td></tr><tr><td>3.2 Requirements for Progressive Data Management</td><td>36</td></tr><tr><td>3.3 Computing Progressive Results</td><td>37</td></tr><tr><td>3.4 Progressive Queries</td><td>39</td></tr><tr><td>3.5 Progressive Data Exploration Systems</td><td>42</td></tr><tr><td>3.5.1 OLA-RAW</td><td>42</td></tr><tr><td>3.5.2 ProgressiveDB</td><td>45</td></tr><tr><td>3.6 Extended Services for Progressive Data Management</td><td>47</td></tr><tr><td>3.7 Summary</td><td>48</td></tr><tr><td>4 Data Structures and Algorithms</td><td>49</td></tr><tr><td>4.1 Vision</td><td>51</td></tr></table>
<table><tr><td>4.2</td><td>Motivation</td><td>51</td></tr><tr><td>4.2.1</td><td>Streaming and Steerable Visualization</td><td>52</td></tr><tr><td>4.2.2</td><td>Creating a Progressive Algorithm</td><td>53</td></tr><tr><td>4.2.3</td><td>Uncertainty on Aggregated Results</td><td>54</td></tr><tr><td>4.3</td><td>Basic Data Structures for Progressivity</td><td>54</td></tr><tr><td>4.3.1</td><td>Vectors, Multidimensional Arrays, and Tensors</td><td>55</td></tr><tr><td>4.3.2</td><td>Data Tables</td><td>56</td></tr><tr><td>4.3.3</td><td>Networks</td><td>56</td></tr><tr><td>4.4</td><td>Basic Algorithms</td><td>57</td></tr><tr><td>4.4.1</td><td>Broadcasting Operations</td><td>58</td></tr><tr><td>4.4.2</td><td>Linear Algebra</td><td>59</td></tr><tr><td>4.4.3</td><td>Statistical Operations</td><td>60</td></tr><tr><td>4.4.4</td><td>Data Sketching</td><td>60</td></tr><tr><td>4.5</td><td>Input and Output</td><td>61</td></tr><tr><td>4.5.1</td><td>Detailed Input</td><td>61</td></tr><tr><td>4.6</td><td>Specific Progressive Services and Strategies</td><td>64</td></tr><tr><td>4.6.1</td><td>Progressive Stability and Normalization</td><td>64</td></tr><tr><td>4.6.2</td><td>Data Change Management</td><td>65</td></tr><tr><td>4.7</td><td>Summary</td><td>67</td></tr><tr><td>5</td><td>Visualization</td><td>69</td></tr><tr><td>5.1</td><td>From Classic to Scalable Visualization</td><td>70</td></tr><tr><td>5.2</td><td>From Scalable to Progressive Visualization</td><td>73</td></tr><tr><td>5.2.1</td><td>Progressive Rendering</td><td>73</td></tr><tr><td>5.2.2</td><td>Interaction, Steering, and Control</td><td>78</td></tr><tr><td>5.3</td><td>Designing a Progressive Visual Analytics System</td><td>79</td></tr><tr><td>5.3.1</td><td>Choose the Right Visual Mapping</td><td>79</td></tr><tr><td>5.3.2</td><td>Represent the Changes</td><td>80</td></tr><tr><td>5.3.3</td><td>Visualizing the Progression</td><td>81</td></tr><tr><td>5.3.4</td><td>Interaction Between Visualization and Progression</td><td>82</td></tr><tr><td>5.4</td><td>Existing Visualization Approaches in PDA</td><td>82</td></tr><tr><td>5.4.1</td><td>DimXplorer</td><td>83</td></tr><tr><td>5.4.2</td><td>InsightsFeed</td><td>85</td></tr><tr><td>5.4.3</td><td>ProReveal</td><td>87</td></tr><tr><td>5.5</td><td>Challenges for Progressive Visual Analytics</td><td>89</td></tr><tr><td>5.6</td><td>Summary</td><td>90</td></tr></table>
<table><tbody><tr><td><strong>6</strong></td><td><strong>Uncertainty and Quality</strong></td><td><strong>92</strong></td></tr><tr><td>6.1</td><td>Introduction</td><td>92</td></tr><tr><td>6.2</td><td>Example Pipelines</td><td>95</td></tr><tr><td>6.3</td><td>Sources of PDA Uncertainty</td><td>96</td></tr><tr><td>6.3.1</td><td>Uncertainty from Data Processing</td><td>96</td></tr><tr><td>6.3.2</td><td>Uncertainty from Computation</td><td>97</td></tr><tr><td>6.3.3</td><td>Uncertainty from the Progression</td><td>98</td></tr><tr><td>6.4</td><td>Measures/Quantification of Uncertainty</td><td>99</td></tr><tr><td>6.4.1</td><td>Sampling Approximations</td><td>100</td></tr><tr><td>6.4.2</td><td>Aggregation Approximates</td><td>103</td></tr><tr><td>6.4.3</td><td>Computation-based Approximates</td><td>104</td></tr><tr><td>6.4.4</td><td>Progressive Measures</td><td>105</td></tr><tr><td>6.5</td><td>Visualization of PDA Uncertainty</td><td>105</td></tr><tr><td>6.6</td><td>Summary</td><td>107</td></tr><tr><td><strong>7</strong></td><td><strong>Human Aspects</strong></td><td><strong>108</strong></td></tr><tr><td>7.1</td><td>Time Engineering for Human Factors</td><td>110</td></tr><tr><td>7.2</td><td>User Roles</td><td>111</td></tr><tr><td>7.2.1</td><td>Role 1: The Progressive Observer</td><td>111</td></tr><tr><td>7.2.2</td><td>Role 2: The Progressive Searcher</td><td>112</td></tr><tr><td>7.2.3</td><td>Role 3: The Progressive Explorer</td><td>113</td></tr><tr><td>7.3</td><td>User Tasks</td><td>114</td></tr><tr><td>7.3.1</td><td>The Observer's Analytic Tasks</td><td>115</td></tr><tr><td>7.3.2</td><td>The Searcher's Analytic Tasks</td><td>116</td></tr><tr><td>7.3.3</td><td>The Explorer's Analytic Tasks</td><td>116</td></tr><tr><td>7.4</td><td>User Focus</td><td>117</td></tr><tr><td>7.4.1</td><td>F1: Focus on the Data Space</td><td>118</td></tr><tr><td>7.4.2</td><td>F2: Focus on the Algorithm Space</td><td>119</td></tr><tr><td>7.5</td><td>User Complications and Biases</td><td>120</td></tr><tr><td>7.6</td><td>Application Example: Crisis Management</td><td>124</td></tr><tr><td>7.6.1</td><td>The Background</td><td>124</td></tr><tr><td>7.6.2</td><td>An Illustrating Scenario</td><td>126</td></tr><tr><td>7.6.3</td><td>The Design Guidance</td><td>128</td></tr><tr><td>7.7</td><td>Summary</td><td>130</td></tr><tr><td><strong>8</strong></td><td><strong>Progressive Methods in Machine Learning</strong></td><td><strong>132</strong></td></tr><tr><td>8.1</td><td>Introduction</td><td>132</td></tr></tbody></table>
<table><tbody><tr><td>8.2</td><td>Motivation</td><td>134</td></tr><tr><td>8.3</td><td>Progressive Machine Learning Algorithms</td><td>135</td></tr><tr><td>8.3.1</td><td>Characteristics of ML Algorithms</td><td>135</td></tr><tr><td>8.4</td><td>Examples of Progressive ML Algorithms</td><td>138</td></tr><tr><td>8.4.1</td><td>k-Nearest Neighbors Classifier</td><td>138</td></tr><tr><td>8.4.2</td><td>Support Vector Machines as Classifiers</td><td>140</td></tr><tr><td>8.4.3</td><td>Deep Neural Networks</td><td>143</td></tr><tr><td>8.5</td><td>Challenges and Recent Advances</td><td>145</td></tr><tr><td>8.6</td><td>Summary</td><td>147</td></tr><tr><td><b>9</b></td><td><b>Evaluation</b></td><td><b>149</b></td></tr><tr><td>9.1</td><td>Scenario and Challenges</td><td>150</td></tr><tr><td>9.1.1</td><td>Approaches to Evaluation</td><td>150</td></tr><tr><td>9.1.2</td><td>Performance Measures</td><td>152</td></tr><tr><td>9.2</td><td>Evaluation at Multiple Stages of the Pipeline</td><td>153</td></tr><tr><td>9.2.1</td><td>Data Management</td><td>153</td></tr><tr><td>9.2.2</td><td>Algorithms</td><td>156</td></tr><tr><td>9.2.3</td><td>Visualization and Interaction</td><td>158</td></tr><tr><td>9.2.4</td><td>Human Factors: Perception and Cognition</td><td>163</td></tr><tr><td>9.2.5</td><td>Machine Learning</td><td>166</td></tr><tr><td>9.2.6</td><td>System Level</td><td>167</td></tr><tr><td>9.3</td><td>Summary</td><td>169</td></tr><tr><td><b>10</b></td><td><b>Challenges and Research Agenda</b></td><td><b>171</b></td></tr><tr><td>10.1</td><td>Overarching Challenges to Broader Adoption of PDA</td><td>171</td></tr><tr><td>10.2</td><td>Data Management</td><td>172</td></tr><tr><td>10.3</td><td>Data Structures and Algorithms</td><td>173</td></tr><tr><td>10.4</td><td>Visualization</td><td>174</td></tr><tr><td>10.5</td><td>Quality and Uncertainty</td><td>176</td></tr><tr><td>10.6</td><td>Human Aspects</td><td>177</td></tr><tr><td>10.7</td><td>Machine Learning</td><td>177</td></tr><tr><td>10.8</td><td>Evaluation</td><td>178</td></tr><tr><td>10.9</td><td>Threats and Opportunities</td><td>180</td></tr><tr><td><b>11</b></td><td><b>Conclusion</b></td><td><b>182</b></td></tr><tr><td></td><td><b>Bibliography</b></td><td><b>184</b></td></tr></tbody></table>
Contents

List of Figures 209

List of Tables 211

List of Definitions 212

Listings 213

Alphabetical Index 215
<figure><img src="image_5.png" /></figure>
List of Authors

<table><tr><td>Chapter 1</td><td>Jean-Daniel Fekete<br>Danyel Fisher<br>Michael Sedlmair</td><td>Inria & Université Paris-Saclay<br>University of Stuttgart</td></tr><tr><td>Chapter 2</td><td>Michaël Aupetit<br>Giuseppe Santucci</td><td>Qatar Computing Research Institute<br>Sapienza, Università di Roma</td></tr><tr><td>Chapter 3</td><td>Florin Rusu<br>Chris Weaver<br>Carsten Binnig</td><td>University of California Merced<br>University of Oklahoma<br>Technical University of Darmstadt & DFKI</td></tr><tr><td>Chapter 4</td><td>Jean-Daniel Fekete</td><td>Inria & Université Paris-Saclay</td></tr><tr><td>Chapter 5</td><td>Marco Angelini<br>Jaemin Jo</td><td>Sapienza, Università di Roma<br>Sungkyunkwan University</td></tr><tr><td>Chapter 6</td><td>Anna Vilanova<br>Marco Angelini<br>Sriram Karthik Badam<br>Jean-Daniel Fekete</td><td>Eindhoven University of Technology<br>Sapienza, Università di Roma<br>Apple Inc.<br>Inria & Université Paris-Saclay</td></tr><tr><td>Chapter 7</td><td>Hans-Jörg Schulz<br>Michaël Aupetit<br>Danyel Fisher</td><td>Aarhus University<br>Qatar Computing Research Institute</td></tr><tr><td>Chapter 8</td><td>Cagatay Turkay<br>Nicola Pezzotti<br>Hendrik Strobelt<br>Barbara Hammer</td><td>University of Warwick<br>Philips Cardiologs & Eindhoven University of Technology & AI4MRI LUMC<br>IBM Research, MIT-IBM Watson AI Lab<br>CITEC, Bielefeld University</td></tr><tr><td>Chapter 9</td><td>Gaëlle Richer<br>Jean-Daniel Fekete<br>Michael Sedlmair</td><td>Inria & Université Paris-Saclay<br>Inria & Université Paris-Saclay<br>University of Stuttgart</td></tr><tr><td>Chapter 10 & 11</td><td>Jean-Daniel Fekete<br>Danyel Fisher<br>Michael Sedlmair</td><td>Inria & Université Paris-Saclay<br>University of Stuttgart</td></tr></table>
<figure><img src="image_6.png" /></figure>
# 1 Introduction

<table><tr><td>1.1</td><td>Intuition</td><td>2</td></tr><tr><td>1.2</td><td>Why we need Progressive Data Analysis</td><td>4</td></tr><tr><td>1.3</td><td>Illustrative Scenario</td><td>6</td></tr><tr><td>1.4</td><td>Resistance to Progressive Data Analysis?</td><td>9</td></tr><tr><td>1.5</td><td>A History of Progressive Data Analysis</td><td>10</td></tr><tr><td>1.6</td><td>Goal of the Book</td><td>10</td></tr><tr><td>1.7</td><td>A Research Future for PDA</td><td>12</td></tr><tr><td>1.8</td><td>Organization of this Book</td><td>13</td></tr></table>

**Authors** Jean-Daniel Fekete, Danyel Fisher, and Michael Sedlmair

Books on data always start with the usual clichés about the wealth of data being generated nowadays, and this one is no exception. What we are looking for is a way to allow the exploration of data at scale, but the fact is that there is currently no satisfactory solution that would allow an analyst to dive into a large dataset and make sense of it using current data exploration methods. The scale of existing exploratory systems is limited for reasons that will not be resolved by improving processor speed and network bandwidth. We are reaching physical limits for computer and data communication speed.

As datasets grow and computations become more complex, the response time of interactive systems suffers. The progressive paradigm has emerged over the last decade to address this problem. The Progressive Data Analysis (PDA) paradigm splits long computations into a series of approximate results that improve with time. For example, by looking at smaller subsets of the data, the user quickly sees a result and can decide how to respond to it—whether to move to the next question or wait for further refinement of the result. PDA offers data analysts a trade-off between time lost while waiting and accuracy of results. Choosing the shortest amount of time to make a decision in order to maximize an expected reward is an instance of the well-known “optimal stopping” problem [52].

In this book, we will describe PDA as a human-in-the-loop process that supports data exploration at scale. Humans input queries to a system that would ordinarily
have a long response time either because of long computation times or large data operations. The user accepts less accuracy of responses in exchange for low latency. PDA is “progressive” in that we expect to receive more precise responses over time, either by examining increasingly large samples or by continuing a slow computation.

Coupled with interactive visualization, PDA becomes Progressive Visual Analytics (PVA), which allows analysts to conduct data exploration at scale and to interact with complex computations such as statistical analyses, machine learning, and simulations.

PDA and PVA are both based on the principle of continuous control, in which analysts are able to interact with the computer during computation, for example, by adjusting computation parameters based on actual results, a process called *steering*.

Systems that use the PDA paradigm are designed to take into account human capabilities (e.g., monitoring, controlling, or steering the computation as it progresses), as well as limitations, particularly regarding latency and attention. As we know from research in Human-Computer Interaction (HCI) [179, 199, 281], humans who interact with computers need to receive a response from the system with bounded latency to avoid dramatic declines in efficiency. While PDA can alleviate the latency issue to some extent, as Zgraggen et al. [342] have shown, progressivity introduces several other complications for computer systems and human cognition that must be addressed. This book is an attempt to identify these issues and challenges and to lay out a research agenda to address them.

As we will see in the following chapter, PDA decouples the latency issue from computational complexity, but at the cost of having to assess and monitor the quality of the results.

PDA can also be seen as a broad net approach: a system might provide regular updates—or it might provide a first approximation and only produce high-quality results on demand. These different approaches allow PDA systems to be tailored to their usage patterns and data environments.

## 1.1 Intuition

We are already familiar with progressive processes from everyday life; the computer-supported examples are fundamentally no different. In this section, we use an example of a United States presidential election to help develop an intuition of how Progressive Data Analysis works.

In the last few election cycles in the United States, the world has seen the challenges of Progressive Data Analysis in action as it struggled through the aftermath of the US
presidential election. Although by election day, every voter had decided and every vote had been cast, the process of receiving, validating, and counting those votes would be spread out over weeks.

The process of counting ballots in a national US election is an example of Progres-
sive Data Analysis. Two candidates compete for the largest number of electoral votes.
Computationally, the process can be modeled in three simple phases:

1. The tallying of the number of votes for each candidate in each electoral district,

2. The assignment of electoral votes based on these numbers,

3. The selection of the candidate with the largest number of electoral votes, while checking for any possible fraud and error.

Each phase can be computed precisely, and accurate results can be expected to
arrive after a certain amount of time. This delay, however, is unsatisfactory for
many stakeholders: for the news media that wants to announce the results; for the
candidates who want to know if they won.

Looking at the results progressively can help us predict the results of the contest
and allow candidates to begin transitioning to their new jobs. As batches of ballots
arrive, there are several tasks that are specific to PDA:

1. An estimation of the likelihood that the outcome will be in favor of one candidate vs. the other based on intermediate results,

2. Detecting and addressing possible fraud or errors as early in the process as possible,

3. Identification of what future information—such as critical county results—might improve the quality of estimates most and the elimination of results that will have no effect on the outcome.

As we saw during the post-election process, anyone attempting to figure out who
the next president was going to be encountered many challenges. How good were the
current results as a predictor of the outcome? Were the votes that had been tallied
thus far a representative sample of what would be counted later? Journalists struggled
to find the right language to describe what was happening, making remarks about
whether one candidate had “momentum” or “a lead”—language that implied that new
votes were somehow still being cast or new information was emerging.

Even for a national election in an experienced country, monitoring and controlling
this seemingly simple progressive process can be challenging. Would the process
run more smoothly if the final decision were not made public until the end? If the
process were flawless, monitoring would just be a source of distraction for some and
entertainment for others. However, where the process has potential issues, the failure
to monitor it progressively would raise suspicions and create problems.
In the best cases, we can expect to see a clear trend early in the process and we can be confident about the outcome early on without having to closely monitor the process. These early decisions are essential in optimizing the time we spend on time-consuming processes and in optimizing energy consumption by stopping any costly computations early, an issue that is relevant in green computing, a topic that has been increasingly receiving attention.

This book will highlight *when* PDA might be useful or necessary, *what* its main benefits, issues, and open questions are, and *how* it should be used and implemented. We can already say with certainty that one of PDA's most exciting aspects is the way that it opens up so many opportunities for the exploration of data that were previously impossible. However, PDA systems pose implementation challenges because they use a paradigm that differs in important ways from those of traditional programming and execution semantics. Therefore, it will require effort and time to design and implement mature, progressive systems, and many parts of the traditional data analysis software “stack” will need adaptation.

## 1.2 Why we need Progressive Data Analysis

The ability to explore data interactively remains as important as ever, maybe even more so given the importance of data today. But unfortunately, exploration is still lagging behind. We constantly hear optimistic claims about how we are now able to obtain perfect data, processed by perfect systems providing perfect results using a well-known objective function. The result of this has been to obscure the importance of exploration. No research domain or industry wants to advertise the issues they're confronting with data. Yet, the reality is something quite different. Data is rarely clean, analysis systems are rarely perfect—sometimes far from it—and it often delivers results that at the very least need to be verified (if not discarded outright) and require humans to assess its utility. But how would we know any of this without exploration tools?

Initially, Exploratory Data Analysis (EDA) [303] was designed to help statisticians make sense of data, which assumed that the data was already available and small enough in size to be visualized using the basic visual representations: bar charts, line charts, histograms, scatterplots, and a few others. These assumptions have changed in important ways. Today, the statistician has been replaced by a range of different analysts working to make sense of data—including, in addition to engineers and scientists, ordinary citizens, activists, journalists, humanists, and marketing
specialists.

Contemporary data exploration has become an extremely diverse field, encompassing data scrutiny, data cleaning, and more generally, data wrangling [150]. It also includes the exploration of statistical data, website and program logs, simulation results, and models fitted by machine learning, often applied to dynamic data.

The exploration of server logs can reveal intrusions, malfunctions, and interesting navigation patterns. Cars, trains, and planes now collect telemetry data that can reveal important information about intermittent problems, worn parts, or even traffic patterns. By simulating power production in a country, for example, thousands of possible scenarios can be generated allowing us to predict a vast range of possible futures, some of which will be impossible, while others are unexpected. Through exploration we are able to discover these among the myriad of well-understood scenarios, as well as to uncover possible bugs in the simulators. AutoML [112] optimizes machine learning pipelines by trying many possible pipelines with even larger numbers of hyper-parameters. In reality, comparing the results of these pipelines requires exploring quality measures with limited resources.

Despite the need to explore these large datasets gathered or produced dynamically, exploratory systems are still lagging behind. Progressive systems should be able to catch up with the scalability requirements for handling large data, and it is the goal of this book to speed up their development, evolution, and eventual adoption.

In data analytics, two fundamental concepts are in tension. One is related to the fact that data exploration is best done with an iterative loop, in which analysts interact with data through computations that return and visualize results. In response, analysts issue new commands, triggering new computations until they obtain an answer to their questions. The faster these loops go, the more effective analysts are: users behave qualitatively differently with rapid response times, allowing them to explore hypotheses more effectively [179]. The other, of course, is the fact that we have gotten better at collecting data and making it available for querying. Increasingly, we want to make data-driven decisions, and to do so flexibly without the need to pre-aggregate and pre-compute results. This “cold start” problem can make for slow computation.

A number of obstacles can stand in the way of interactivity. Some data sits on the other side of a network and can take a long time to move, process, and visualize. At other times, data volumes are so large that visualization can become slow. Finally, some computation algorithms take a long time to run and get longer as they become more sophisticated. The purpose of PDA is to mitigate these obstacles.
## 1.3 Illustrative Scenario

How would a data analyst perform Progressive Data Analysis assuming the existence of a full PDA system? We could build on multiple experimental systems, merging their best features to imagine a mature product. There are currently two very different approaches to exploratory systems. Data scientists tend to use computational notebooks such as Jupyter for Python and RStudio for R, while domain practitioners tend to use graphical applications such as Tableau or Power BI. PDA can be used in either of these approaches with proper modifications to the user interface as outlined in Chapter 5 Visualization.

As an example scenario, consider the role of data exploration in public health. This scenario is adapted from a collaboration with French Social Security for the analysis of patient treatments in France. The goal is to update national recommendations for specific diseases using evidence from massive amounts of medical treatment data.

The Ministry of Health has a strong interest in understanding the effects of public health measures, including by searching for both cost and utility efficiencies. To that end, it asked Social Security to start analyzing data initially collected for reimbursement purposes for all persons covered by French Social Security—about 70 million at any given time—with a history of 25 years.

Unfortunately, the Social Security researchers are extremely limited in how they can explore and interact with the data. The data presents challenges both in terms of scale and form. There might be hundreds of millions of patients visiting doctors and hospitals in any given year. An individual patient might be associated with thousands of records and each record might contain hundreds of different fields. The data is heterogeneous: an X-ray might be associated with a radiologist's analysis, imaging, and diagnostic code; a prescription might be associated with the dosage, frequency, and so on. In addition to structured data, an analyst may need to examine unstructured text, images, and even audio or video data.

The process of working with the data is arduous. When a medical data analyst wants to explore this data, they will often write a series of data cleaning and transformation scripts that move a subset of the data into a smaller database, which is then pre-indexed. The disadvantages are clear: the analyst is limited to making decisions about the data before cleaning and transforming, and the costs of this work make it impossible to explore new questions quickly.

The promise of PVA is that it can allow complex data to be explored at scale by the medical doctors with a PVA Health Explorer. A group of specialists in charge of national recommendations for a disease or condition can visualize the aggregated
treatment history of all the French patients. Many chronic illnesses involve millions
of patients over decades—billions of medical events.

Currently, systems for exploring these aggregated patient pathways are in the
experimental stage [201], but they are limited to 50–100k patients with hundreds of
events. A progressive system can easily handle hundreds of millions of patients with
thousands of events, allowing doctors to look at the situation at the country level. The
first thing the doctors will want to understand is how the drugs are being used. They
will do this by looking at an overview of the treatment pathways (see Figure 1.1).

The overview is computed progressively, meaning that the beginning of the aggre-
gated history stabilizes quickly, while the deeper leaf nodes may take a few seconds
to stabilize. Fortunately, the doctors are initially interested in the main trends that
are near the beginning of the treatments. They notice that in about half the cases
the treatments follow their recommendations and are consistent with their expec-
tations. But in the other half, there are unexpected situations. For example, they
believed that after surgery all the patients would be cured. But in reality, there will
always be a certain percentage of patients—about 5%—who need continued treat-
ment, sometimes including a second surgery. Why does that happen? All of these
unexpected situations call for further exploration and steer questions. Is it an issue of
old recommendations vs. new, older patients vs. younger? Does it have to do with
patients with a particular set of health conditions (diabetes, hypertension, overweight,
etc)? By filtering for the large number of attributes associated with the patients, the
doctors can try to discover why some patients are not following recommendations.
Selecting a rectangle shows the associated attributes to the right. The system allows
filtering using any number of attributes or history patterns to limit the visualization to
specific contexts and conditions. A change in the filter will update the visualization
progressively, providing an approximate result immediately, with details becoming
more stable in a few seconds at most.

The doctors are able to use these filtered results to collect a set of unexplained
cases. They can build a cohort of patients for further analysis. Again, even while
the analysis continues, they have a first few patients that they can check manually.
For example, these early samples might show that there are a lot of patients with this
diagnosis being treated in a very different way because they suffer from high blood
pressure. Perhaps there are interactions between the drugs being taken for the two
conditions, leading the doctors to modify their recommendations on that basis.

At each step of the exploration, the ability to view a fraction of data allows doctors
to decide whether to use the current result or to continue exploring. In all cases,
progressiveness provides them with partial results in just seconds, regardless of
<figure><img src="image_7.png" /><figcaption>Figure 1.1: Icicle tree visualization of the aggregated events of 10 million (synthetic) patients treated for non-cancerous prostate adenoma. Each colored rectangle represents a treatment; its height is proportional to its frequency (e.g., the large yellow lower left rectangle's height represents 40%, meaning that 40% of the patients started with the drug "alphabloc"), and its width represents the average duration of the treatment, except "surgery" and "death" that have no duration. On the right of the yellow rectangle is the next stage of the treatment. For the most part, people who started with it are staying with it until the end (the large bottom right section after the rectangle is empty). About 5% had a surgery (red line) or stopped their treatment for a certain time before continuing it or using another molecule.</figcaption></figure>
data size, allowing them to stay engaged in the exploration and leading to possible enhancements to the treatment recommendations.

1.4 Resistance to Progressive Data Analysis?

PDA's detractors are concerned that PDA systems have requirements that are incom-
patible with most existing software libraries. Traditional libraries have APIs that
are based on function calls that run once, not progressively. A traditional function
call may take an unbounded amount of time to run, but returns a single result that is
as accurate as possible. Calling the equivalent progressive function, as discussed in
Section 2.3, would return a sequence of results, each bounded in time and improving
in quality. Such a paradigm shift would be expensive to achieve, so it is worth
considering whether there might be alternatives to PDA.

Scalability in (visual) exploration can be achieved without PDA when the dataset
and exploration tasks are well defined, allowing resources to be invested upfront to
match latency constraints. A number of systems are scalable because they perform
pre-computations to serve results without performing overly expensive (and time-
consuming) calculations [133]. The Nanocubes system [177] allows exploration of
large spatiotemporal datasets by pre-aggregating results ahead of time. While the
pre-aggregation step can take hours, the system runs in interactive time afterward.
The Cartolabe system [39] allows visualization and exploration of large textual
corpora by pre-processing them: downloading, analyzing, and performing expensive
computations (NLP, multidimensional projection, clustering) ahead of time. The
Falcon system [206] allows exploration of long time series using cross-filtering by
relying on a high-performance approximate database, requiring a preparation time to
ingest and index data. These scenarios do not apply when exploration is performed
only once and has to be cold-started; the initial investment of collecting data, cleaning,
and pre-processing it must be accounted for as bottlenecks or even roadblocks.

By contrast, a pure PDA system allows cold starting of the exploration process:
there is no need to download datasets before beginning exploration, no need to pre-
process data or create indexes. PDA systems reduce preparation time and enable
spontaneous explorations, in comparison to those that involve significant preparation
overhead. For exploring large data with complex algorithms, open-ended tasks, and
bandwidth-limited data communication channels, PDA has no clear competitor.
## 1.5 A History of Progressive Data Analysis

Early solutions using progressive computations date back to the late 1990s with Hellerstein et al. [117] coining of the concept of “online aggregation”. This term is still used in the database domain to refer specifically to the output aspect of a progressive computation, albeit without steering. Although early articles on online aggregation also mentioned visualization, the progressive approach has specialized in different directions, and has relied heavily on visualizations during the first decades of the new millennium. These have been introduced under different names, such as Incremental Visualization [89], Progressive Visualization [92], Per-Iteration Visualization [157], and Progressive Visual Analytics [11]. The idea of displaying partial results before the final result is complete was not unique to database researchers. The graph-drawing community has been using progressive layout methods since the early '90s following Eades' work on the force-based layout method [74]. Early Web browsers (Mosaic, Netscape) of the same era also featured progressive download of web pages, images, and progressive HTML layout as a way to mitigate the Internet's latency. These early progressive systems were designed for very specific tasks, whereas PDA is aimed at general data exploration.

There is as yet no unique consensus name for these approaches, and this book uses the term *Progressive Data Analysis* as a generic term, along with others such as *Progressive Visual Analytics* (PVA) to emphasize the role of visualization and interaction. Where other terms appear in the following chapters, they are relics of their various origins. One of our goals is to connect previous studies related to PDA in an effort to strengthen the field, identify the research questions raised in the past, and collaborate in order to answer them both now and in the future, crossing over traditional research domains.

In Chapter 2, we'll outline some of the philosophical differences between approaches that are somewhat similar to PDA, highlighting the main differences and addressing possible sources of misunderstanding about PDA.

## 1.6 Goal of the Book

The goal of this book is to tame this proliferation of paradigms and approaches related to Progressive Data Analysis.

In the past, attempts to build progressive systems have been slowed down because of the fragmentation of the research fields. Database researchers have been able
to build early progressive database engines [116, 117], but their results were not
usable in traditional back-ends. The visualization community also designed early
progressive systems, but their data management has not proven scalable. Lying
somewhere in the middle, data analysis and machine learning, despite their needs,
have only been able to build prototype progressive systems [293, 334] due to the lack
of adequate data management and visualization support. We strongly believe that the
problem of Progressive Data Analysis should be tackled in a holistic way by all three
communities working together, as is reflected by the chapter authors of this book.
This will allow the field to grow and mature instead of remaining forever stuck in its
infancy.

Data analysis researchers and practitioners have already begun this process of
software evolution toward progressive systems. In October 2018, they gathered for a
seminar in Dagstuhl to exchange ideas, experiences, and visions [82]. They are all
convinced that in the coming years, Progressive Data Analysis will become a leading
paradigm for data exploration systems, but that it will require major changes in the
algorithms, data structures, and systems of today.

Most of the existing research in PDA has been done within one computer science
community, sometimes in collaboration with a particular application domain such as
medicine and biology (e.g., [128]), but rarely in collaboration with other communities
or domains.

The Dagstuhl seminar discussions convinced us that these silos are largely respon-
sible for the slow development and adoption of PDA, and the goal of this book is
to help break through the barriers standing in the way of this work and to foster
collaboration.

This book summarizes the main challenges that need to be addressed in designing
progressive systems and lays out a scientific roadmap for attacking the problems in
a constructive and consistent manner. It is, therefore, meant to serve as a first step
in this process, to clarify for all of the research communities what the main issues
are that need to be addressed, why they are important, and why they are sometimes
difficult. It seeks to provide a useful roadmap that can be used to find solutions to the
main challenges, deliver usable PDA systems to support data exploration, and make
sense of current and future data.
<figure><img src="image_8.png" /></figure>

## 1.7 A Research Future for PDA

PDA presents many exciting research opportunities, which are discussed in Chapter 10. They will also be mentioned as they come up in the book; research agenda entries are introduced as shown here: **Research Agenda:** (note the icon in the margin).

In our earlier example of the election scenario in Section 1.1, we saw some of the major issues that arise in progressive computation. Partial results had to be measured with wide error bars. To interpret the results, the news-watcher or analyst must understand the biases of the underlying system—different voting habits related to vote-by-mail vs. in-person ballots. There were even implications associated with different state-wide policies affecting when ballots could be counted and what data was available.

When designing a PDA system, it is vital to ensure that there are ways to help the user estimate current progress, recognize potential sources of bias, and keep them from prematurely reacting to incorrect results, and when they do make that mistake, to help them recover from it. Unfortunately, it can be hard for people to correct past errors.

We will frequently return to the question of how to manage the trade-off between stability and fresh results, ensuring that users are able to track how the results of partial computations change over time, especially in Section 5.2.1. Traditionally, visualizations have been built based on the data at hand. PDA implies that we will need to keep updating the visualization, but radical changes in scale or size can be disorienting.

For example, progressively loading and visualizing a network graph can be reasonably stable. When a node is added, a physics-based layout can often do a good job of maintaining relative positions around it. Connecting two existing nodes can change the layout quite a bit, especially if two disconnected components of the graph become connected; the graph layout then changes dramatically. Avoiding or overcoming these abrupt changes is a challenge for PVA. Other visualizations are even more sensitive: visualizing a bar chart while loading a large database progressively is sensitive to small data changes. For example, when visualizing the height of the average person in each country sorted by size, if two countries have almost the same average height, their positions may flip randomly when a new chunk is processed. PDA must find new visual or interactive strategies to avoid or mitigate these insignificant and distracting changes.

We will also return to the question of whether partial results are meaningful in Chapter 7. It can be tempting and risky for a user to quickly respond to a non-
<figure><img src="image_9.png" /><figcaption>Figure 1.2: The Information Visualization Reference Model, adapted from [41]</figcaption></figure>

representative sample of the source data.

There are challenges related to choosing progressive algorithms for machine
learning, as we address in Chapter 8. In modeling, simulation, and forecasting, it is
important to have humans monitor and steer progress. It can both ensure that the ML
system obtains a meaningful result and can save power by avoiding expensive model
training when the outcome can be foreseen by a skilled human.

This book calls for collaboration between the database, visualization, HCI, psy-
chology, and machine learning communities, as well as others, such as simulation.
It is intended to help bridge the gap between these communities and accelerate the
development of common ground to facilitate such collaboration.

1.8 Organization of this Book

As visualization researchers, we tend to think about PDA in the context of the
information visualization reference model [41] (Figure 1.2) and the Visual Analytics
reference model [154] (Figure 1.3). The Visualization Reference Model shows data
going from a data source through a series of transformations and into a final view.
The Visual Analytics Model suggests that data goes through a visualization phase, as
well as data modeling and mining. The two models remain valid for PDA, but data
processing and visualization are now progressive in both models.

The outline of the book follows these two reference models (Figure 1.4): from data
management to users, including perception and mental models, and from the connec-
tions between visualization and data modeling and mining. The key information that
should be taken from the reference models comes by recognizing the dependencies
<figure><img src="image_10.png" /><figcaption>Figure 1.3: The Visual Analytics Reference Model, adapted from [154]</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 1.4: From left to right, logical organization of book chapters related to the data analysis pipeline.</figcaption></figure>

between the areas. In traditional EDA, we can often abstract away different domains. That is, as long as there is a data table available, we can find a way to visualize it. The design of the data management and mapping algorithms will influence the sorts of visualizations that we can create. Requirements from user perception and cognition will influence requirements from data management on the other side of the pipeline. Therefore, the development of PDA solutions requires an awareness of the entire reference model and pipeline, overcoming the traditional separations.

We start by defining what PDA is in Chapter 2, comparing it to other well-known execution paradigms such as *streaming computation* and *anytime algorithms*. Throughout the book, we contrast progressive algorithms and visualizations with
their traditional counterparts, which in this book will be designated with the word *eager*.

We then introduce the typical issues that arise with a complete PDA sequence of
operations and interactions, starting with data management (Chapter 3) for loading,
storing, indexing, and querying data in a progressive way.

We then discuss how general computations are applied (Chapter 4) as data is pro-
gressively loaded into memory. We discuss how classical data structures, arithmetic,
linear algebra, and statistical methods can be adapted so that they are progressive.

Because Progressive Data Analysis is aimed at data exploration, visualization and the user interface play major roles. Chapter 5 addresses the main questions raised by the evolution of visualization techniques and the need to support user interfaces for progressive results in a way that is compatible with human perception and cognition. With progressive methods, visualizations should become scalable to very large amounts of data. This will also raise new scalability issues, some of which are specific to the use of progressive algorithms.

Chapter 6 addresses the problem of uncertainty with progressive computations that generate approximate solutions that improve over time. In these cases uncertainty needs to be assessed and presented to the analyst in an understandable way to assess whether a decision can be made at each point.

This issue of decision-making is one of many such topics discussed in Chapter 7 that touch on the human aspects of PVA and understanding.

Chapter 8 is dedicated to applications of progressivity to machine learning. Some methods are inherently progressive, some can be made progressive with adaptations, while others are more challenging.

Evaluating progressive systems is addressed in Chapter 9. This chapter discusses technical evaluation methods that are traditional in the database and data analysis communities, but also human-centered methods that are closer to the visualization and HCI communities. Both kinds of methods should be considered to ensure that progressive systems are effective for data exploration at scale.

The book concludes with a summary of the challenges raised by Progressive Data Analysis and offers a research agenda (Chapter 10) that should be approached in a multidisciplinary manner. Such an agenda will require several years of research and experimentation to reach a point of maturity where it offers high gain for high risk, just as all the paradigm shifts of the past have done.
# 2 Concepts and Definition

<table><tr><td>2.1 Motivation</td><td>16</td></tr><tr><td>2.2 Concepts</td><td>18</td></tr><tr><td>2.3 Definitions</td><td>22</td></tr><tr><td>2.4 <i>Progressive-in-chunks</i> and <i>Progressive-in-iterations</i></td><td>30</td></tr><tr><td>2.5 Summary</td><td>31</td></tr></table>

**Authors** Giuseppe Santucci and Michaël Aupetit

## 2.1 Motivation

When exploring data, the computation of meaningful results requires that data be available in sufficient quantity and quality, and that sufficient time be allowed for the computations to finish. However, in many cases, this setting is not optimal, if impossible at all, for those in charge of the computation.

When data access or computation is too slow, we can use data sampling. But how much sampling is enough to obtain meaningful results? We can, of course, also resort to iterative or incremental computation techniques and get our results gradually or progressively instead of all at once. This is what Progressive Data Analysis aims for. PDA can therefore be described as a data analysis technique that produces partial results during execution until the final results are computed.

As noted in Section 1.5, there is not yet a unique, agreed-upon name for this technique, but in this book, we call such techniques Progressive Data Analysis and Progressive Visual Analytics. A PDA system can be described as one that:

1. produces partial results that improve with time, with controlled latency,

2. uses visualization for the presentation of results,

3. meets appropriate requirements for the progression to be meaningful.

We will define these concepts more precisely later in this chapter. We will call non-progressive systems *eager*. Eager systems compute results all at once without controlling latency.
This chapter aims to provide a common framework for defining and formalizing the ideas and techniques associated with PDA and to clarify where progressive methods stand in the landscape of other related methods.

The concept of working through incremental results is not new in this kind of work. Indeed, we can see such methods as part of a wider landscape of systems, each designed to solve different kinds of problems. To get a sense of some of these specializations, we can look at some related concepts in the field of database research and other fields.

In Section 1.5, we made reference to the database concept of “online aggregation” (OLA). Database researchers have also explored the concepts of “streaming computation” and “anytime algorithms”. *Streaming computation* is an approach in which new data is streaming in continuously, e.g., from a remote sensor, and the associated time plays a significant role in its analysis, i.e., it has to be analyzed using a sliding time window. *Progressive* systems, by contrast, assume that the data is **static**, and thus does not change over time. The result analysis is conducted in a series of steps intended to satisfy latency constraints. *Anytime* algorithms start a computation process on the back-end. Here, the user can query the system at “any time” to request the latest computed result, which improves as more computation is performed. The user takes the latest result. This distinguishes it from online, streaming, and progressive systems, which push updates to the user. PDA generalizes these concepts, allowing interactive control steerability, and when it includes visualization, we call it *Progressive Visual Analytics (PVA)*.

Progressive systems can either have the goal of returning a single result or returning multiple results. For the latter, we will refer to *search/gather* progressive systems, in which the ultimate result is a list of results. In those cases, the progressive system may progress by incrementally returning results.

The proliferation of related concepts is both a blessing and a curse. It is a blessing because it acknowledges the need for a computation paradigm to help humans in exploring data at scale with complex analytical methods. There are already significant bodies of research and application work covering areas such as data streaming, online computation, and iterative algorithms. It is a curse because discussions of these concepts are often confusing and lead to misunderstandings. Is “Online aggregation” identical to PDA? Why aren’t streaming methods able to solve the latency problem? Our goal in this chapter, then, is to articulate the range of possibilities, to explain how these solutions are related, and to assess some of their trade-offs.

Ultimately, we see these multiple approaches as a strength. Algorithms and data processing paradigms that are developed in one tradition can sometimes be adapted to
others. For example, a clustering algorithm that can work on partial data might also be developed for use in anytime computation. It can be easily used for progressive systems, and adding knobs to make it steerable can make it even more powerful.

Key to the concept of progressive computation is the aspect of human monitoring and control. This can be illustrated by contrasting it with other approaches. In algorithm animation [155], an algorithm is instrumented to visualize the multiple steps it produces when it runs on data. In that case, the algorithm drives the system, and the human monitors the algorithm with limited control—often doing nothing but starting, pausing, and stopping the animation. In-situ visualization [185] is another important topic in visualization related to simulation. In-situ systems instrument a simulation program to generate visualizations on-the-fly during simulation to allow monitoring of the simulation and, to a certain extent, controlling (e.g., the user might pause, change a few parameters, get more details about the ongoing simulation, stop/abort, etc.). In-situ systems are algorithm-driven and not human-driven, as PDA systems are, and they have different architectures than progressive systems. For these reasons, we will not discuss them further in this book.

In this chapter, we will attempt to clarify several of the concepts that are most relevant to PDA, while providing formal definitions of the main methods.

## 2.2 Concepts

In this subsection we will look at the basic PDA-related concepts, while also introducing the main elements of the PDA process, detailing its different facets and analyzed data. We will also examine Progressive Visual Analytics as a more comprehensive form of PDA in terms of type of data, interaction, and visualization. In Table 2.1, we list the main requirements for PDA systems, classified along the axes of feedback, control, result, and execution. We will refer to and illustrate these requirements along with the descriptions in the text.

### Progressive Data Analysis

The next section attempts to formally define what we mean by Progressive Data Analysis. A PDA system takes data as input and produces a sequence of *meaningful*, *partial* results (design requirements R1, R6, R7) characterized by increasing *utility*. The early *real-time* results (R3, R9) are helpful for the analysis at hand (R10, R11) and each result should be better than the previous one (sometimes after an initial
<table><caption>Table 2.1: Design requirements from the related work [119, 207, 293] for creating PVA systems in terms of the user feedback and control provided for the results and executed processes (adapted from [16]).</caption><thead><tr><th></th><th>Result</th><th>Execution</th></tr></thead><tbody><tr><td>Feedback</td><td>R1: "Provide increasingly <i>meaningful partial results</i> as the algorithm executes" [293]<br>R2: Return "<i>structure-preserving intermediate results</i>" [207], i.e., results that are structurally equivalent to the final results <i>R</i> in the sense that the same techniques for visualization and data processing can be applied to them" [207]<br>R3: Avoid interfering with users' <i>cognitive workflow</i> on updates [293]<br>R4: <i>Minimize distractions by not changing views excessively</i> during updates [293]<br>R5: Provide cues to indicate where new results have been found by analytics [293]<br>R6: Return <i>aggregated information</i> that "provides a certain aspect of intermediate results <i>R</i> without preserving the structure in full detail" [207]<br>R7: Return <i>Uncertainty</i> "concerning the final result <i>R</i> as estimated based on the available intermediate information" [207]<br>R8: Return <i>provenance</i> "information, any type of meta-information concerning simplifications made for generating <i>R</i>" [207]</td><td>R9: Show <i>aliveness</i> to "confirm that the computation is in progress" [207]<br>R10: Show <i>absolute progress</i>, "information about the current execution phase of <i>F</i><sub>p</sub> which may be qualitative (e.g., 'computing distance matrix...') or quantitative (e.g., 'iteration 12' for k-means or the number of processed data items)" [207]<br>R11: Show <i>relative progress</i>, "information about the degree of completeness of <i>F</i><sub>p</sub> which is frequently provided as a percentage or as an estimate of the remaining time" [207]</td></tr><tr><td>Control</td><td>R12: Provide <i>full interactivity</i> [119]<br>R13: Support an <i>on-demand refresh</i> when analysts are ready to explore the latest results [293]<br>R14: Allow to <i>steer the final result R</i> [207]</td><td>R15: Allow <i>cancellation</i>, "the most important type of execution control" [207]<br>R16: Allow "<i>prioritization</i> of the remaining work" [207]</td></tr></tbody></table>
phase), i.e., the progression should converge. In the following, we provide more details on real-time and convergence concepts and the related design requirements:

* **Real-time** Producing early results is a real-time activity, meaning that the result must be produced within some time constraints, typically related to cognitive aspects [R3] (i.e., not too often, so as not to disrupt the human analysis flow, nor too infrequently, so that the user does not lose focus) and human-computer interaction [R9] (not too late, which disrupts the interaction flow) [179]. A real-time system can be classified as soft, firm, or hard [280]: it is *hard* if the failure to meet a deadline results in total system failure; it is *soft* if the usefulness of a result degrades after its deadline, thereby lessening the system's quality of service; and *firm* if a small number of missed deadlines are tolerable but may degrade the system's quality of service. A PDA is a *soft* real-time system. It also allows *early termination*, in which the sequence of results is stopped before reaching an optimal result when a specific condition is met—e.g., the sufficient target value has been reached [R10], the confidence interval for the result is below a threshold [R11], an interaction triggered new computations with modified parameters [R12], the latest results are requested for refresh [R13], steering triggered recomputation [R14], computation has been canceled [R15] or re-prioritized [R16].

* **Convergence** [R1, R6, R7, R8, R9, R10, R11] PDA results form a sequence related to their provenance [R8]. There are multiple notions of convergence depending on the computed results. One typical case is convergence to a scalar value. Formally, a series of scalar results $S_i$ are convergent (Cauchy convergence criterion) if there exists a number $r$ (the limit) such that, for any small positive number $\varepsilon$ and a sufficient number of steps $N$, $|S_i - r| < \varepsilon$ for $i \ge N$. We do not expect a PDA to reach a final target value $r$ in a finite number of steps, but we expect that after a finite and *small enough* number of steps, the result will approximate the target with sufficient accuracy,<fnref n="1" /> i.e., within a *small enough* error bound (called $\varepsilon$ above) while accounting for its uncertainty [R7] to make these partial results *meaningful enough* [R1]. Moreover, further steps would make absolute progress [R10] by further reducing the approximation error, while making sufficient relative progress [R11] with each step, leading to a *significant* enough improvement of their utility.

* **Algorithmic Stability** [R9, R10, R11] Algorithmic stability implies that convergent results should change in small and consistent ways: additional

<footnote n="1">¹"Accuracy" is defined by ISO 5725-1 [138] as "the closeness of a measurement to the true value"</footnote>
data or additional iterations should not make major changes to the results. Stability may also depend on data: some progressive solutions split data into chunks, which are processed one at a time until all the data has been consumed (we call these *progressive-in-chunks*). Chunks must share the same properties so as not to bias the computations of the initial partial results. Formally, we say that data must be *stationary*, as described in Section 2.4. Algorithm stability is associated with the concept of Visual stability, which is discussed in Section 5.2.1. Note that bias and uncertainty [R7] can sometimes be evaluated and compensated for (e.g., by removing useless values or adding missing values). A stochastic definition of convergence can be considered an alternative [28], which focuses on another type of aggregated information [R6], e.g., the characteristics of the statistical distribution of intermediate results or some measure of probability defined by them. In search/gather (item 2.1) progressive systems, a progressive computation can also search for a list of values, like Google search does for web pages matching a query. In that case, convergence has yet another meaning related to the precision and recall of the returned list relative to the query. Intuitively, at the end of the progressive computation the results should be as close as possible to the result of a perfect *eager* computation.

**Research Agenda:** Questions such as what aggregated information [R6] to use; which definition of convergence to use; what is small, meaningful, significant enough to obtain converging results [R1, R7, R10, R11]; and what is the right time to maintain the cognitive workflow [R3] and aliveness [R9], are all application-dependent aspects and are part of the challenge of designing PDA systems.

<figure><img src="image_12.png" /></figure>

### Progressive Visual Analytics

The term “Progressive Visual Analytics” was introduced by Stolper *et al.* [293], who acknowledged that including progressive data analysis in the Visual Analytics context can maintain the system’s interactive capability, a key point in Visual Analytics methods. In a PVA system, “progressive results can be integrated into interactive visualizations that allow users to immediately explore partial results.” PVA is a progressive data analysis in which the user observes the sequence of visual results and can interact with those results in order to gain early insight and steer the computation. Below are some details on the main concepts:

* **Visualization [R2, R3, R4, R5, R6, R7, R8]** Derived data can be visualized, transforming the sequence of results into a sequence of visualizations. This
extension can introduce additional latency to the process and requires both a more complex definition of usefulness and additional care in displaying the results to the user. Consistency should be maintained throughout the sequence of visualizations [R2], the cognitive workflow should be maintained [R3], and distractions during updates should be minimized [R4]. For example, if a new result is signaled but that result produces a change in the visualization that is hard to perceive, then it is considered to be of questionable usefulness, as it can cause the user to lose focus on other important tasks to an unnecessary degree, and producing that visualization is a waste of resources if the change will not be noticeable anyway (see, e.g., [9]). In addition, this opens up the possibility of visually representing changes [R5], summary results [R6], and their uncertainty [R7] and provenance [R8], e.g., visually distinguishing stable elements in a cluster so that they can be tracked during progressive clustering.

* **Computational steering [R12, R13, R14, R15, R16]**. In terms of controlling the process, the analyst should have, at a minimum, control over starting, pausing, slowing down [R13], and speeding up, as well as stopping (early cancellation [R15], early completion). This can also include branching an analysis into two concurrent processes—e.g., running the same algorithm on different data, or different algorithms on the same data, to compare or interleave their results [R14]. Finally, more involved forms of steering include narrowing and refocusing [R16] the process on certain subspaces of interest within the dataset, or to stop [R15] the processing of data subspaces that are not relevant to the current task or analytic question.

PVA is probably one of the most demanding types of PDA and a great deal of effort has gone into fully defining its characteristics and requirements (see, e.g., [11, 16, 119, 207, 293]). Table 2.1 lists the main PVA requirements broken down by feedback, control, result, and execution. A more comprehensive list of requirements is available in Angelini et al. [11].

## 2.3 Definitions

**Data analysis function** The first step in characterizing the various types of computing methods related to PDA is to define a data analysis function from some data space that returns a result. In mathematics, the result does not involve time or accuracy. In computer science, a process to compute the function consumes some amount of computation time and uses a certain amount of memory. It starts with a machine state,
and progresses through several internal states until it reaches the final state. For data analysis, we differentiate between the computation parameters and the data. Thus, the mathematical analysis function becomes a computation function.

In data analysis, we can also draw a distinction between search results and other kinds of computational results in the sense that the notions of stability, convergence, and quality of a search result (e.g., quality based recall and precision) are different than those of a computational result (e.g., quality based on accuracy).

**Definition 1 (Mathematical and Computer function).** The gray boxes provide a formal view of the methods and their characteristics.

In mathematics, we define a data analysis function $f$ on $n$ values $X = \{x_1, \dots, x_n\}$ yielding a result value $r$:

$$f(X) \mapsto r$$

In computer science, a function to compute $f$ takes some amount of computation time $t$, uses an amount of memory $M$, starts with a machine state $S_1$, and ends with the final state $S_z$. Moreover, for data analysis, we distinguish the computation parameters $P = \{p_1, \dots, p_m\}$ from the data $D$ it uses as input. Without loss of generality, we represent the data $D$ with a set of data tables $D = \{d_1, \dots, d_m\}$ that the function takes as input, and the outputs it returns as results $R = \{r_1, \dots, r_o\}$. Since $R$ can be approximate, some functions can return an assessment of their uncertainty/quality, which we denote by $U$. Thus our mathematical function $f$ becomes a computation function $F$:

$$F(S_1, P, D) \mapsto (S_z, R, U, t, M) \qquad (2.1)$$

Now we use that framework to define scenarios that share common aspects with the notion of *Progressive Data Analysis*:

* Online

* Iterative

* Incremental

* Streaming

* Real-time

* Anytime

* Progressive

* AQP (approximate query processing).

For each of these, we will characterize the kind of data they use, how the data is processed, the degree to which a user can control the process, and whether or not the function will converge.
**Online methods** According to Albers [6], an online algorithm A is presented with a request sequence $\sigma = \sigma_1, \dots, \sigma_n$ that must be served in the order of occurrence with the goal of minimizing the cost associated with the whole sequence. This happens for two main reasons: additional data is not available, i.e., “in any situation where decisions must be made and resources allocated without knowledge of the future” [153] or, closer to the book’s objectives, to provide the users with a result in a shorter time, see, e.g., [117]. The latter approach dates back to the 90s as an alternative to long computing batch queries, and was mainly used to obtain aggregate values on large datasets [116]. It typically provides an estimation of the confidence about the result, e.g., the confidence interval of a mean, and reuses the previous result to compute the new one efficiently. Online algorithms are popular in machine learning (see Section 8.5) and analytics in general, in particular for handling large or dynamic data.

Essential characteristics of Online methods:

* **Data**: bounded or unbounded

* **Process**: backward-looking to the analyzed data (e.g., reuse previous computed result for computing the new one)

* **Control**: little or no control over the input

* **Convergence**: possible in the case of bounded data.

**Definition 2 (Online function).** An online function $F_o$ is related to the way the data tables D are made available to the function: $F_o$ is called iteratively with subsets $D_k$ of the input. Formally, the growth of the data tables can be modeled with a partition $\mathcal{P}(D)$ of D into z non-intersecting subsets, also called chunks $C_i$: $\mathcal{P}(D) = [C_1, \dots, C_z]$, $\cup_i C_i = D$, $C_i \neq \emptyset$ and $\forall i \neq j, C_i \cap C_j = \emptyset$. At step k, $F_o$ is called with data $D_k$ formed with all first k chunks, and the last result $R_{k-1}$ that can be reused:

$$F_o(S_1, P, C_1, R_0 = \emptyset) \quad \mapsto \quad (S_2, R_1 \approx R, t_1, M_1)$$

$$F_o(S_z, P, \cup_{j=1,z} C_j, R_{z-1}) \quad \mapsto \quad (S_{z+1}, R_z \approx R, t_z \ll t_{1,...,z}, M_z)$$

Online functions guarantee that each result $R_i$ is accurate (although sometimes less than eager functions, $R_i \approx R$). The total time $t_z$ to compute $R_z$ after $R_{z-1}$ is shorter than the total time to compute $F_o(S_1, P, \cup_{j=1,z} C_j)$ which would be $t_{1,...,z} = \sum_{j=1,...,z} t_j$ ($t_z \ll t_{1,...,z}$), however, there is no guarantee that $t_i$ is bounded.

**Iterative methods** An iterative function performs its computation through a number of internal iterations and provides a sequence of improving results at each iteration, although some extra work may be required to obtain the partial result in an externally
usable form [262]. The total time to compute the final result is usually controlled indirectly either through a tolerance parameter or a maximum number of iterations, but none of these parameters allow analysts to predict the completion time.

### Essential characteristics of Iterative methods:

* *Data*: bounded and digested in one shot

* *Process*: repeated passes over the same data (e.g., k-means, simulated annealing, ...)

* *Control*: tolerance on accuracy or maximum number of iterations

* *Convergence*: possible on final result.

**Definition 3 (Iterative function).** An iterative function $F_{it}$ always takes the whole datasets D and returns improving results $R_i$:

$$F_{it}(S_1, P, D, R_0 = \emptyset) \mapsto (S_2, R_1 \rightsquigarrow R, t_1, M_1)$$

$$F_{it}(S_z, P, D, R_{z-1}) \mapsto (S_{z+1}, R_z \rightsquigarrow R, t_z, M_z)$$

Iterative functions guarantee that the results $R_i$ will converge to the final value R, $\lim_{j \to \infty} R_i = R$, but the intermediary results may not improve at each step ($R_j \rightsquigarrow R$). There is no guarantee that $t_i$ is bounded, although the tolerance and number of iteration parameters provide some control of $t_i$.

**Incremental methods** Incremental computing [247] deals with the challenge of "[computing] the new output incrementally by updating parts of the old output, rather than by recomputing the entire output from scratch."

### Essential characteristics of Incremental methods:

* *Data*: dynamically updated

* *Process*: reuse the previous results and recompute only the ones depending on updated data

* *Control*: possible on the input

* *Convergence*: not guaranteed.
**Definition 4 (Incremental Function).** An incremental function $F_{in}$ is such that the data $D_z$ at iteration $z$ is obtained by updates $\Delta$ on previous data $D_{z-1}$ explicitly considering added, deleted, and changed elements:

$$F_{in}(S_1, P, D_1, R_0 = \emptyset) \mapsto (S_2, R_1, t_1, M_1)$$

...

$$F_{in}(S_z, P, \Delta(D_{z-1}), R_{z-1}) \mapsto (S_{z+1}, R_z, t_z, M_z)$$

There is no guarantee that $i$ is bounded, although for many incremental functions, it will be.

**Streaming methods** Streaming methods can be considered a special case of online methods for unbounded data and mainly deal with memory usage and time constraints, as discussed in [212]: “in the data stream scenario, input arrives very rapidly, and there is limited memory to store the input. Algorithms have to work with one pass over the data (most of the time), space less than linear in the input size, or time significantly less than the input size.”

Due to real-time constraints, streaming algorithms can sometimes compute rough approximations of their results, and in general, streaming algorithms are difficult to design and implement. It is worth noting that the sequence of results is the consequence of the real-time constrained sequential nature of the data stream and its limited memory, not an artifact of the process as with *iterative* or *incremental* methods. Nor is it the result of the need to anticipate a final result, as the stream may never end. In many cases, the computation performed over the course of a stream focuses on the most recent values, e.g., they operate on a *sliding time window*, not the whole data history.

Essential characteristics of *Streaming* methods:

* *Data*: stream inherent to the data, possibly unbounded, ordered by time

* *Process*: real-time, backward-looking to the analyzed data (e.g., density kernel estimation, mean, etc.); use of a sliding window, very often only a single pass over the data is possible with limited memory and computational resources

* *Control*: no control over the input

* *Convergence*: not guaranteed.
**Definition 5 (Streaming function).** A streaming function $F_s$ only takes the chunks $C_i$ and not the whole dataset; it is sometimes called a delta. The maximal size of a chunk can be limited by the algorithm.

$$ 
\begin{aligned}
F_s(S_1, P, C_1, R_0 = \emptyset) &\mapsto (S_2, R_1, t_1 \le T_{bnd}, M_1 \le M_{bnd}) \\
\vdots & \\
F_s(S_z, P, C_z, R_{z-1}) &\mapsto (S_{z+1}, R_z, t_z \le T_{bnd} \ll t_{1\dots z}, M_z \le M_{bnd})
\end{aligned}
$$

The intermediate results $R_i$ may be inaccurate, so $R_z \approx R$. The total time $t_z$ to compute $R_z$ after $R_{z-1}$ is much shorter than the total time to compute $F_s(S_1, P, \bigcup_{j=1,...,z} C_j)$, which would be $t_{1\dots z} = \sum_{j=1,...,z} t_j (t_z \ll t_{1\dots z})$. Streaming functions are real-time, so $t_i$ is bounded ($T_{bnd}$), and the memory $M_i$ used by $F_s$ is also bounded ($M_{bnd}$).

**Real-time methods** Real-time approaches deal with the constraint of producing the output within a predefined time frame (sometimes called quantum) and are agnostic on what method is used. However, it should adapt its behavior to optimize the result quality according to the available time. But they cannot guarantee that a useful result is returned at each intermediary step (e.g., unknown time of interruption).

Essential characteristics of *Real-time* methods:

* *Data*: bounded data

* *Process*: optimize the computation according to the available quantum

* *Control*: pull model depending only on the time constraint

* *Convergence*: must always produce a result within the quantum.

**Definition 6 (Real-time function).** A real-time function $F_*$ produces an output within a predefined bounded time $T_{bnd}$ independent on the method $F_*$ itself:

$$ F_*(S_z, P, D_z) \mapsto (S_{z+1}, R_z \rightsquigarrow R, t_z \le T_{bnd}, M_z) $$

**Anytime methods** According to [103], “anytime algorithms are algorithms that trade performance for time. As the amount of time is increased, the quality of the output that an anytime algorithm returns increases. An anytime algorithm is supposed to return a valid solution even if it is interrupted before it ends.” Anytime is an observational feature and shares with *Bounded time* the characteristic of not being tied to any particular implementation [347]. Both online and iterative methods can be used to implement an Anytime algorithm. Moreover, Anytime algorithms have no concept of steps or iteration. They do not *push* their results, but rather can be *queried* at any time for the latest, most accurate result.
Essential characteristics of *Anytime* methods:

* *Data*: bounded or unbounded

* *Process*: returns a meaningful answer on demand based on what has been processed up to that point

* *Control*: pull model that can be interrupted and queried at any time

* *Convergence*: quality cannot decrease.

**Definition 7 (Anytime function).** An anytime function $F_*$ gets queried at any time $q$ for the latest, most-accurate result:

$$F_*(S_q, P, D_q) \quad \forall q \quad \mapsto \quad (S_{q^+}, R_q, t_q, M_q)$$

**Progressive methods** Unlike the previous methods, progressive methods are designed to deliver results for analysts at a controlled pace and with controlled accuracy. They are *real-time* methods that deliver increasingly-accurate results over large quantities of input data. PDA methods allow steering [210], meaning that the input data and computation parameters can change without always triggering a full restart. They aim to bound computation time, ensuring that new results arrive under a *quantum*. Like *online*, *iterative*, and *anytime* methods, progressive methods should guarantee results with increasing quality over time (after some point).

In contrast to *streaming* methods, the sequence of results associated with the analysis of a progressive method is not significant, and the incomplete results are seen not as a time window but as a partial result. We call *progressive computation* the use of progressive functions to run complete programs, sometimes called *pipelines*, in data analysis and machine learning.

We refer to the *quality* of a progressive result as the degree to which any given partial result is a good approximation of the final result (see also *Definition 11*). In some circumstances, we can compute *quantitative, bounded uncertainty* on an approximation. In many cases, however, uncertainty cannot be computed, but users still need an assessment of how good the approximation is.

Essential characteristics of *Progressive* methods:

* *Data*: bounded data

* *Process*: similar to *online* and *streaming* approaches

* *Control*: over input (order and parts of the data), delivery time, and quality of intermediate results

* *Convergence*: sequence of results improves over time; bias and uncertainty are evaluated and can be compensated for.
**Definition 8 (Progressive function).** A progressive function $F_p$ takes the following form:

$$F_p(S_1, P_1, D_1, R_0 = \emptyset) \mapsto (S_2, R_1 \approx R, t_1 \le T_{bnd}, U_1, M_1)$$

$$F_p(S_z, P_z, D_z, R_{z-1}) \mapsto (S_{z+1}, R_z \approx R, U_z, t_z \le T_{bnd}, M_z)$$

It delivers its results when called with increasing input data but will also work on changing input data, so there is no constraint that $D_i \subset D_{i+1}$. It provides a bounded-time guarantee $T_{bnd}$ at the cost of a potentially low-accuracy estimate $R_i \approx R$. Moreover, progressive functions should guarantee that the results $R_i$ converge to the real value $R$ ($R_i \rightsquigarrow R$). Ideally, progressive functions should return an assessment of their quality $U$. Additionally, input parameters $P_i$ can be modified between each call, and each call will provide an estimate of the result $R_i$ that can be inaccurate. Progressive functions are similar to online functions when $D_i$ is growing, and similar to iterative functions when $D_i$ is constant. They also reuse the previous result $R_{i-1}$ to improve it and keep it as stable as possible.

**Approximate Query Processing** Approximate Query Processing (AQP) is a database technique that, given a specified maximum delay, returns approximate results to standard queries, usually in a fraction of the time needed for computing exact results. It also relies on sampling and is similar to a progressive function run for a given specified time. One of its main advantages is that it behaves like a standard function, with one call returning the results. It fits well in the existing eager function paradigm and can be directly integrated into an existing analytical pipeline. Yet, while users receive a result in a bounded time, the uncertainty may be too large to make any decisions, leaving the user with the single option of re-running the AQP query with a longer delay.

Essential characteristics of AQP methods:

* *Data*: bounded or unbounded

* *Process*: real-time, sampling

* *Control*: time is controlled and uncertainty bounds are returned (sometimes the other way around)

* *Convergence*: convergence is not guaranteed, but a quality is returned.
**Definition 9** (Approximate Query Processing Function).

$$F(S_1, P, D) \mapsto (S_z, R, U, t, M) \qquad (2.2)$$

AQP functions have real-time guarantees with no guarantee of the accuracy of the result R, but they also return an uncertainty U regarding the result.

## 2.4 Progressive-in-chunks and Progressive-in-iterations

Progressive functions, algorithms, and programs rely heavily on sampling to achieve their goal: to provide meaningful estimates to the user at a bounded pace. They mainly use two strategies: chunking and iterations. For example, a progressive function that computes the average of a very long table of values will rely on splitting the table into chunks and updating the returned average with each chunk. The “average” is easy to compute chunk by chunk using Welford’s online algorithm [327]; we call this family of algorithms *progressive-in-chunks*.

To be efficient and unbiased, the chunks should be built as lists of random samples without replacement of the dataset, i.e., **shuffled**. If the samples are not *independent and identically distributed* (iid), the convergence of most algorithms will be slower. More generally, the data should be **stationary**: its unconditional joint probability distribution should not change when accessed earlier or later in the sampling process. For example, if you are computing the average temperature in NYC based on weather data sorted chronologically starting in January (i.e., not shuffled), the initial temperature estimates will be low, but they will then rise through August and eventually become too high before averaging out by the end of the year. An important concern with progressive systems is thus to make sure that data is processed in random order (i.e., shuffled). **Research Agenda:** It can be challenging, however, to make sure that data arrives in a random order in real applications (see Section 3.5.1).

Alternatively, many algorithms are iterative, producing improved estimates of their result by iterating through all of the data until a final result is obtained. For example, the gradient descent functions used in machine learning are iterative (Newton’s method, stochastic gradient descent, k-means, etc.). We call this family of algorithms *progressive-in-iterations*. *Progressive-in-chunks* algorithms can always be used whether the data arrives in chunks or is available upfront, since it can be split if necessary to match the desired progressive quantum. Unfortunately, iterative algorithms cannot always become progressive when data is large, even when it
<table><caption>Table 2.2: Summary of the different methods of computation detailed in Section 2.3. S stands for internal states, P for parameters, D for data, C for data chunks, R for results, t/T for time, M for memory, and U for uncertainty/quality.</caption><thead><tr><th>Method</th><th>Computation function</th><th>Output</th></tr></thead><tbody><tr><td>Generic</td><td>F(S<sub>1</sub>, P, D)</td><td>→ (S<sub>z</sub>, R, t, M)</td></tr><tr><td>Online</td><td>F<sub>o</sub>(S<sub>z</sub>, P, ⋃<sub>j=1,z</sub> C<sub>j</sub>, R<sub>z-1</sub>)</td><td>→ (S<sub>z+1</sub>, R<sub>z</sub> ≈ R, t<sub>z</sub> ≪ t<sub>1...z</sub>, M<sub>z</sub>)</td></tr><tr><td>Iterative</td><td>F<sub>it</sub>(S<sub>z</sub>, P, D, R<sub>z-1</sub>)</td><td>→ (S<sub>z+1</sub>, R<sub>z</sub> ↛ R, t<sub>z</sub>, M<sub>z</sub>)</td></tr><tr><td>Incremental</td><td>F<sub>in</sub>(S<sub>z</sub>, P, Δ(D<sub>z-1</sub>), R<sub>z-1</sub>)</td><td>→ (S<sub>z+1</sub>, R<sub>z</sub>, t<sub>z</sub> ≤ T<sub>bnd</sub> ≪ t<sub>1...z</sub>, M<sub>z</sub> ≤ M<sub>bnd</sub>)</td></tr><tr><td>Streaming</td><td>F<sub>s</sub>(S<sub>z</sub>, P, C<sub>z</sub>, R<sub>z-1</sub>)</td><td>→ (S<sub>z+1</sub>, R<sub>z</sub> ↛ R, t<sub>z</sub> ≤ T<sub>bnd</sub>, M<sub>z</sub>)</td></tr><tr><td>Real-time</td><td>F<sub>*</sub>(S<sub>z</sub>, P, D<sub>z</sub>)</td><td>→ (S<sub>z+1</sub>, R<sub>z</sub> ↛ R, t<sub>z</sub> ≤ T<sub>bnd</sub>, M<sub>z</sub>)</td></tr><tr><td>Anytime</td><td>F<sub>*</sub>(S<sub>q</sub>, P, D<sub>q</sub>)</td><td>∀q → (S<sub>q</sub><sup>+</sup>, R<sub>q</sub>, t<sub>q</sub>, M<sub>q</sub>)</td></tr><tr><td>Progressive</td><td>F<sub>p</sub>(S<sub>z</sub>, P<sub>z</sub>, D<sub>z</sub>, R<sub>z-1</sub>)</td><td>→ (S<sub>z+1</sub>, R<sub>z</sub> ≈ R, U, t<sub>z</sub> ≤ T<sub>bnd</sub>, M<sub>z</sub>)</td></tr><tr><td>AQP</td><td>F<sub>AQP</sub>(S<sub>1</sub>, P, D)</td><td>→ (S<sub>z</sub>, R<sub>z</sub> ≈ R, U, t ≤ T<sub>bnd</sub>, M)</td></tr></tbody></table>

is available upfront, as one iteration can exceed the quantum. Many articles on progressive algorithms describe ways to adapt iterative algorithms to chunking [142, 233], their characteristics, and their limits. **Research Agenda:** More research is needed to develop general strategies for adapting iterative algorithms to be applicable to data arriving in chunks. Some *progressive-in-iterations* algorithms can resort to *mini-batch* sampling to scale up. Instead of iterating multiple times over the entire dataset, these algorithms iterate over small *random samples with replacement* (e.g., [242,272] and more generally Mini-Batch stochastic gradient descent [173]).

<figure><img src="image_13.png" /></figure>

Other strategies exist in addition to these two main ones [124,126], but they remain rare. **Research Agenda:** More research is needed to identify and categorize sampling strategies that are usable by progressive algorithms, and assess their efficiency.

<figure><img src="image_14.png" /></figure>

## 2.5 Summary

The goal of this section was to present some of the main concepts, design requirements, and methods that share similarities with Progressive Data Analysis.

In Section 2.2, we presented important concepts related to data, real-time, convergence, visualization, and steering, and the design requirements of these concepts that need to be considered when designing PDA and PVA systems, as summarized in Table 2.1. Then, in Section 2.3, we proposed more formal and descriptive characterizations for *Online*, *Iterative*, *Incremental*, *Streaming*, *Real-time*, *Anytime*, and
<table><caption>Table 2.3: Summary of the determining characteristics of each method detailed in Section 2.3. The desirable characteristics of a progressive method are in bold font. Control requires that the method return meaningful results [R1] any time it is interrupted, converging in some way [R10, R11]. There are additional requirements regarding the timing of these interruptions [R3, R9], and all types of control requirements [R12–R16] depend on such interruptions happening. Other requirements [R2, R4–R8] are related to the nature of the results, and their delivery to the user, and do not impact this classification.</caption><thead><tr><th>Method</th><th>Data</th><th>Control<br/>→[R3,R9,R12-R16]</th><th>Convergence<br/>→[R1,R10,R11]</th></tr></thead><tbody><tr><td>Online</td><td><strong>bounded or not</strong></td><td>no</td><td>possible if bounded data</td></tr><tr><td>Iterative</td><td><strong>bounded</strong></td><td>only on start</td><td>possible on final result</td></tr><tr><td>Incremental</td><td><strong>bounded or not</strong></td><td>possible on input</td><td>no</td></tr><tr><td>Streaming</td><td>stream</td><td>no</td><td>no</td></tr><tr><td>Real-time</td><td><strong>bounded</strong></td><td>only at specific time</td><td>only at specific time</td></tr><tr><td>Anytime</td><td><strong>bounded or not</strong></td><td><strong>at any time</strong></td><td>improving with time</td></tr><tr><td>Progressive</td><td><strong>bounded</strong></td><td><strong>at any time</strong></td><td><strong>meaningful at any time</strong></td></tr><tr><td>AQP</td><td><strong>bounded</strong></td><td>only at specific time</td><td>approximate</td></tr></tbody></table>

*Approximate Query Processing* methods, and explained how *Progressive* methods differ from them. Their *computation function* forms are summarized in Table 2.2, and the main characteristics of each method and their relation to the progressive design requirements are summarized in Table 2.3.

Progressive data analysis is a complex and multidisciplinary activity, and its success strongly depends on considering all the relevant aspects in a holistic way: algorithms, including machine learning, visualization, uncertainty and, last but not least, the analyzed data, which is the topic of the next chapter.
# 3 Data Management

<table><tr><td>3.1 Motivation</td><td>33</td></tr><tr><td>3.2 Requirements for Progressive Data Management</td><td>36</td></tr><tr><td>3.3 Computing Progressive Results</td><td>37</td></tr><tr><td>3.4 Progressive Queries</td><td>39</td></tr><tr><td>3.5 Progressive Data Exploration Systems</td><td>42</td></tr><tr><td>3.5.1 OLA-RAW</td><td>42</td></tr><tr><td>3.5.2 ProgressiveDB</td><td>45</td></tr><tr><td>3.6 Extended Services for Progressive Data Management</td><td>47</td></tr><tr><td>3.7 Summary</td><td>48</td></tr></table>

**Authors** Florin Rusu, Carsten Binnig, and Chris Weaver

## 3.1 Motivation

Visualization is used for skimming through data quickly, searching for patterns along various dimensions, and drilling down into details. This process entails generating sequences of visualizations and the means for the user to continuously interact within and across them. Visual delays of more than 500 ms tend to decrease both end-user activity and dataset coverage due to the reduction in the rate of user interaction [179]— which is critical for overall observation, generalization, and hypothesis generation. However, if the visualizations are progressive, higher delays are acceptable since latency does not impact the user in the same way [342]. Instead, we can try to keep the progressive quantum below that threshold and, in doing so, maintain interactivity and responsiveness.

In this chapter, we outline considerations for managing and structuring data to improve progressivity and maintain interactive response times. To illustrate how these considerations might play out, we lay out some proposed extensions to SQL that would allow it to incorporate expressions of progressivity.

**Limitations of Existing Systems** We begin by considering the implementation of a progressive system over a traditional relational database. Existing data management
solutions for data exploration, especially those built on relational databases, have
severe limitations across the entire stack in such a case.

We note two different time restrictions. Before the first query is executed, data
must usually be loaded or processed in the data management system. This can be
a slow process and often entails creating a series of indexes or other statistics to
optimize later querying. Second, each query may run slowly on loaded data.

To reduce upfront database loading costs, in-situ data processing systems have been
recently introduced. They are extensions of external tables supported by standard
database servers. Although external tables avoid loading, the system has to access
the entire data for each query, which can lead to poor performance over a sequence
of diverse queries. A series of adaptations have also been developed to address
these challenges. For example, NoDB [3] and SCANRAW [49] are query-driven
in-situ processing systems that improve their performance progressively and converge
to the database execution time by loading all of the data. These systems execute
SQL queries directly over raw data while optimizing the conversion process into
the format required by the query engine. This optimization eliminates loading and
provides instant access to data, thus allowing exploration to begin immediately. These
systems also provide a dynamic trade-off between the time to access data and the
query execution time by adaptively loading a portion of the data during processing.
This allows for progressively improved query execution times while reducing the
amount of storage needed for replication. All of these in-situ database systems are
data-agnostic; as such, they cannot be optimized to discard irrelevant data early
in the exploration. As a result, valuable CPU and storage resources may be used
inefficiently. **Research Agenda:** We need to develop models of relevance and strategies
for optimization based on them.

Existing eager database systems are also ill-suited to the workloads that result from
interaction in visual exploration tools. When a dataset becomes large, computing
results, even for a single visualization, can take seconds—or even minutes—creating
a significant barrier to interactivity [21]. As we note in Chapter 1, one promising
approach for computing approximate results is using a family of systems that esti-
mates such results based on a sample of the data. By using a sample much smaller
than the overall dataset, these systems greatly reduce the execution time of a query.
These samples can be fixed-size offline samples, as used in BlinkDB [2] or Ver-
dictDB [223], or *online aggregation* (OLA) [117], which uses progressively larger
samples extracted online during query execution. These estimation techniques define
a principled method of computing an estimation and confidence bounds for several
SQL aggregation operators. Existing OLA solutions have strict requirements imposed

<figure><img src="image_15.png" /></figure>
by the sampling procedure. Data shuffling or random access by row are considered
the standard procedure for extracting samples of progressively increasing size from
a dataset. Shuffling generates a permutation of the data as a query preprocessing
step such that a runtime sequential scan results in random samples of increasing
size. However, shuffling creates a secondary copy of the data and requires significant
processing time, even more than loading. To date, online aggregation has not been
implemented in any commercial database system. **Research Agenda:** We should find
ways to incorporate progressive aspects into commercial database systems.

Another obstacle is that eager query processing prohibits progressive result gener-
ation. For example, query processing can make use of so-called blocking operators,
such as certain implementations of “join” (e.g., hash join) or “group-by”. Such
operators require processing all of their inputs before producing any output tuple.
This has led to the development of non-blocking operators, such as hybrid-hash join,
which generate result tuples much earlier—and do so continuously. Their functioning
principle is to operate on blocks—or chunks—of tuples that are processed by all
the operators in the query execution plan at once. This is identical to performing
the entire query on a subset of the data, i.e., the selected blocks or chunks. While
a partial result is generated, the important question is, “What is the significance of
this result?” In the case of queries that produce tuples where the output order does
not matter, the partial tuples are satisfactory. For queries that compute grouping
aggregates, the partial tuples have to be statistically significant in order to produce
a meaningful estimate of the result. This is done by taking random samples from
the base tables and performing the subquery on them. The process can be repeated
multiple times, with a partial result generated each time. These results are progressive
only to the extent that the estimate is refined with each additional subquery executed.
This will not be the case if the subqueries are independent. The operator state must be
preserved across subqueries such that each subsequent subquery can “build” on top
of the previous ones. Since this is not done by any of the existing database engines,
architectural changes are required. **Research Agenda:** There are opportunities to
design new architectures to support progressive subqueries.

Lastly, in interactive data exploration, users often want to quickly refine a query.
For example, a user may supply a succession of different ranges to a filtering predicate.
In current databases, each such user interaction results in a completely new SQL
query that has to be evaluated from scratch. This results in a high overhead on
system performance. In the typical use of a data exploration system, we can expect
many queries to be closely related: a user might adjust just one or two parameters
at once. That will lead to a sequence of closely related queries. Ideally, results and

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>
intermediate states from previous queries should be used to improve the performance of similar queries. An example of a non-progressive system that uses this insight is Falcon [206], which precaches related queries so that the user can modify the data interactively.

## 3.2 Requirements for Progressive Data Management

We are considering a data management architecture for progressive computation that aims to support interactive data exploration through visualization. At a general level, our goal is to define the requirements for an architecture akin to a “Progressive Tableau” [297]. Visualization is the next step in the pipeline, consuming the results of the database engine. Thus, the interaction between the visual user interface and the computing engine is realized through standard SQL queries that are executed over relational data, i.e., tables.

The visualization requirements for progressivity have to be included in all of the elements of the dashboard interface. Results of long-running queries should be returned progressively for interactively “continuous” display. Partial (approximate) results make sense when they are statistically meaningful. Progressive results can be materialized in an evolving time series to provide continuity. The query itself should be allowed to evolve based on the progressive results. This evolution can take the form of minor changes to the original query or the triggering of related new queries. The refinement process generates a hierarchy of queries connected through their lineage. The end-user analyst can further interact with these queries in two ways: they can monitor the execution by inspecting the progressive results, and they can steer the query hierarchy by stopping uninteresting queries and adding derived queries.

In addition to its functional requirements, a visualization design can impose strict response time constraints that are highly dependent on particular graphical widgets and how they parameterize queries. For example, the movement of a slider may elicit “immediate” response times lower than 100 ms, while the pressing of a button may increase the acceptable feedback time to 1 second. If a custom text entry is required, feedback time may be as long as 10 seconds [281]. Such “time engineering” constraints can affect the design of progressive execution by making some graphical widgets more suitable to be included in progressive visualization and disqualifying others (Section 7.1).

Given the functional specification and performance constraints, we outline a data
management architecture for progressive computation. Rather than design a novel
architecture from scratch, we embed progressivity in a modern relational database
accessed through SQL. There are two solutions for realizing this approach. First,
a middleware that sits between the visual interface and the database engine can
implement progressivity by intercepting queries and splitting them into smaller,
partial subqueries. This is a completely non-intrusive solution. The second approach
requires changes to the database operators and tackles the situations that cannot
be handled at the middleware layer. Independent of the approach, the progressive
architecture has to provide support for progressive results and progressive queries.
These support aspects, together with specific systems, are discussed in the following
sections.

**3.3 Computing Progressive Results**

Based on these functional constraints, we can now look at technical approaches that
address each of these issues.

**Index-based sampling** The XDB system [172] offers a possible approach in how it implements the WanderJoin algorithm [242] in the PostgreSQL database. XDB provides online aggregation-style estimates which improve progressively. The progressivity integration exists at all levels of query processing, including optimization and execution. A progressive query is specified, for example, as follows:

```sql
SELECT ONLINE SUM (l_extendprice*(1-l_discount)), COUNT(*)
FROM customer, orders, lineitem
WHERE c_mktsegment='BUILDING' AND c_custkey=o_custkey AND
      l_orderkey=o_orderkey
WITHINTIME 20000 CONFIDENCE 95 REPORTINTERVAL 1000
```

<caption>Listing 3.1: Example: SQL Progressive Query</caption>

This online aggregation query tells the database engine to report estimations and associated confidence intervals, calculated with a 95% confidence level, with a progressive quantum of 1,000 milliseconds, for up to 20,000 milliseconds. In this case, the partial results—consisting of an estimate and its confidence intervals—are managed by the database engine and pushed progressively to the visualization client.

Another alternative is to allow the client to pull new results by itself. Rather than
always transferring the complete result, it is also possible to send only the difference,
i.e., *delta*, from the previous result.
To execute the query efficiently, B+-tree indexes can be built on all of the attributes having selection predicates and on all of the join attributes. This allows for all of the blocking operators to be transformed into non-blocking operators; thus, `GetNext()` from the query execution tree root can be pushed to a single table. Because there is an index, `GetNext()` retrieves samples from this table that satisfy the selection predicate efficiently. Joins become index lookups using the indexes built for each join attribute. As more samples are extracted from the source table, the accuracy of the progressive results increases. This requires maintaining the state of the estimate as well as the state of the aggregate.

**Independent sampling** Another strategy for progressive result generation is to extract samples from each of the source tables and execute the complete query over the samples. A middleware architecture is likely more appropriate in this case, with the database providing minor support. State has to be maintained by the middleware between queries for improved results. This requires efficient sampling from the source tables. In PostgreSQL, this can be done by selecting all tuples stored in the same block—information which is available in the catalog. For sampling *without* replacement, a block has to be accessed only once and this can be controlled by the middleware. To provide accuracy guarantees, the middleware can implement statistical techniques such as CLT-bounds or bootstrap.

**Deterministic approximations** Sampling poses drawbacks for aggregates such as maximum and minimum because no estimates and bounds can be derived from a sample; there is no tangible relationship between the maximum/minimum in the sample and the global maximum/minimum. The term “deterministic” indicates that the bounds are always guaranteed to contain the true value, unlike confidence bounds. Existing work on deterministic approximations [144, 239] demonstrates that this can be achieved by processing only a data subset—or data permutation—as long as the data is sorted in a certain order. For example, the maximum can be determined easily by accessing a single data item if the data is sorted in descending order. In the case of additional predicates and joins, more items may need to be accessed. Creating an “interesting” order is akin to extracting a sample and can be performed by creating a complete copy of the data or an index on it. The deterministic bounds can then be derived by executing a binary search operation on the “interesting” order.
**3.4 Progressive Queries**

Producing and visualizing the results of a single query in a progressive manner is by no means the only role of progressivity in visual data analysis. Because the results of a long-running query are produced and presented in a progressive fashion over the entire course of a query's execution, users can monitor the extent to which the evolving results are yielding analytical insights, and intervene to steer their analyses at any point. Users perform their steering actions via the respective interaction mechanisms in the visualization interface, i.e., panning and zooming, selecting regions, adjusting sliders, adding/removing attributes, etc. These actions result in modifications of the currently running query to produce the required data. Modifications to a query can include changing predicate boundaries, adding or removing filters, adding or removing result attributes, adding or removing group-by clauses, i.e., drill-down and roll-up, and adding joins for pivoting. Note that progressive joins are particularly challenging to implement correctly, as explained in several articles [106, 241, 242].

Other additions to the SQL language could expose query changes to the database engine. For instance, the language could allow queries to refer to past queries so that they can be interpreted as iterations of each other. One possible solution would be to add the ability to name queries, along with the addition of an `ALTER QUERY` statement to SQL. For example, suppose we wanted to remove the predicate on the customer table in the query introduced in the previous section—named Q1—we might write the following statement:

```sql
ALTER QUERY Q1 WHERE: DELETE c_mktsegment='BUILDING'
```

<caption>Listing 3.2: SQL `ALTER QUERY`</caption>

**ALTER QUERY** One naive approach to implementing progressive queries is to stop the running query—preferably whenever a result chunk has been produced—and start the execution of the revised query. While semantically correct, this approach does not explicitly convey the information to the database engine that the original query and its modified version are related—let alone how. Consequently, the queries are treated independently, even though they share common results. A more effective approach is to refine the previous results and devise a method to combine the new results with the old ones. Moreover, the execution of the derived query should also be optimized based on the previous queries. For instance, the modification to query Q1 given in the example `ALTER QUERY` statement could be handled by performing Q1 with the predicate `c_mktsegment<>>'BUILDING'` and then summing-up this estimate
with the progressive result of Q1 computed up to the query change. This choice may
be optimal if the number of ‘BUILDING’ tuples is large, thus allowing them to be
pruned away before the costly join. Another option is to perform both Q1 and its
modification—essentially, a group-by on `c.mktsegment` with two groups—and then
summing the results. Which of the three alternatives—the third being the execution
of the modified query from the start—is more efficient will depend on many factors,
such as the time when the transition occurs, the quality of the Q1 estimate, the data
distribution, etc. A progressive architecture should at least be aware of all these
options and consider them in a meaningful way when a query is modified.

**FORK QUERY** The progressive architecture we envision allows users to not only execute a single query in a progressive manner, but also to expand their data exploration by issuing additional related queries, which can also be executed in a progressive manner. In this case, the system is making sure that all the progressive queries are collectively optimized and executed. We illustrate this functionality with the following example. Consider a user who explores a census dataset and starts by issuing a progressive SQL query to get overall statistics on the gender distribution. Initial results show that the distribution is heavily skewed towards females, so the user decides to issue a second progressive SQL query to find out the distribution of females over different geographic areas. This distribution, being uniform, prompts the user to issue a third progressive query that computes the distribution of females for different age groups. At this point the system is running three progressive queries in parallel, the last two of which are dependent on the first one. Notice, though, that they do not replace the original query—they run alongside the original query. This difference is captured in SQL with the `FORK QUERY` statement, which permits more extensive changes compared to `ALTER QUERY`. Essentially, `FORK QUERY` creates a graph of query dependency relationships that must all be satisfied.

The system is responsible for creating and running a query execution plan that includes all the queries in the graph, thus optimizing overall system resource usage. This is a complicated problem because several decisions have to be made. First, the queries have to be prioritized. A simple approach is to give preference to the newer queries over the older ones. While this makes sense if we assume that the attention span of the user is skewed towards the immediate past, we may miss or delay significant trends for the older queries. The second decision is to extract the queries that can be processed concurrently and assign them the required resources. The end goal is for the user to make quick progress on their data exploration and analysis tasks, which is possible since they are able to quickly formulate and check
different hypotheses without having to wait for each query to finish execution.

Fork queries enable the *parallel creation and processing of related queries*, a good strategy to conduct progressive data analysis when latency is guaranteed but the wait time to make a decision can be long.

**Speculative queries** The approach of progressive multi-queries can be advanced one step further by speculating on what the results of the next query might look like. For example, consider a progressive histogram over an attribute of a table in the database. An initial progressive histogram result may be coarse-grained, with a fixed number—say 2 or 10—of bins. Progressive results may consist of finer-grained bins, such as increasing from 2 to 4 or from 10 to 100 bins. The Falcon system [206] computes its bins progressively this way. We can speculate that such a finer-grained histogram will be requested and begin processing through a speculative forked query of the initial query. Since the overlap between the two queries is significant, most of the computation can be reused across them. If the database had known that the client was going to change the query in this way or a similar way, the database could have served more accurate results faster by scheduling and beginning the execution of the forked query before the client even launched the query. In the course of executing progressive queries, there is a clear expectation that subsequent queries will be made to the database. Moreover, these queries are likely to be similar to the queries before and after. This similarity may come in many forms, for example, a changed `WHERE` clause parameter, group-by attribute, or addition or removal of a `WHERE` clause. As such, the progressive architecture can “learn” the query sequence from past user sessions and predict the next queries in the sequence with high probability. **Research Agenda:** The next step is to incorporate such predicted queries into the query graph and schedule them for processing. This can be easily achieved within the progressive multi-query architecture by setting the priorities accordingly.

<figure><img src="image_18.png" /></figure>

Rusu *et al.* [260] present a solution for generating speculative queries based on a template for model calibration using the gradient descent (GD) algorithm. While all these queries have the same structure, they are parameterized with different values for the hyperparameters of the GD algorithm. The group of queries are executed concurrently in parallel and progressively probed. The hyperparameters that are identified as suboptimal are progressively pruned and replaced with more promising values.
**3.5 Progressive Data Exploration Systems**

In this section, we present two progressive prototypes for interactive data exploration—OLA-RAW [50] and ProgressiveDB [23]—that implement the concepts discussed in the previous sections. While OLA-RAW provides specialized database operators inside the query execution engine, ProgressiveDB is a middleware that is implemented on top of an existing database.

<figure><img src="image_19.png" /><figcaption>Figure 3.1: OLA-RAW architecture</figcaption></figure>

**3.5.1 OLA-RAW**

Figure 3.1 depicts the super-scalar pipeline architecture of OLA-RAW. Chunks of adjacent tuples are read from the raw file and passed for extraction to a pool of worker threads that are dynamically assigned work. An extraction thread converts the assigned chunk from the file format into the internal representation of the execution engine. The amount of work executed by an extraction thread varies across file formats. In order to compute an estimate and corresponding bounds, the OLA sample estimator has to be provided with a provably correct sample from the original file. Due to the asynchronous execution of the extraction threads, this is not trivial. Moreover, as more chunks and samples are extracted, the bounds of the estimate have to improve progressively. OLA-RAW carefully orchestrates the execution of each component of the system by making it sample-aware.
**Bi-level sampling** OLA-RAW performs estimation based on bi-level samples [107] which are a generalization of block-level sampling. Chunks are read in a predetermined random order by the Shuffle Read module shown in Figure 3.1. However, instead of aggregating all the tuples in the chunk into a single value that becomes a surrogate for the chunk, a secondary sampling process is performed over the tuples in the chunk. This is realized by randomly shuffling the order in which tuples are extracted. Independent orders are used across chunks by initializing a pair of random seeds for each Code-Generated Shuffle Extract. To cope with data structure and query variety and make sampling efficient, the code in Shuffle Extract is dynamically generated from a template corresponding to a file format, e.g., CSV, JSON, or FITS. The template takes as parameters the schema, the columns accessed by the query, and the random seeds. At each step during processing—in OLA Sample Estimator and Shuffle Extract—the set of sampled tuples correspond to a bi-level sample. This allows for estimates to be computed at any point—not only at chunk boundaries. Moreover, the sample size can be increased either by including more chunks—requiring more I/O—or more tuples inside a chunk—requiring more CPU. This provides more control over the resource utilization in raw data processing, which is known to vary significantly across file formats.

**OLA Sample Estimator** The role of OLA Sample Estimator is to coordinate and monitor the execution of the Shuffle Extract instances. First, it has to gather the samples from all the instances such that they form a sound bi-level sample used for estimation. Given the asynchronous execution, this is not trivial because the inspection paradox can invalidate the sampling procedure. OLA Sample Estimator addresses this issue by implementing a timing-based procedure. Each Extract thread is configured with a timing parameter that specifies when samples from the chunk have to be produced. This is achieved by forcing the Extract instances to push their samples to OLA Sample Estimator at each timing interval. Since chunks are scheduled for extraction sequentially, this guarantees that samples are extracted in order. The number of tuples included in the sample, however, can vary based on the properties of the chunk.

Second, OLA Sample Estimator has to determine the minimum number of tuples to extract from each chunk in order to optimally achieve convergence based on the available resources. This problem cannot be solved if one does not have complete knowledge of the data distribution, which is the case in raw data processing. As such, we design a resource-aware sampling strategy that dynamically and adaptively determines how much to sample from a chunk by continuously monitoring the
<figure><img src="image_20.png" /><figcaption>Figure 3.2: ProgressiveDB architecture</figcaption></figure>

resource utilization—I/O bandwidth and CPU threads—of the system. We monitor the number of text chunks produced by Shuffle Read and the pool of threads available to Shuffle Extract each time an estimate is generated. This is the same timing parameter required to avoid the inspection paradox. As long as the number of threads is larger than the number of text chunks, processing is I/O-bound. Otherwise, it is CPU-bound. For I/O-bound processing, our goal is to end a chunk as soon as another chunk becomes available and there are no threads in the pool. In the case of CPU-bound tasks, the goal is to finalize a chunk as soon as accuracy is satisfied. We achieve these goals by carefully controlling the timing parameter at which samples are produced.

**In-memory Sample Synopsis** We build the in-memory bi-level sample synopsis following a process similar to reservoir sampling [58,317]. The chunks are considered for insertion in the random order in which they are extracted for estimation. As long as the memory budget is not exhausted, all the tuples extracted from a chunk are added to the synopsis, organized based on chunks. Complications arise when the memory budget is exhausted. In this case, we propose a variance-driven insertion strategy. The memory budget is divided across the chunks in the synopsis proportionally to their local variance for the current query. The larger the internal variance, the more synopsis space a chunk gets. This requires dropping some of the sampled tuples inside the chunk while preserving a sample of smaller size. By following the variance-driven insertion strategy, the synopsis is guaranteed to contain a bi-level sample at any time instant. This is important because processing can finish at any moment. In the extreme case where all the chunks are included, the synopsis degenerates into a stratified sample. For this type of sampling, we can determine the optimal order in which to extract chunks in a subsequent query—the decreasing order of the chunk variance.
**3.5.2 ProgressiveDB**

The goal of ProgressiveDB [23] is to enable progressive query processing and steering
of queries without changing the underlying DBMS. Therefore, ProgressiveDB
utilizes a middleware-based approach that provides progressive query capabilities
to applications via a standard interface such as JDBC. This middleware handles all
query routing, intermediate result processing, and manages the internal state of the
progressive query execution as depicted in Figure 3.2. To support progressive query
execution, a table has to be specifically prepared and made available to ProgressiveDB
as a chunked *Progressive Table* (depicted on the right side of Figure 3.2). What is
important is that chunking can be typically implemented by simply using the partition
functions of an underlying database.

As a query interface, ProgressiveDB supports both standard SQL queries like $Q2$, which are directly executed on the underlying DBMS on the whole table, and progressive queries as shown for $Q1$ formulated in our Progressive-SQL language (which is a SQL extension). Both are handled by the *Progressive Executor* of the middleware. For executing a query $Q1$ formulated in our Progressive-SQL language, the Progressive Executor translates the incoming progressive queries into a series of sub-queries $Q1_1 - \cdots - Q1_N$ on the prepared Progressive Table. Each sub-query is executed on the underlying DBMS on a per chunk basis—typically a single partition of the table. The Progressive Executor progressively combines the partial results over individual chunks with the current state of the query execution. Each time a new sub-query has finished, the approximate overall result is updated and sent to the application. Consequently, the more of the table that is processed, i.e., the more sub-queries that have finished, the lower the relative error.

The middleware is also responsible for providing efficient execution strategies for query steering. For example, part of the SQL extensions are so-called *progressive views* that allow an application to refine an already running query with additional filtering predicates or to drill-down into its grouping categories. In such cases, the ProgressiveDB middleware manages all the necessary intermediate states needed for the refinement without having to re-run any already completed (sub-)query.

**Database Preparation** In order to be used by Progressive-SQL, a table that resides in an existing DBMS has to be prepared for progressive queries. ProgressiveDB partitions tables into chunks holding data such that each partition is small enough to be queried by an analytical query within a given query latency. An important aspect of this preparation step is that tuples are assigned randomly to each chunk so that the
individual sub-queries sent by ProgressiveDB access a random sample of the table.

Note that chunking a table can be implemented without the need to physically split and copy the data of a table in the underlying database system. Instead, if a database system natively supports partitioning (as most commercial DBMS and PostgreSQL do), ProgressiveDB makes use of this capability. The table is partitioned into *n* randomized chunks such that the average response time of a simple aggregation query is below a configured threshold latency. Note that, for most systems, partitioning is natively supported. For systems without partitioning support, a chunking column and an index on that column are used by ProgressiveDB.

**Progressive Queries** With progressive query execution, clients continuously receive approximate query results, which get progressively more accurate in approaching the final result. Clients initiate a progressive query by adding the keyword `PROGRESSIVE` to an aggregation query:

```sql
SELECT PROGRESSIVE <aggregation_list>
FROM <table>
WHERE <filter>
GROUP BY <group-by-atts>
```

<caption>Listing 3.3: SQL PROGRESSIVE Query</caption>

ProgressiveDB translates such a progressive aggregation query *Q* internally into a series of sub-queries $Q_i$ such that each sub-query accesses only a single chunk (partition) of the prepared progressive table. The results of each sub-query $Q_i$ are then combined in the middleware with the current state of the progressive query execution to produce an approximate overall aggregation result at stage *i*.

ProgressiveDB computes the aggregation approximation based on the combined result of all previous sub-queries $Q_j$ ($j < i$) and the additional partial result of sub-query $Q_i$. This is possible for all decomposable aggregation functions, such as `SUM`, `COUNT`, and `AVG`, where the result can be computed by aggregating over sub-aggregates or auxiliary aggregates for subsets of the data.

**Query Steering** During interactive data exploration, users often want to quickly refine a query, for example to further filter a result or drill-down into a result. While the progressive queries, as introduced above, provide fast (low latency) and progressive feedback to users, they do not allow the user to steer the query at runtime. With our SQL syntax thus far, refining a query would require a new query for each step, which would have to be processed by the underlying database from scratch, resulting
in both execution overhead and a delay in achieving a result accuracy comparable to
the already running query.

To facilitate the steering of progressive queries, Progressive-SQL introduces the concept of a PROGRESSIVE VIEW for which some FUTURE grouping attributes and filter conditions can be specified:

```sql
CREATE PROGRESSIVE VIEW <view-name> AS
SELECT <aggregation-list>
FROM <table>
WHERE <filter-1> (AND FUTURE <filter-i>)*
GROUP BY <group-by-atts-1> (, FUTURE <group-by-atts-i>)*
```

<caption>Listing 3.4: SQL PROGRESSIVE VIEW and FUTURE</caption>

The general semantics of a PROGRESSIVE VIEW is the same as with a progressive query: ProgressiveDB executes a series of sub-queries $Q_i$ such that each sub-query accesses only a single chunk table of the prepared database schema and progressively combines these partial results with the current query execution state into new result approximations. The executed sub-queries, however, include additional grouping attributes for each FUTURE clause from the view definition.

## 3.6 Extended Services for Progressive Data Management

When all the data processing needed by an application can be done inside a progressive database, the mechanisms described above are sufficient. For more complex analytical operations or detailed visualization, however, a large amount of data will need to be transferred progressively from the database to the analytical system. For example, when computing the multidimensional projection of a data table using the t-SNE algorithm, all the considered tuples should be moved from the database to the analytical system. Similarly, when visualizing a table as a scatterplot, all the rows should be transferred with a selection of columns mapped to the x, y axes, and possibly other columns mapped to additional visual channels. (We will discuss more constraints on visualization in Section 5.1).

In such cases, the database can be considered to be in streaming mode, in which no aggregation or grouping is performed by the database, and all the processing is performed progressively by the analytical system. The database system can nevertheless provide some support. For visualization, knowing the ranges of data values (minima and maxima) is necessary to scale those data values to ranges of visually mapped values. Similarly, knowing the distribution of data values allows
their transformation through the visual mapping to, e.g., use a log scale for the x or y axis. However, this information is not always available instantaneously. In the case of a complex query, computing the exact bounds and distribution in advance can take time, introducing latency.

Sending approximate bounds and distributions progressively is faster than having the visualization system recompute them while streaming data. However, asking a progressive database to send the bounds progressively while streaming the data should be done with care, using a fork query when one query will be I/O-bound (streaming the data) and the other CPU-bound (computing the bounds and distributions). Otherwise, the approximate bounds might not be synchronized with the data sent, and the analytical system would not visually map the data correctly for display in the visualization.

**Research Agenda:** More experience is needed to understand the level of support required between the progressive database and the analytical operations needed to avoid redundant work while freeing the analytical front-end of operations that are cheaper to do in the database.

**Research Agenda:** Many large databases are already available but are not progressive. To use PDA over the network to explore them, more progressive services are needed to provide important operations, including progressive (min, max) for a query, approximate distributions, distinct-values counts, quantiles, and possibly different levels of shuffling to trade speed for quality, to name a few.

## 3.7 Summary

In this chapter, we have presented progressive data management techniques for interactive data exploration and visual analytics. While such techniques have been developed for more than two decades, their adoption in practice is rather limited. One possible reason for this is the lack of an adequate interface to access and query data progressively, particularly for use in visualization applications. With a view to addressing that lack, we have focused here on concepts that support better integration between progressive data processing and visualization. We discuss these concepts in detail and illustrate how they are implemented in two prototypes for interactive data exploration: OLA-RAW and ProgressiveDB. The capabilities of these prototypes represent just a limited exploration of what could be a much larger and richer design space. **Research Agenda:** Considerably more work lies ahead to realize the design and implementation of a “Progressive Tableau”.
# 4 Data Structures and Algorithms

<table><tr><td>4.1 Vision</td><td>51</td></tr><tr><td>4.2 Motivation</td><td>51</td></tr><tr><td>4.2.1 Streaming and Steerable Visualization</td><td>52</td></tr><tr><td>4.2.2 Creating a Progressive Algorithm</td><td>53</td></tr><tr><td>4.2.3 Uncertainty on Aggregated Results</td><td>54</td></tr><tr><td>4.3 Basic Data Structures for Progressivity</td><td>54</td></tr><tr><td>4.3.1 Vectors, Multidimensional Arrays, and Tensors</td><td>55</td></tr><tr><td>4.3.2 Data Tables</td><td>56</td></tr><tr><td>4.3.3 Networks</td><td>56</td></tr><tr><td>4.4 Basic Algorithms</td><td>57</td></tr><tr><td>4.4.1 Broadcasting Operations</td><td>58</td></tr><tr><td>4.4.2 Linear Algebra</td><td>59</td></tr><tr><td>4.4.3 Statistical Operations</td><td>60</td></tr><tr><td>4.4.4 Data Sketching</td><td>60</td></tr><tr><td>4.5 Input and Output</td><td>61</td></tr><tr><td>4.5.1 Detailed Input</td><td>61</td></tr><tr><td>4.6 Specific Progressive Services and Strategies</td><td>64</td></tr><tr><td>4.6.1 Progressive Stability and Normalization</td><td>64</td></tr><tr><td>4.6.2 Data Change Management</td><td>65</td></tr><tr><td>4.7 Summary</td><td>67</td></tr></table>

**Author** Jean-Daniel Fekete

In the previous chapter, we examined low-level data management operations for supporting visualization and analytics front-ends. In this chapter, we move up a level of abstraction. Many data analysts today work in higher-level scientific languages. These popular scientific languages (SLs), such as Python [313], R [244], Julia [26], and MATLAB [189], are used to implement data pipelines to carry out analyses. They offer multiple layers of libraries, with standard data types such as *vectors*, *arrays*, *tensors*, *data tables* (also called *Data Frames*), and various types of *graphs* (aka *networks*). These data types support arithmetic operations, linear algebra, statistical
operations, input and output, and other more specialized operations. These libraries and data types are fundamental to any data analysis and computation, and every data analyst relies on them.

However, these standard libraries are not currently designed for progressive computation. A progressive language or platform should offer data structures and algorithms similar to SLs to achieve the same level of service and avoid the current situation where each PDA application has to re-implement all of them. This chapter explores some of the issues and challenges involved in implementing these data structures and algorithms for a progressive approach. It discusses how general algorithms and data structures that support arithmetic, linear algebra, basic statistics, and input/output methods should be adapted to become progressive. The chapters on data management, visualization, machine learning, and evaluation build on some of the mechanisms described here. Many of the issues discussed in this chapter are speculative. Our goal is to provide tips that can help the community tackle challenges now and in the future.

In the examples used here, we will follow the conventions of the Python ecosystem for Data Science, which includes NumPy [312], SciPy [147], and Pandas [193]. Other SLs provide similar mechanisms with slightly different names and options.

For our purposes here, we assume that a progressive program is made up of one or more pipelines of connected progressive functions, as shown in Section 3.5. These run sequentially or in parallel to achieve a sequence of results, which are sent to other stages of the pipeline, such as visualization or data analysis functions. Most of the stages remain alive until the entire computation is completed, contrary to eager programs where each stage runs to completion and, therefore, finishes before the next one starts. A progressive program can be represented as a directed acyclic graph of progressive functions kept alive and run multiple times until they finish processing, and possibly continuing even after that if interactive steering allows for changing data in the pipeline. A single change in an earlier part of the pipeline produced by interactive steering can trigger new computations in another part of the pipeline.

Therefore, in addition to adapting the traditional data structures and algorithms, naive progressive computation pipelines can produce a large number of recomputations, slowing down the whole process and wasting resources. Advanced progressive computations require *strategies* to avoid triggering an excessive number of recomputations.
## 4.1 Vision

When progressive data analysis and visualization become standard, data scientists using their laptops will be able to start an exploratory analysis based on data from anywhere on the internet, either from flat files or progressive databases. Loading the datasets will produce statistics (e.g., min, max, histogram, average, and quantiles) and simple visualizations in at most a few seconds, which will be progressively updated. The analyst can then apply higher-level operations to the data, including cleaning the data, computing derived values, normalizing columns, fitting data to models, or computing multiple models. At this stage, the analyst will want to monitor the results of these operations using visualizations of the derived data, but also of the quality measures, computed progressively to decide which of the chosen operations seem to be converging. All these operations should be supported by the fundamental algorithms, including the quality measures that they return and that are fed to visualizations to facilitate monitoring and decision-making.

## 4.2 Motivation

Let's start with an example: one of the simplest analytics pipelines has the following form and can be executed in Python eagerly, but also progressively:

1. `vector = read_data('huge_file.dat')`

2. `avg = mean(vector)`

3. `plot(avg)`

<caption>Listing 4.1: Example: Progressive Mean</caption>

In an eager context, this is a straightforward three-line program: line 1 reads in a single file, line 2 computes a value, and line 3 visualizes the result.

But this could also be interpreted as a dataflow in a progressive program. These eager imperative constructs are mainly a syntax that can be turned into a dataflow representation internally, so a progressive language can look like an imperative language and use the same syntax while being executed as a dataflow system. Line 1 is an input operation that can be performed progressively and will grow the vector as the file is loaded in chunks. Line 2 is a function that can be computed progressively using e.g., Welford's method [327]. Line 3 visualizes the results while it is being computed, likely with some indication of the uncertainty of the mean value as is typical in progressive systems.
The result of the progressive mean function is different from the eager one: the progressive version should return a measure of uncertainty (e.g., a confidence interval) to be visualized by the plot function, while the eager version returns only a number.

This simple pipeline, applied to a few vectors to compute a bar chart, was used as the initial example of *online aggregation* by Hellerstein *et al.* [117], and for early human-factors studies by [88, 224].

Not all operations are easy to transform into progressive form. Computing the mean progressively is easy, but computing the median, as in Listing 4.2, is more complex, since in its strictest form it requires keeping all the loaded data in memory (this is called a *holistic function* [330]). There are streaming approximate implementations of the median, using a “quantile” data sketch, although the error can be bounded [152]. This, in turn, requires that the visualization should also show the uncertainty in a way that is faithful to the approximation.

```R
1 vector = read_data('huge_file.dat')
2 med = median(vector)
3 plot(med)
```

<caption>Listing 4.2: Example: Progressive Median</caption>

### 4.2.1 Streaming and Steerable Visualization

As we noted with the median algorithm above, some algorithms that compute on data streams [97, 339] can be adapted to support PDA.

There are two major differences between data streaming algorithms and progressive algorithms: time and steering. In streams, time is intrinsically associated with data, whereas in progressive systems, it is an artifact of the algorithms and has no inherent meaning for data analysis. Many stream-based algorithms use the time explicitly to limit their computation to a time window or to decrease the importance of data as it ages. Progressive methods should not be sensitive to the order of the arrival of the data. In our previous examples, the order of the data in the file should have no impact on the final result, and the `read_data` function may load it in any order.

In PDA, steering requires the system to allow the user to modify the query without fully recomputing the data. Unfortunately, streaming systems do not support looking back at the data. Rather, they process transient data “on the fly” and build summarized intermediate representations, called “synopses” or “data sketches” [57, 58, 97], that compute approximate results and update their summarized state as data streams by.
Steerable progressive systems can also filter or update data interactively if the ana-
lyst decides to at any time—something stream-based algorithms and data structures
are not designed for, as we can see in the example below:

1 vector = read_data('huge_file.dat')

2 filtered_vector = range_filter(vector, filter_specification)

3 med = median(filterd_vector)

4 plot(med)

<caption>Listing 4.3: Example: Steerable Progressive Median with Filtering</caption>

In this pipeline, the `range_filter` function takes its filter specification from an interactive filter interface (e.g., a range slider) that can be changed at any time. Because quantile sketches cannot be changed retroactively, this computation cannot be done with streaming techniques. In the example of the mean computation, updating the mean when data is filtered out can be done iteratively by slightly changing Welford's method and just removing the filtered values. Welford's sketch can be maintained incrementally when adding or removing items. Sketches computed from sets of values can usually be combined, but with limitations. Most sketches can be merged (union of items), but very few support differences (e.g., Welford) or intersections. For the quantile sketch KLL [152], an extension for these operations has been presented recently [345].

4.2.2 Creating a Progressive Algorithm

As described by Schulz et al. [270] and in Section 2.4, progressive algorithms can split their input in two different ways to manage their progressivity. I/O or memory-bound operations can subdivide the data into chunks (*progressive-in-chunks*) as in the examples above, while compute-bound operations can subdivide the computations into steps or iterations (*progressive-in-iterations*).

Ideally, all progressive algorithms should be able to handle data growing by chunks,
but this can come at a high cost. Therefore, it also makes sense for progressive
libraries to provide multiple variations of the same algorithm that are better suited to
data arriving in chunks or all at once. The same is true for steering (as in the previous
example): some algorithms will happily adapt to data changing and being filtered
or updated, but most fundamental algorithms are not designed to deal with data that
changes dynamically.

**Research Agenda:** Several strategies are possible for allowing algorithms to support incremental changes progressively. In the fortunate case where it is possible, an

<figure><img src="image_21.png" /></figure>
<figure><img src="image_22.png" /><figcaption>Figure 4.1: Bar charts visualizing flight delays of four companies. (Left) in a non-progressive setting. (Right) taking into account and visualizing the uncertainty of the progression [224].</figcaption></figure>

algorithm implementation can be adapted to changing data. If that is not possible, higher-level strategies have to be developed to avoid complete recomputation—which is always the last resort. A third option would be the development of algorithms that are progressive in nature—they might be suboptimal in a traditional setting but better support the paradigm.

### 4.2.3 Uncertainty on Aggregated Results

As explained in Chapter 6, a progressive system should assess the quality of its results while computing them. Therefore, aggregated values computed progressively should also maintain a quality assessment (see Definition 11). For example, Figure 4.1 shows two designs of a bar chart, the baseline on the left and one on the right with confidence intervals to render the progressive uncertainty of the visualization.

By contrast, an eager computation of an aggregated value is exact and does not require confidence intervals related to progressivity. These confidence interval values should be computed and stored with the histogram vector. Progressive aggregated functions should, therefore, always return a value with some measure of uncertainty.

## 4.3 Basic Data Structures for Progressivity

All SLs support a core set of basic data structures. These commonly include vectors, multidimensional arrays, and data tables. Many also support tensors (sometimes used as a generalization of arrays and vectors) and graphs (also called networks). In this section, we discuss analogous data structures for PDA.
### 4.3.1 Vectors, Multidimensional Arrays, and Tensors

**Progressively filling tensors** SL-dense tensors are allocated as a single contiguous block of memory to support high-speed vector-based operations. Progressively populating a tensor by e.g., progressively loading a CSV file requires growing the tensor dynamically, something that is ill-fitted for one contiguous block of memory. Consider the following program:

1. `array = read_csv('bigfile.csv')`

2. `derived = sqrt(array)`

<caption>Listing 4.4: Example: Filling a Tensor</caption>

This program computes the square root of each element in the tensor. When run eagerly, only `read_csv` has to allocate an array of unknown size. The `sqrt` function knows the input array size and can allocate it up front. When this code is executed in a progressive manner, the first operation will be performed at the speed of the data transfer so that the array will grow with time, probably by chunk. The second operation will be performed on the chunks already loaded and so will require the `derived` array to also be resized as new chunks arrive. Therefore, progressive systems cannot rely directly on the existing contiguously allocated array semantics provided by traditional computing environments. Progressive systems should re-design more appropriate data representations that will grow gracefully. This is not a problem for traditional databases that handle growth; on the other hand, those databases may be less efficient at computing vector-based operations than SLs.

There are some promising approaches in existing systems that could be adapted. Several array libraries handle memory-bound computation by using tile-based allocation. Out-of-core computation on large arrays (i.e., computations on arrays that are too big for working memory) uses tile-based arrays [250, 294] and splits array operations into tiles. File storage for very large arrays such as `HDF5` [56] and `Apache Parquet` [318] also uses partitioned tiles to support dynamic growth and updating of data. Modern linear algebra libraries such as `Plasma` [71] also split array operations by tiles to parallelize these operations, implementing them with multicores and GPUs. `PDA` could borrow insights from these tile-based systems to support progressive operations efficiently, as is done in e.g., `Modin` [228].

Another possible implementation of efficient growable storage is used in the `MonetDB` [29] database for its data columns. These columns are stored in contiguous main memory using the operating system `mmap` mechanism. This implementation allows the system to dynamically grow the column without copying the content of the
<figure><img src="image_23.png" /></figure>

array [229]. This mechanism can be used instead of tiled arrays, but it has limitations related to the resizing of multi-dimensional arrays. **Research Agenda:** More work is needed to explore different mechanisms for managing tensors in a manner that will allow for the resizing of large tensors progressively and efficiently. Existing SLs are not being implemented to manage dynamically/progressively sized tensors.

Finally, there are embeddable databases such as SQLite and DuckDB [121, 245], which can be used by progressive systems to reliably manage dynamically evolving vectors and tables. It is possible that they will also evolve to better implement the most frequent operations needed by SLs and progressive systems.

### 4.3.2 Data Tables

Most SLs rely on data tables internally. These data structures are well-known and well-aligned semantically with database tables (as in Chapter 3), although they can be much faster for some operations.

Like tensors, none of the existing APIs for tables are intended for use in a progressive setting. There would be challenges with dynamically growing data tables. Some operations could remain instantaneous (e.g., reading the table length), while others might need to return a stream of approximate results rather than exact ones. Other more involved operations, such as aggregation operations or joins, become similar to the online operations that are described in the database literature, with guarantees of the usability of their progressive values and quality. Some research on these operations exists, but it is still far from being readily available [117, 172, 241, 242].

Although in most SLs data tables are implemented as in-memory data structures, there is now a full spectrum of options ranging from ad-hoc in-memory to reliance on database engines. Many databases can be deeply connected to R with “connectors” like RSQLite, MonetDBLite for R, and MonetDB R Connector. More recently, database technologies have been used to re-implement Pandas DataFrames with Modin [228]. Progressive systems should similarly reimplement in-memory data tables with progressive semantics.

### 4.3.3 Networks

Networks are typically implemented as paired tables of vertices and edges, with integrity constraints between the tables. These networks can be implemented over progressive data tables.
Assuming the whole graph is stored in memory, simple depth-first or breadth-
first algorithms to visit a graph are progressive-in-iterations. Many standard graph
algorithms are more complex to transform into progressive form, including the
standard shortest-path algorithms. To date very little research work has been done on
progressive computations on networks (but see [230]).

However, there is a long tradition in network visualization and, more precisely, in graph drawing, of using iterative algorithms for computing graph embeddings (or layouts), starting with force-directed layouts [34, 74]. Many popular graph-drawing software can visualize graphs while the layout algorithm computes the vertex locations. To that extent, progressive visualization has been standard in the graph drawing community for many decades. In the last decade, there have been some extensions that also allow progressive computation for computationally expensive graph measures, such as Betweenness Centrality [162].

**Research Agenda:** Many graph algorithms are based on visitors, which are iterative but do not deliver useful partial results. For example, computing the shortest path in a graph is iterative and can be interrupted at any time, but the utility of partial results has yet to be explored. Alternatively, there are many stochastic algorithms on graphs that could certainly be made progressive, such as those based on random walks [162].

**Research Agenda:** There is no software package or API that provides progressive operations on networks, and the generalization of progressive data analysis on networks remains an open problem.

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

**4.4 Basic Algorithms**

Progressive libraries should be able to handle functions that are time-consuming to compute, which require a more sophisticated implementation than a traditional function. Some state should be maintained across multiple function runs, and the results should be returned along with quality and progression measures to inform the rest of the computation pipeline—and eventually the analyst. Instead of being simple functions, progressive functions become steps in a continuous computation pipeline, which can be implemented as objects with a standard interface. Transforming functions or algorithms into objects is already relatively standard in SLs. For example, the scikit-learn [226] machine learning toolkit in Python provides most of its algorithms as objects.

In scientific computing, most basic algorithms deal with tensors and data tables.
We can use a popular API, such as Python Pandas DataFrames [193] as a starting
<figure><img src="image_26.png" /></figure>

list of basic algorithms. Following the Pandas documentation, for example, we can perform all of the supported operators iteratively or online: all the unary and binary operators, function application, groupBy and windowing, computation of descriptive statistics, and time series-related functions.

Some algorithms will require updating for the scale or the different semantics of progressive implementations: the issues raised in Section 3.4 will apply to implementations of reshaping, sorting, transposing, combining/comparing/joining/merging. For example, progressive sorting algorithms might return partial results with different meanings, e.g., a portion of a table is correctly sorted, the top-k elements are sorted, some selection is sorted, or the dataset is sorted within an error tolerance. Many basic algorithms can be implemented in a progressive fashion with different interpretations of an “estimate” of the result and how to assess the result quality. **Research Agenda: A clear articulation of the semantics of the progressive versions of a function library will help build future scientific software.**

Sorting and top-k algorithms are particularly interesting cases, as these algorithms can produce harmful instability in a progressive setting. Bar charts use height to visualize multiple positive quantitative values and most implementations keep the bars sorted by value to facilitate comparison. In a progressive setting, two or more bars with nearly identical values will see their estimates change slightly over time, potentially producing random changes in order over time (neighboring bars will flip). According to requirement R4, progressive systems should not change views excessively. Therefore, progressive sorting should consider the progressive uncertainty of the values and strive for stability over accuracy at each intermediary step. (See also Section 5.2.1.)

### 4.4.1 Broadcasting Operations

Simple arithmetic operations between tensors and tables can be generalized as *broadcasting* operations [113]. An operation such as $c = 3 \times \log(a) + 2 \times b$ can be performed when $a$ and $b$ are tensors of the same shape, even when they are tables with an identical layout when all the operations $+, \times, \log$ are implemented on all of the columns and values. These operations are typically highly optimized in SLs, and they can be optimized just as easily in progressive computations. However, the semantics of the returned values should be clarified if the computation is not eager. If $a$ and $b$ are extremely large arrays, the result of $c = 3 \times \log(a) + 2 \times b$ will take time to compute and might have to be computed in multiple runs, chunk by chunk. What if an operation performed before the end of the computation tries to access
a portion of *c* that has not yet been computed? Should it block? Or return some
kind of NULL or NOT_YET value? Or should progressive systems be protected from
accessing pending values? **Research Agenda:** This problem does not arise in eager
computation because broadcasting operations are carried out in an atomic fashion.
The semantics of progressive broadcasting operations should be well specified to deal
with multidimensional tiles instead of traditional chunks.

If a progressive function is called during broadcasting, such as an aggregation
function, its progressive results can be assigned, but this result will improve with
time and the management of quality/uncertainty should be addressed, as explained
above. The management of this quality/uncertainty is not yet well understood and
will require extra storage and the computation of an aggregated quality measure to
help assess the overall quality of the result (see also Chapter 6).

**4.4.2 Linear Algebra**

Linear algebra operations can be time-consuming to compute. **Research Agenda:** It is likely that matrix and vector products, matrix decomposition, eigenvalues computation, norms, solving equations, and inverting matrices can be done progressively, but the implementation remains to be done. The algorithms would follow a process similar to tile-based linear algebra libraries such as Dask [250], Modin [228], and Plasma [71], but they should be implemented to return meaningful information at each step. In n-dimensional data containers like tensors and tables, chunks become tiles, and these algorithms would be *progressive-in-chunks*. Current systems implementing tiled-based linear algebra ( [71,228,250]) perform the computations in an order that minimizes data transfer and maximizes cache coherency. Ultimately, they return the full computed result and not an approximate or partial result. Progressive algorithms may choose to return only a portion of the results, e.g., for matrix multiplication, or they may perform the operation tile by tile, returning the resulting tiles in a meaningful order instead of the unpredictable order of Plasma or according to the scheduler order of Dask and Modin. Controlling that order is important in allowing additional progressive operations down the pipeline to start and progress. For example, when multiplying two matrices $o = m \times n$, the progressive results might decide to fill up the $o$ matrix in bands in row order, column order, or some other order. This choice should probably be controlled according to the needs of the operations using the value of $o$. This choice may require an explicit decision from the programmer, or it might be inferred from the pipeline if a high-level PDA language is designed to do so.

Several linear decompositions and eigenvalue computation methods can be per-

<figure><img src="image_27.png" /></figure>

<figure><img src="image_28.png" /></figure>
formed iteratively (*progressive-in-iterations*) or online (*progressive-in-chunks*) [43, 108, 176, 222], using exact or approximate methods. A number of stochastic linear methods are already being used in popular libraries such as scikit-learn [226] because they are faster than the exact methods. Most of these implementations hide their iterative mechanisms from the external API, meaning that they cannot be used in a progressive setting. A progressive system could copy their implementation but expose their inner state. We hope that, as progressive applications and toolkits become more popular, the standard APIs of SLs will provide progressive versions of the iterative methods that they are already implementing. Scikit-learn already offers an online implementation of PCA (Incremental PCA [255]), *progressive-in-iterations*, which has been used in some progressive data analysis applications [304].

### 4.4.3 Statistical Operations

Many statistical operations can be performed online and adapted to be progressive. For example, the mean, variance, and higher moments can be computed progressively using Welford's method [225, 327]. Stable samples of datasets can be used with Reservoir Sampling [317].

Clustering algorithms such as k-means perform very well in a progressive context. The mini-batch implementation [272], for example, is flexible to data being loaded progressively. It improves results progressively, which allows data to be filtered interactively, and can even be steered by changing the centroids interactively without changing its implementation. But not all statistical algorithms are as well-behaved.

For functions performing clustering and multidimensional projections, traditional SLs tend to start from pairwise distance matrices. Their computation is quadratic with the size of the input vectors, meaning that a progressive system will struggle to output meaningful results in a bounded time. Progressive variants of these algorithms could potentially rely instead on approximate k-Nearest Neighbors (kNN) [13] that are very fast to compute and use a space and time complexity almost linear with the number of items. Indeed, progressive versions of kNN are available [75, 142]. **Research Agenda:** Other solutions with different trade-offs could be explored to support the progressive implementation of important statistical operations.

<figure><img src="image_29.png" /></figure>

### 4.4.4 Data Sketching

More complex statistical operations are possible with data sketching, i.e., compact data structures and algorithms that compute and maintain incrementally good and
bounded approximations of values in a streaming fashion. Typical operations include quantiles, equi-depth histograms, top-k values, distinct value estimation, various clustering methods [97], kNN [209], wavelet computation [58], and more recently, PCA computation [94, 175], and Graph algorithms [191].

It is possible that some existing sketches can be improved to handle changes more efficiently than restarting from scratch. Jo et al. [142] have already shown that a data structure and algorithm to compute the k-Nearest Neighbors in an online fashion [209] can be adapted to become progressive. **Research Agenda:** More research will be needed to adapt existing data sketching methods to handle general progressive operations efficiently. Two adaptations will be needed: bounding their computation time (latency) and—for steerable progressivity—handling deletions or value updates in a smarter manner than complete recomputation.

<figure><img src="image_30.png" /></figure>

## 4.5 Input and Output

As explained in Section 3.5.1, reading data from external sources for progressive computations offers many layers of possible optimization not provided by standard input management libraries or services. There are two different issues to address concerning input: detailed input and aggregated input. The progressive output should also deal with communication with e.g., a progressive visualization system through the web or other communication channels.

While progressive input is difficult to manage efficiently, detailed progressive output is a rather straightforward *progressive-in-chunks* process, which can use standard output streams, data formats, or databases. As for progressive aggregated output, because progressive aggregated computations need to provide an estimate of quality, writing that information to an output channel is possible, although there is currently no standard format for that. However, most NoSQL databases use the JSON format for interchange, and JSON is flexible enough to carry the extra information. Several standard file formats and protocols exist to store and transfer data, but very few can encode quality in a standard way, either with confidence intervals or other measures of quality.

### 4.5.1 Detailed Input

The simplest input service consists of reading data linearly by chunk, an operation offered by most standard data input systems from raw files, streams, data tables, and, more generally, from most modern SQL and NoSQL data management systems.
While streaming data progressively is possible with databases and row-oriented file formats, it is not always supported with recent file column-oriented formats, such as Arrow [12] or Parquet [318]. In that case, data will arrive column by column, limiting the options of progressive systems to manage them progressively. The Apache Arrow and Parquet formats allow chunking of data tables, but they come with no recommendation to do so. Therefore, most of these data files are currently stored in public file servers without chunking, preventing their use in progressive systems. Chunking or partitioning this storage would incur almost no overhead in writing and reading. We hope that the experience of early progressive systems and services will convince data providers to provide chunked data files.

The order of the chunks read usually cannot be controlled, and this may bias the data distribution. For example, when reading the New York Taxi dataset [214], which contains billions of taxi trips from remote CSV files, data is stored and will arrive in chronological order, exhibiting strong seasonal biases. Data will not initially be stationary, and it will require that several years of data be read to reach a stationary distribution, slowing down the convergence of any algorithm requiring stationary data.

Although some progressive algorithms have been devised to be resistant to non-stationary data arriving in chunks, they incur a non-negligible cost that slows down convergence in certain cases. For example, Responsive *t*-SNE [142] can compute a multidimensional projection progressively using an adaptation of the *t*-SNE algorithm. It detects non-stationary data and reacts to it by re-launching the “exaggeration” phase of the algorithm that conceptually reshuffles the projection. Figure 4.2 shows the results of applying the algorithm to a completely skewed dataset when the high-dimensional points are read in label order. The final projection is well recovered but requires more resources to compute and devise the algorithm adaptation to protect against non-stationarity.

There are several strategies that can be used to improve linear order reading. In the best case scenario, when the data can be processed before it is loaded, shuffling the data can avoid non-stationarity and possible biases. **Research Agenda:** If data is accessed through a data service such as a database, this non-stationarity problem can be alleviated by providing a mechanism to read it by chunk in random order. OLA-RAW [50] (see Section 3.5.1) shuffles the data incrementally using more sophisticated mechanisms to avoid global pre-processing. While most databases offer data sorting (at a high cost), very few offer shuffling. Although the problem has been explored in research [237], existing systems offer few solutions.

<figure><img src="image_31.png" /></figure>
<figure><img src="image_32.png" /><figcaption>Figure 4.2: Responsive *t*-SNE [142] progressive steps for computing a multidimensional projection of the MNIST dataset loaded in chunks in a very skewed order (worst case). The algorithm eventually converges but is slower to deliver a faithful picture of the full dataset than if the input data were shuffled.</figcaption></figure>
In many situations, when data is stored in one location and needs to be used (e.g., visualized) in another, there is no need to transfer all the detailed data, since it can be sent in an aggregated form. Aggregated values are typically histograms or single values that can also be computed progressively. Current databases only allow computation of the final exact results, but a progressive system could easily receive a progressive histogram or a progressive value with confidence intervals, since this is already what it deals with internally. This kind of service is not yet available, but is easily foreseeable and would be useful, e.g., for direct consumption of aggregated values on large data over the web. This is what progressive databases, as described in Chapter 3, aim to provide.

## 4.6 Specific Progressive Services and Strategies

In addition to fundamental algorithms and data structures, progressive computations need to have *strategies* to manage progressive updates and keep track of data changes in the computation pipeline. The ProgressiVis toolkit [83] explores some possible approaches. Although some of these are discussed here, other possibilities surely exist. **Research Agenda:** More research and engineering work is needed to better understand what strategies might be effective in managing interactive progressive computations in different exploration scenarios.

<figure><img src="image_33.png" /></figure>

### 4.6.1 Progressive Stability and Normalization

As we will discuss in Section 5.2.1, a *stable* output or visualization is one that does not change or move excessively between progressive steps. In a chart, for example, the axes and color scales should remain consistent, changing as little as possible. There will often be a trade-off, then, when underlying data has changed substantially—should the visualization stay true to the previous steps or to the current state?

A useful instance of illustrating the trade-offs around stability comes from axis normalization. In many data analysis pipelines, data should be normalized: the values of a vector should be scaled to fit between e.g., [0, 1] or with a mean of 0 and a standard deviation of 1. The normalization process needs to know the exact bounds or distribution of the data before normalizing them. This is typically a two-pass operation. In a progressive setting, each new incoming chunk of data can change the bounds or the distribution, and if the normalization has to adapt at each chunk,
then all of the normalized data may also change at each chunk. This may, in turn, affect other operations down the pipeline and may even trigger a change in the scale of the visualized data, producing an undesirable instability on the display. Different strategies can be devised to avoid these frequent jumps and resets in the computations and visualizations, such as temporarily extending the distribution or temporarily filtering out out-of-distribution data. Strategies are always required for visualization at the end of the pipeline. But in some cases statistical or machine learning operations may also need them too.

The first strategy—temporarily extending the distribution—consists of adjusting the bounds of the distribution when it has to grow by some percentage of the growth rate. For example, if the first chunk of data is bounded by [-1, 1], the maintained bounds will be constrained to grow by no more than 5% to become [-1.05, 1.05], ensuring that the bounds don't shift excessively. Extending the distribution with a fixed percentage of the growth stabilizes the rescaling process somewhat at the cost of keeping bounds that are too narrow, with a bounded error (5% in the example). This option can still suffer from sudden changes if extreme values are not well distributed in the data, but for shuffled data this simple strategy is a clear improvement over the baseline.

Instead of increasing the bounds for normalization, a progressive pipeline can filter out entries that are out-of-bounds until too many of them have been seen and then trigger a full recomputation. While interacting with the computation, the analyst can also monitor the out-of-bounds entries and trigger the recomputation only when desired.

**Research Agenda:** There are certainly other methods for dealing with progressive normalization, but having the user in the loop allows for simple yet effective solutions instead of more complicated ones, e.g., trying to model the true distribution from an incomplete one.

<figure><img src="image_34.png" /></figure>

### 4.6.2 Data Change Management

When a progressive application is built from scratch and all the dependencies are well known, a centralized approach can be used to orchestrate the multiple algorithms and feed the data to all the concerned parts of the software as it arrives. In contrast, to implement modular progressive algorithms and data structures, one important property of a toolkit is to maintain a separation of concern between all its components. For this purpose, the ProgressiVis toolkit [83] provides a mechanism to allow progressive *computing modules* (the equivalent to progressive functions) to keep track of changes
between each run in the data structures they operate on.

This issue can be related to the need for communication mechanisms between back-ends and the User Interface. Popular mechanisms such as the “Model-View-Controller” [164], the “Observer” design pattern [96, p. 293], and Functional Reactive Programming [323] all maintain a back-end to track what has changed, and a front-end that visualizes the differences. In interactive systems, changes happen every time the user moves the pointer or touches a key; in databases, changes occur with each commit. In the ProgressiVis system, changes come each time a progressive module completes a chunk or a certain number of iterations.

For example, returning to the normalization example above, the minimum and maximum values of each table column have to be maintained. A progressive module is in charge of computing and maintaining the minimum values of each column contained in a data table (call it the *Min* module), and another one for the maximum values. The *Min* module will be run each time the data table is modified, which is usually by chunk when the table is loaded or filled. So, if the data table is loaded from a CSV file, at every chunk (e.g., every 10,000 records), *Min* will run to update the minimum values it maintains. Therefore, at each run, it requests the changes from the last call in terms of a *delta*.

Similar to database triggers, the *delta* structure is made of three parts: the rows *created*, *deleted*, and *updated* (ignoring here that data columns can also be created, deleted, and updated).

* Assuming the progressive system is simply loading a large table, the *Min* module receives a delta with only created rows. Its task is simple: to compute the minimum over the new row values and combine it with the already computed running column minima.

* If the progressive system is computing the *Min* over a table filtered by a user, using e.g., a range slider, ranges of values will be filtered out or added back. The delta will thus contain *deleted* and *created* values, and things get more complicated. The simplest strategy is to restart the module to compute the minimum values from scratch. There are potentially smarter strategies that can be used, but they are also more complex. For example, one of the ProgressiVis toolkit *Min* modules is optimized to handle *deleted* values; it keeps track of the indices that reached the running minimum value of each column. If the *deleted* values do not intersect with these indices, there is no need to restart from scratch since the minimum has not been changed.

* If the progressive system is computing the content of the table iteratively, e.g., the *x*, *y* columns computing by a graph layout algorithm, the computed values
will change with each iteration and the Min module will receive deltas with *updated* items. In that case, resetting the module might be the easiest and most efficient approach.

The communication mechanism based on deltas allows non-centralized handling of the data changes in algorithms/modules, but it adds some burden to each module.

Different algorithms handle these deltas in different ways. Some algorithms can ignore them (e.g., many iterative algorithms such as *k*-means clustering), while others can only deal with creations and in other cases need to restart from scratch. The level of complexity for managing these deltas varies across algorithms, but the information they carry is, in most cases, essential.

This *delta* service to keep track of what happened to a data structure since the last time it was processed is very useful to progressive libraries and algorithms in maintaining good separation of concern between algorithms and state management, but it requires some specific data management efforts from the data structures. The implementation of that mechanism is slightly different from database triggers. Database triggers can be heavy to implement since they require the database to keep track of all the changed values of all the tracked tables to retrieve the old values of updated and deleted rows in the trigger management procedure (though not all databases provide these previous values). ProgressiVis management is lighter because it does not keep track of previous values, but only the indices that have changed, which it does through a very efficient data structure based on compressed bitsets [47]. This mechanism of change tracking is implemented in several progressive-aware data structures available in ProgressiVis: tables, columns (that also implement vectors), dictionaries, and bitsets.

**Research Agenda:** This state management is specific to ProgressiVis, and there may be alternative ways of maintaining the separation of concerns between progressive algorithms and data structures, but some mechanism should be provided to keep track of the changes to the data structures that occur when re-entering progressive algorithms. This problem is novel and calls for more research.

<figure><img src="image_35.png" /></figure>

## 4.7 Summary

Like every programming environment used in data analysis, PDA will need to provide a set of algorithms and data structures suited to progressive computations. These data structures and algorithms have to provide a particular API to be usable progressively: the functions should not only return values, but also some quality information that is
useful in assessing their utility, and the data structures should be able to compute what changed since the last time they were used by a progressive algorithm. Progressive systems should also provide a variety of algorithms that are suitable in different situations: progressive-in-chunks or progressive-in-iterations.

Some implementations will accommodate both of these cases, but will have performance issues. In addition, progressive algorithms should be used with particular strategies to avoid triggering complete recomputations, and these strategies are new and need to be studied further. Finally, on top of these requirements, progressive libraries or toolkits should also implement internal mechanisms to track changes in data structures that are used multiple times by the algorithms. The ProgressiVis toolkit implements a method based on deltas over its data structures so that each algorithm can determine what changed since the last time they ran. There may be other possible mechanisms, and they need to be studied and compared for efficiency and usability from a programming point of view.

Overall, the development of fundamental algorithms and data structures for progressive systems will require a new line of research for adapting existing algorithms. But it will also be necessary to devise software engineering patterns and architectures to facilitate the design and development of progressive systems.

The mean and median examples in Section 4.2 represent an easy and hard case of algorithms regarding progressivity. Wickham [330] distinguishes three types of summary statistics: distributive (e.g., count, sum), algebraic (e.g., mean, standard deviation), and holistic (e.g., median). **Research Agenda:** The first two are easy to compute progressively, but the last one requires more research on approximate methods, including data sketching.

**Research Agenda:** More work is needed to characterize existing algorithms in terms of progressivity and to help in the discovery of generic transformation methods or strategies to make more of them progressive.

The adaptation of algorithms to become progressive can be viewed as an extension of transforming algorithms to become online, with soft real-time constraints. It can also be viewed from the perspective of streaming algorithms to allow them to adapt to changing data, whereas data sketches are only implemented for data streaming in and not updated over time. Several algorithms have already been transformed into progressive counterparts, and we look forward to the development of more of these adapted or new algorithms.

<figure><img src="image_36.png" /></figure>

<figure><img src="image_37.png" /></figure>
# 5 Visualization

<table><tr><td>5.1</td><td>From Classic to Scalable Visualization</td><td>70</td></tr><tr><td>5.2</td><td>From Scalable to Progressive Visualization</td><td>73</td></tr><tr><td>5.2.1</td><td>Progressive Rendering</td><td>73</td></tr><tr><td>5.2.2</td><td>Interaction, Steering, and Control</td><td>78</td></tr><tr><td>5.3</td><td>Designing a Progressive Visual Analytics System</td><td>79</td></tr><tr><td>5.3.1</td><td>Choose the Right Visual Mapping</td><td>79</td></tr><tr><td>5.3.2</td><td>Represent the Changes</td><td>80</td></tr><tr><td>5.3.3</td><td>Visualizing the Progression</td><td>81</td></tr><tr><td>5.3.4</td><td>Interaction Between Visualization and Progression</td><td>82</td></tr><tr><td>5.4</td><td>Existing Visualization Approaches in PDA</td><td>82</td></tr><tr><td>5.4.1</td><td>DimXplorer</td><td>83</td></tr><tr><td>5.4.2</td><td>InsightsFeed</td><td>85</td></tr><tr><td>5.4.3</td><td>ProReveal</td><td>87</td></tr><tr><td>5.5</td><td>Challenges for Progressive Visual Analytics</td><td>89</td></tr><tr><td>5.6</td><td>Summary</td><td>90</td></tr></table>

**Authors** Marco Angelini and Jaemin Jo

User interface designers for PDA systems face a unique challenge: they not only have to enable the user to interpret the final results of a computation, but also to make sense of intermediate results, assess uncertainty, comprehend the progress of progressive computation, and steer the computation. A poorly designed visualization can lead the user to incorrect findings or imply unfounded accuracy, reinforcing her biases. Well-designed visualizations and user interfaces are therefore critical in PDA. We refer to the visualization aspects of PDA as Progressive Visual Analytics (PVA).

In this chapter, we begin by discussing the visualization community's journey from classic visualization to progressive visualization. Starting with classic visualization techniques, typically for small-scale data, we offer an overview of the history of the attempts that have been made to allow visualizations to scale to the large data sizes that are common in PDA. We then raise some of the questions and challenges that come up when visualization is used for a sequence of progressively changing data in
PVA. To illustrate how these challenges can be met, we briefly describe three PVA
systems that grapple with these questions and conclude with a future research agenda
for PVA.

5.1 From Classic to Scalable Visualization

Although the scalability of visualization is a major concern even in classic visual-
ization systems [249,330], its importance becomes more evident in PVA, especially
with progressive-in-chunks involving very large datasets. As shown in Figure 5.1,
many common visualization techniques, such as scatterplots, parallel coordinates,
and pie charts, do not scale well graphically. In particular, techniques where each
data item is mapped to a single graphical element are subject to overplotting, as the
number of visual elements in the scene is bound to the data size, which can grow
arbitrarily large.

Figure 5.1 highlights some of the main issues related to visual scalability: *number of items, number of dimensions, and number of distinct categorical values*. One prominent issue with non-scalable visualization techniques in Figure 5.1 is the overplotting problem, which results from the number of visual items drawn. There are five methods typically used to address visual scalability: *sampling, filtering, aggregation, dimensionality reduction, and summarization*.

The most straightforward solution to the problem of the number of items is to reduce the number of elements that have to be shown. *Sampling* achieves this, but it should be used with care, since important but infrequent patterns in data, such as outliers, can be left out [25] (see Figure 5.1a (center)). *Filtering* is another method for reducing the number of items and can be effective if the selectivity of the filter applied is high enough. However, both methods cannot support overview tasks where the full dataset should be visualized.

To address the overplotting problem while faithfully showing all of the data,
one can map multiple data items to one visual element, as in *aggregation*-based
techniques [330]. For example, splatterplots [190] overcome the overplotting problem
of conventional scatterplots by representing dense data points as contours while
showing individual outliers as points around the contours. Density maps are another
approach to scaling scatterplots. These maps split a 2D data space into 2D bins,
count the number of items belonging to each bin, and represent the counts, typically
using color (see Figure 5.1a (right) and Figure 5.1b (right)). One benefit of density
maps is that the number of visual elements drawn (i.e., the number of 2D bins) can
<figure><img src="image_38.png" /><figcaption>(a) Visualizing locations of 100k yellow taxi pickups in NYC [214] (sample from May 2016) produces overplotting in the center of Manhattan (left). Sampling (center) avoids overplotting but also erases information, such as the multiple pickups occurring along the paths from the airports to Manhattan. Using a density plot (right) with appropriate parameters allows for showing the main patterns and preserving sparse areas.</figcaption></figure>

<figure><img src="image_39.png" /><figcaption>(b) Parallel Coordinates on large datasets also produce overplotting (left). Transparency (center) can alleviate the problem for a few thousand items. Density-based parallel coordinates (right) partially mitigate this on large datasets, showing the main trends but hiding outliers. From [115].</figcaption></figure>

<figure><img src="image_40.png" /><figcaption>(c) Pie charts do not scale well with the number of categories in general (left). Gathering small categories in an “other” category (center) can sometimes alleviate the problem, but using a more appropriate visualization, such as a bar chart, can be a better option (right). Courtesy of https://www.mssqltips.com/sqlservertip/2773/handling-a-large-number-of-categories-in-a-sql-server-reporting-services-pie-chart/</figcaption></figure>

Figure 5.1: Standard visual representations do not scale well as data grows. Scatterplots suffer from overplotting, as well as parallel coordinates. Even pie charts become unusable when the number of categories grows. All of these techniques require expensive analytical methods to correctly handle scale.
be user-defined, completely independent of the data size, which allows the rendering
process to finish within a predictable time.

Unfortunately, not all non-scalable visualization techniques have scalable counterparts. For example, bar charts, a very basic visualization technique, scale well for the count of items represented in bars, but not for the number of bars, the number of distinct categories usually represented on the x-axis. It is difficult to address this problem using simple aggregation, as in Figure 5.1c (center). Furthermore, adopting aggregation-based techniques can present new design challenges for visualizing the information that could be easily shown in the original non-aggregate plots. For example, in a conventional scatterplot, the class membership of an item can be easily encoded as the color of the corresponding point. In density maps, because multiple items from different classes can be aggregated into the same 2D bin, showing the class membership introduces new considerations, as discussed in Jo *et al.* [143].

Parallel Coordinates and Scatterplot Matrices are limited to visualizing tens of dimensions. When the number of dimensions increases, visualization can use *dimensionality reduction* methods, which are either steered by human selection, i.e., showing the bivariate relationships between the chosen attributes as a SPLOM, or based on automatic techniques such as *t*-SNE [311] or UMAP [192], i.e., showing a low-dimensional projection of high-dimensional points as a scatterplot. The reduced dimensions can help place items in space with a meaningful distance function, at the cost of losing interpretable dimensions. These algorithms are expensive to compute, but progressive implementations do exist [142, 160, 232, 233] (see Figure 4.2).

Another possible solution to scalability consists of using summarization techniques, such as presenting distributions of the data. For example, the scagnostics [333] technique computes a number of descriptive techniques for different dimensions, such as how skewed and how sparse the data is, akin to a dataset “facial composite”.

Most of the known techniques used to scale visualizations are expensive to compute. Even sampling, which is fast for very simple techniques, can become expensive when trying to avoid artifacts [25, 48, 317]. Therefore, visualizing data at scale implies an extra cost not only because of the rendering, but also because of the analytical cost of controlling visualization quality and achieving a meaningful rendering.

Furthermore, to remain interactive, visualizations should react with low latency, which is something that eager scalable visualizations cannot guarantee. One important advantage of PDA is that it allows scalable visualizations that are as interactive as their small-data equivalents, provided they are properly adapted.
## 5.2 From Scalable to Progressive Visualization

PVA introduces four new groups of issues: (1) progressive rendering; (2) interaction, steering, and control in a progressive setting; (3) PDA uncertainty, as addressed in Chapter 6; and (4) new tasks such as monitoring, attention management, and early decision-making, as addressed in Chapter 7.

### 5.2.1 Progressive Rendering

In a classic visualization, where data are fully available at the time of rendering, we expect to be able to create the visualization in a single step. By contrast, a progressive visualization is updated at a rate that depends on the progress of intermediate results. The visualization and graph drawing communities have long been aware of the problem of representing a series of partial results from a progressive computation [54, 117, 216, 290]. Graph drawing with spring models dates back as far as the early 1980s [74].

In the last 20 years, there has been a greater focus on big data analysis coupled with a rich data visualization environment and the rise of Visual Analytics [154] as a discipline. The first works on the topic of instrumenting, steering, and evaluating PDA with the use of visualization appeared with Williams & Munzner [334], Fisher et al. [89], and Angelini et al. [9]. The field was labeled Progressive Visual Analytics by Stolper et al. [293].

As a pioneering progressive visualization, Fisher et al. [89] chose to use a histogram in their SampleAction system for its simplicity and familiarity (see Figure 5.2): the height of a bar shows the estimated value from each intermediate partial result, while the error bars show the confidence bounds around the relative estimate. The error bars show the range of values that may occur at the confidence levels. In this way, the user can issue a query and inspect the partial results visually by interpreting column estimates and the probability of them being included in a shrinking confidence interval. The progressive histogram in the SampleAction system illustrates well the new design concerns that arise in the transition from scalable to progressive visualization. The two prominent concerns are the **stability** and **uncertainty** of progressive visualization.

**Stability** A progressive visualization needs to be updated to faithfully show the most up-to-date results. However, updating a progressive visualization generally means confronting a tension between quality and stability, especially with aggregation-based
<figure><img src="image_41.png" /><figcaption>Figure 5.2: A screenshot from the SampleAction system [89]: the analyst is looking at flight delays by day of the week. The histogram on the right represents the current estimates with dark blue bars, and the expected range of values with pale blue dots. A progress indicator on top shows that just 0.32% of the dataset has been processed.</figcaption></figure>

techniques.

In classic visualization, only one state exists for the visualization: the final one. But in PVA, the system must produce a visualization for each intermediate result. This consideration has consequences even for simple visual mappings.

For example, consider a bar chart showing the top 10 categories and with values in descending order. As more data points arrive progressively, some categories may enter or leave the top 10, the order might change, and the axes may need rescaling. Not unlike the discussion about tracking normalization in Section 4.6.1, the visualization designer must choose whether to maintain the precision of the latest data or stability.

Stability refers to the need to preserve, to the fullest extent possible, all of the
<figure><img src="image_42.png" /><figcaption>Figure 5.3: In the NYC Taxi dataset [214], the density map of taxis loaded progressively (left) becomes the top left point (right) after loading a data row representing a taxi that traveled to Florida with its meter on, creating a scale problem.</figcaption></figure>

aspects of the visualization that might help the user maintain their mental model. These include the scale and order of the axes, the color mapping, and all other aspects of the visual mapping. In general, keeping these stable will allow the user to more easily understand the changes that are made.

The nature of progressivity highlights some of the challenges of stability. Outliers distorting an axis are an excellent example: in the NY Taxi dataset [214] shown in Figure 5.1a, one taxi forgot to turn off its meter when traveling to Florida. When its record arrives in a chunk, the scale dramatically changes and the NYC area shrinks to a few pixels, as shown above.

We have discussed some approaches to improving stability in Section 4.6.1. Indeed, many algorithms can be stabilized at the cost of layout quality. A progressive Treemap is an interesting example (Figure 5.4c). One can fully re-layout and render the Treemap when new data arrives, independently of the Treemap that was previously on the screen. In this case, a layout can be obtained that is optimized to the current data in terms of quality metrics such as aspect ratio [289]. However, since the coherence between the old and new Treemaps is broken, the user will see a sequence of Treemaps that “dance” with each chunk, which makes it harder for the user to visually track the changes and understand temporal patterns. On the other hand, one can consider the previous layout when computing the new one, seeking better stability between them. In the Treemap example, one can minimize the relative position change for the same rectangle between the frames [289, 315] at the expense of visual quality. There are similar tradeoffs for graph drawing: a stabilized transition may not choose as optimal a layout [202], as a drawing from scratch would.
<figure><img src="image_43.png" /><figcaption>(a) It is common to sort the bars in a bar chart by their height (left). When the heights change due to progressive computation, maintaining the order of the items on the x-axis may conflict with maintaining the ordering on the y-axis (center and right).</figcaption></figure>

<figure><img src="image_44.png" /><figcaption>(b) To make scatterplots more stable, the domains of the axes can be fixed, which means that an out-of-range outlier that is found during progressive computation (left and center) will not be shown. When the domains are updated to reflect the change, the visualization becomes less stable (left and right).</figcaption></figure>

<figure><img src="image_45.png" /><figcaption>(c) When a Treemap is updated, one can maintain the topology of the rectangles in the previous frame for better stability at the cost of visual quality, i.e., aspect ratio (left and center). By contrast, fully rerendering the Treemap loses topological consistency (left and right).</figcaption></figure>

Figure 5.4: When a visualization is updated progressively, there is often a tradeoff between stability and quality.